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: 680
Venue: PODS
Year: 1984
Pagerank: 9.2564254e-05
Overall Rank: 2,047 | 85.96%
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
377	Data Exchange: Getting to the Core	2003	PODS	0.00019643793
506	Schema Mappings, Data Exchange, and Metadata Management	2005	PODS	0.0001728171
3,025	An Axiomatic Approach to Deciding Query Safety in Deductive Databases	1988	PODS	7.8386928e-05
3,485	The Complexity of Data Exchange	2006	PODS	7.3703451e-05
5,062	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS	6.3799383e-05
10,665	Entity/Relationship Graphs: Principled Design, Modeling, and Data Integrity Management of Graph Databases	2025	SIGMOD	5.093636e-05
13,025	Making Object-Oriented Schemas More Expressive	1994	PODS	5.093636e-05
13,184	Independent Database Schemes Under Functional and Inclusion Dependencies	1987	VLDB	5.093636e-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.0007727299
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
1,180	Towards a Sound View Integration Methodology	1983	PODS	0.00011798223
3,527	Functional Dependencies on Cyclic Database Schemes	1983	SIGMOD	7.3428228e-05
3,884	Inclusion Dependencies and the Universal Instance	1983	PODS	7.0480285e-05

Semantically Similar Papers

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