On The Recognition Of Coverings Of Acyclic Database Hypergraphs

Summary: Model schemas as hypergraphs with directed hyperedges encoding join and functional dependencies; define a database-hypergraph closure and relate it to JDs, FDs, tableaux and the chase. Prove equivalence: hypergraph admits an acyclic schema iff its closure is acyclic, and give algorithms showing recognition is polynomial-time in most cases. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 665
Venue: PODS
Year: 1983
Pagerank: 5.6746696e-05
Overall Rank: 7,203 | 50.59%
DOI: 10.1145/588058.588092

Incoming Non-self Citations Over Time

Authors

1. Domenico Sacca (CRAI; IBM Research Laboratory)

BibTeX Citation

@inproceedings{sacca_pods83,
        address = {New York, NY, USA},
        series = {{PODS} '83},
        title = {{ON THE RECOGNITION OF COVERINGS OF ACYCLIC DATABASE HYPERGRAPHS}},
        url = {https://dl.acm.org/doi/10.1145/588058.588092},
        doi = {10.1145/588058.588092},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Sacca, Domenico},
        year = {1983}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,561	On the Recognition and Design of Acyclic Databases	1984	PODS	6.1741042e-05
6,516	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD	5.8545649e-05
6,698	Properties Of Database Schemata With Functional Dependencies	1984	PODS	5.7985588e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
40	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00046918506

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,561	On the Recognition and Design of Acyclic Databases	1984	PODS
2	5,140	Transforming Cyclic Schemas Into Trees (Extended Abstract)	1982	PODS
3	13,194	ON FINITE FD-ACYCLICITY (Extended Abstract)	1986	PODS
4	7,186	Structure and Complexity of Bag Consistency	2021	PODS
5	3,527	Functional Dependencies on Cyclic Database Schemes	1983	SIGMOD
6	13,230	On the Decomposition of Join Dependencies	1984	PODS
7	6,698	Properties Of Database Schemata With Functional Dependencies	1984	PODS
8	13,227	Dependency Characterizations For Acyclic Database Schemes	1984	PODS
9	14,491	Line Graph of Gamma-Acyclic Database Schemes and Its Recognition Algorithm	1984	VLDB
10	7,053	Connections in Acyclic Hypergraphs -- Extended Abstract	1982	PODS