On the Computational Complexity of Cardinality Constraints in Relational Databases
We show that the problem of determining whether of not a lossless join property holds for a database, in the presence of key dependencies and cardinality constraints on the domains of the attributes is NP-complete.
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148987 |
| _version_ | 1826192645483921408 |
|---|---|
| author | Kanellakis, Paris C. |
| author_facet | Kanellakis, Paris C. |
| author_sort | Kanellakis, Paris C. |
| collection | MIT |
| description | We show that the problem of determining whether of not a lossless join property holds for a database, in the presence of key dependencies and cardinality constraints on the domains of the attributes is NP-complete. |
| first_indexed | 2024-09-23T09:27:04Z |
| id | mit-1721.1/148987 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T09:27:04Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1489872023-03-30T04:12:03Z On the Computational Complexity of Cardinality Constraints in Relational Databases Kanellakis, Paris C. We show that the problem of determining whether of not a lossless join property holds for a database, in the presence of key dependencies and cardinality constraints on the domains of the attributes is NP-complete. 2023-03-29T14:16:36Z 2023-03-29T14:16:36Z 1980-03 https://hdl.handle.net/1721.1/148987 6635694 MIT-LCS-TM-160 application/pdf |
| spellingShingle | Kanellakis, Paris C. On the Computational Complexity of Cardinality Constraints in Relational Databases |
| title | On the Computational Complexity of Cardinality Constraints in Relational Databases |
| title_full | On the Computational Complexity of Cardinality Constraints in Relational Databases |
| title_fullStr | On the Computational Complexity of Cardinality Constraints in Relational Databases |
| title_full_unstemmed | On the Computational Complexity of Cardinality Constraints in Relational Databases |
| title_short | On the Computational Complexity of Cardinality Constraints in Relational Databases |
| title_sort | on the computational complexity of cardinality constraints in relational databases |
| url | https://hdl.handle.net/1721.1/148987 |
| work_keys_str_mv | AT kanellakisparisc onthecomputationalcomplexityofcardinalityconstraintsinrelationaldatabases |