On the complexity of join dependencies

DOI10.1145/5236.5237zbMath0602.68097OpenAlexW2000391493WikidataQ114613779 ScholiaQ114613779MaRDI QIDQ3738613

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

relational databaseconsistency checkinghingeintegrity checkingdegree of cyclicitydecomposition of join dependencies

Mathematics Subject Classification ID

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

Related Items

A Generalization of the Inference Rules for Join Dependencies in Databases, Domain filtering consistencies for non-binary constraints, Strictly chordal graphs are leaf powers, Accelerating new product development by overcoming complexity constraints, Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms, A Formal Context for Acyclic Join Dependencies, Local consistency for extended CSPs, Decomposing constraint satisfaction problems using database techniques