On the Complexity of Testing Implications of Functional and Join Dependencies

DOI10.1145/322276.322280zbMath0481.68094OpenAlexW2006564766WikidataQ114614036 ScholiaQ114614036MaRDI QIDQ3939277

Mihalis Yannakakis, Yehoshua Sagiv, David Maier

Publication date: 1981

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322276.322280

zbMATH Keywords

relational databaseNP-completefunctional dependencymultivalued dependencyjoin dependencymembership algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Information storage and retrieval of data (68P20)

Related Items (13)

Independent database schemas ⋮ On improving dependency implication algorithms ⋮ Characterization of desirable properties of general database decompositions. ⋮ On minimal constraint networks ⋮ Structure of closures in relational schemas with join and functional dependencies ⋮ An incremental algorithm for computing ranked full disjunctions ⋮ A corrected 5NF definition for relational database design ⋮ Appropriate inferences of data dependencies in relational databases ⋮ Characterisations of multivalued dependency implication over undetermined universes ⋮ Inferring multivalued dependencies from functional and join dependencies ⋮ On the representation and querying of sets of possible worlds ⋮ Querying incomplete data over extended ER schemata ⋮ I/O-efficient join dependency testing, Loomis-Whitney join, and triangle enumeration

This page was built for publication: On the Complexity of Testing Implications of Functional and Join Dependencies