On the Complexity of Testing Implications of Functional and Join Dependencies

DOI10.1145/322276.322280MaRDI QIDQ3939277zbMATH OpenOpenAlexWikidataFDO

Authors David Maier, Yehoshua Sagiv, Mihalis Yannakakis

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

functional dependencyjoin dependencymembership algorithmmultivalued dependencyNP-completerelational database

Mathematics Subject Classification ID

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

Cited in

(13)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3939277)