Functional and Inclusion Dependencies: A Graph Theoretic Approach

Summary: Graph-theoretic framework for FD+IND implication; proves decidability for the unrestricted implication when INDs are typed and FDs are acyclic. Establishes NP- and PSPACE-hardness (bounded domains) and shows no k-ary complete axiomatization even under pairwise consistency. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hd1b8406bc0fa9206
Venue: PODS
Year: 1984
Pagerank: 9.0521246e-05
Overall Rank: 2,098 | 85.90%
DOI: 10.1145/588011.588016

Incoming Non-self Citations Over Time

Authors

1. Stavros S. Cosmadakis (Massachusetts Institute of Technology)
2. Paris C. Kanellakis (Brown University)

BibTeX Citation

@inproceedings{cosmadakis_pods84,
        address = {New York, NY, USA},
        series = {{PODS} '84},
        title = {{Functional and Inclusion Dependencies: A Graph Theoretic Approach}},
        url = {https://dl.acm.org/doi/10.1145/588011.588016},
        doi = {10.1145/588011.588016},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cosmadakis, Stavros S. and Kanellakis, Paris C.},
        year = {1984}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
392	Data Exchange: Getting to the Core	2003	PODS	0.0001922472
517	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.00016948466
3,083	An Axiomatic Approach to Deciding Query Safety in Deductive Databases	1988	PODS	7.6632607e-05
3,561	The Complexity of Data Exchange	2006	PODS	7.2055481e-05
5,187	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS	6.2371772e-05
11,106	Entity/Relationship Graphs: Principled Design, Modeling, and Data Integrity Management of Graph Databases	2025	SIGMOD	4.9793485e-05
13,315	Making Object-Oriented Schemas More Expressive	1994	PODS	4.9793485e-05
13,474	Independent Database Schemes Under Functional and Inclusion Dependencies	1987	VLDB	4.9793485e-05

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
10	Extending the Data Base Relational Model to Capture More Meaning	1979	SIGMOD	0.00075944947
136	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00029740459
159	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS	0.00027958527
1,208	Towards a Sound View Integration Methodology	1983	PODS	0.00011538101
3,598	Functional Dependencies on Cyclic Database Schemes	1983	SIGMOD	7.1782813e-05
3,968	Inclusion Dependencies and the Universal Instance	1983	PODS	6.8901775e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,406	Solving Implication Problems in Database Applications	1989	SIGMOD
2	209	Dependency Inference	1987	VLDB
3	4,582	Reasoning about Nested Functional Dependencies	1999	PODS
4	3,598	Functional Dependencies on Cyclic Database Schemes	1983	SIGMOD
5	4,753	On The Complexity And Axiomatizability Of Consistent Database States	1984	PODS
6	3,356	The Implication And Finite Implication Problems For Typed Template Dependencies	1982	PODS
7	1,291	Extending Dependencies with Conditions	2007	VLDB
8	3,026	Functional Dependencies for Graphs	2016	SIGMOD
9	3,529	Inference Rules for Functional and Inclusion Dependencies	1983	PODS
10	159	Inclusion dependencies and their interaction with functional dependencies (Extended abstract)	1982	PODS