ON FINITE FD-ACYCLICITY (Extended Abstract)

Summary: Studies database schemes under FDs with finite representative instances and introduces fd-acyclicity: every pairwise-consistent satisfying state is join-consistent. Shows fd-acyclicity ⇔ hypergraph acyclicity when relation schemes are FD-closed, and gives a polynomial-time test when an FD cover is embedded. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 766
Venue: PODS
Year: 1986
Pagerank: 5.093636e-05
Overall Rank: 13,194 | 9.48%
DOI: 10.1145/6012.15422

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Yehoshua Sagiv (Hebrew University; Stanford University)
2. Oded Shmueli (Technion)

BibTeX Citation

@inproceedings{sagiv_pods86,
        address = {New York, NY, USA},
        series = {{PODS} '86},
        title = {{ON FINITE FD-ACYCLICITY (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/6012.15422},
        doi = {10.1145/6012.15422},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Sagiv, Yehoshua and Shmueli, Oded},
        year = {1986}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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
134	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00030343737
162	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00027886326
3,222	Comprehensive Approach to the Design of Relational Database Schemes	1984	VLDB	7.6260706e-05
3,527	Functional Dependencies on Cyclic Database Schemes	1983	SIGMOD	7.3428228e-05
6,698	Properties Of Database Schemata With Functional Dependencies	1984	PODS	5.7985588e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	162	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS
2	4,659	On The Complexity And Axiomatizability Of Consistent Database States	1984	PODS
3	5,351	Constant Time Maintenance or The Triumph of the fd.	1986	PODS
4	9,332	Unifying Functional and Multivalued Dependencies for Relational Database Design	1986	PODS
5	2,047	Functional and Inclusion Dependencies: A Graph Theoretic Approach	1984	PODS
6	7,203	On The Recognition Of Coverings Of Acyclic Database Hypergraphs	1983	PODS
7	13,170	Logical Design of Relational Database Schemes	1987	PODS
8	13,227	Dependency Characterizations For Acyclic Database Schemes	1984	PODS
9	6,698	Properties Of Database Schemata With Functional Dependencies	1984	PODS
10	3,527	Functional Dependencies on Cyclic Database Schemes	1983	SIGMOD