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)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 8 of 8 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 494 | Data Exchange: Getting to the Core | 2003 | PODS | 0.00021805832 |
| 621 | Schema Mappings, Data Exchange, and Metadata Management | 2005 | PODS | 0.00019005115 |
| 2,786 | An Axiomatic Approach to Deciding Query Safety in Deductive Databases | 1988 | PODS | 8.1283801e-05 |
| 3,643 | The Complexity of Data Exchange | 2006 | PODS | 6.8862411e-05 |
| 5,195 | Equivalence of Queries Combining Set and Bag-Set Semantics | 2006 | PODS | 5.6366303e-05 |
| 10,376 | Entity/Relationship Graphs: Principled Design, Modeling, and Data Integrity Management of Graph Databases | 2025 | SIGMOD | 4.1945683e-05 |
| 12,831 | Making Object-Oriented Schemas More Expressive | 1994 | PODS | 4.1945683e-05 |
| 12,986 | Independent Database Schemes Under Functional And Inclusion Dependencies | 1987 | VLDB | 4.1945683e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 8 | Extending the Data Base Relational Model to Capture More Meaning | 1979 | SIGMOD | 0.0015385917 |
| 104 | Inclusion dependencies and their interaction with functional dependencies (Extended abstract) | 1982 | PODS | 0.00048766186 |
| 144 | Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract) | 1982 | PODS | 0.00041462501 |
| 863 | Towards a Sound View Integration Methodology | 1983 | PODS | 0.00015817182 |
| 3,361 | Functional Dependencies on Cyclic Database Schemes | 1983 | SIGMOD | 7.1735665e-05 |
| 3,877 | Inclusion Dependencies and the Universal Instance | 1983 | PODS | 6.6739427e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,703 | Discovering Graph Functional Dependencies | 2018 | SIGMOD | 4.9555163e-05 |
| 25 | Dependency Inference (Extended Abstract) | 1987 | VLDB | 0.00083101742 |
| 4,169 | Reasoning about Nested Functional Dependencies | 1999 | PODS | 6.3905263e-05 |
| 3,361 | Functional Dependencies on Cyclic Database Schemes | 1983 | SIGMOD | 7.1735665e-05 |
| 3,917 | On The Complexity And Axiomatizability Of Consistent Database States | 1984 | PODS | 6.6328189e-05 |
| 2,032 | The Implication And Finite Implication Problems For Typed Template Dependencies | 1982 | PODS | 9.7332616e-05 |
| 1,401 | Extending Dependencies with Conditions | 2007 | VLDB | 0.00012187775 |
| 2,450 | Functional Dependencies for Graphs | 2016 | SIGMOD | 8.7882979e-05 |
| 1,954 | Inference Rules for Functional and Inclusion Dependencies | 1983 | PODS | 9.9639379e-05 |
| 104 | Inclusion dependencies and their interaction with functional dependencies (Extended abstract) | 1982 | PODS | 0.00048766186 |