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: h883124fc7bb5ca31
Venue: PODS
Year: 1983
Pagerank: 5.5473458e-05
Overall Rank: 7,343 | 50.64%
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,691	On the Recognition and Design of Acyclic Databases	1984	PODS	6.0355739e-05
6,643	The Design of non-1NF Relational Databases into Nested Normal Form	1987	SIGMOD	5.7232205e-05
6,834	Properties Of Database Schemata With Functional Dependencies	1984	PODS	5.6684547e-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
41	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00045899672

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,691	On the Recognition and Design of Acyclic Databases	1984	PODS
2	5,257	Transforming Cyclic Schemas Into Trees (Extended Abstract)	1982	PODS
3	13,484	ON FINITE FD-ACYCLICITY (Extended Abstract)	1986	PODS
4	7,330	Structure and Complexity of Bag Consistency	2021	PODS
5	3,598	Functional Dependencies on Cyclic Database Schemes	1983	SIGMOD
6	13,520	On the Decomposition of Join Dependencies	1984	PODS
7	6,834	Properties Of Database Schemata With Functional Dependencies	1984	PODS
8	13,517	Dependency Characterizations For Acyclic Database Schemes	1984	PODS
9	14,801	Line Graph of Gamma-Acyclic Database Schemes and Its Recognition Algorithm	1984	VLDB
10	7,187	Connections in Acyclic Hypergraphs -- Extended Abstract	1982	PODS