On the complexity of join dependencies

DOI10.1145/5236.5237MaRDI QIDQ3738613zbMATH OpenOpenAlexWikidataFDO

Authors Marc Gyssens

Publication date 1986

Published in ACM Transactions on Database Systems (Search for Journal in Brave)

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

zbMATH Keywords

consistency checkingrelational databasehingeintegrity checkingdegree of cyclicitydecomposition of join dependencies

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4043317
• Join dependencies in relational-database design
• On acyclic database decompositions
• Acyclic join dependency and data base projections
• Complete decompositions of join dependencies

Cited in

(20)

• Losslessness and project-join constructibility in relational databases
• A Generalization of the Inference Rules for Join Dependencies in Databases
• scientific article; zbMATH DE number 4043317 (Why is no real title available?)
• Join dependencies in relational-database design
• Decomposing constraint satisfaction problems using database techniques
• I/O-efficient join dependency testing, Loomis-Whitney join, and triangle enumeration
• A formal context for acyclic join dependencies
• On the join dependency relation in multinomial lattices
• Local consistency for extended CSPs
• Domain filtering consistencies for non-binary constraints
• Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
• Enumeration complexity of conjunctive queries with functional dependencies
• Size bounds and query plans for relational joins
• Testing arbitrary subhypergraphs for the lossless join property
• Complete decompositions of join dependencies
• On acyclic database decompositions
• Acyclic join dependency and data base projections
• Strictly chordal graphs are leaf powers
• Accelerating new product development by overcoming complexity constraints
• Problem of optimizing the number of block accesses in performing relational join is NP-hard

This page was built for publication: On the complexity of join dependencies

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