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 |
|---|---|---|---|---|
| 493 | Data Exchange: Getting to the Core | 2003 | PODS | 0.00021782199 |
| 620 | Schema Mappings, Data Exchange, and Metadata Management | 2005 | PODS | 0.00018983367 |
| 2,790 | An Axiomatic Approach to Deciding Query Safety in Deductive Databases | 1988 | PODS | 8.1203289e-05 |
| 3,647 | The Complexity of Data Exchange | 2006 | PODS | 6.8796285e-05 |
| 5,196 | Equivalence of Queries Combining Set and Bag-Set Semantics | 2006 | PODS | 5.6311982e-05 |
| 10,388 | Entity/Relationship Graphs: Principled Design, Modeling, and Data Integrity Management of Graph Databases | 2025 | SIGMOD | 4.1905499e-05 |
| 12,840 | Making Object-Oriented Schemas More Expressive | 1994 | PODS | 4.1905499e-05 |
| 12,997 | Independent Database Schemes Under Functional And Inclusion Dependencies | 1987 | VLDB | 4.1905499e-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 |
|---|---|---|---|---|
| 7 | Extending the Data Base Relational Model to Capture More Meaning | 1979 | SIGMOD | 0.0015464728 |
| 105 | Inclusion dependencies and their interaction with functional dependencies (Extended abstract) | 1982 | PODS | 0.00049082041 |
| 142 | Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract) | 1982 | PODS | 0.00041780711 |
| 861 | Towards a Sound View Integration Methodology | 1983 | PODS | 0.00015801354 |
| 3,367 | Functional Dependencies on Cyclic Database Schemes | 1983 | SIGMOD | 7.1665323e-05 |
| 3,877 | Inclusion Dependencies and the Universal Instance | 1983 | PODS | 6.6673599e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,074 | Solving Implication Problems in Database Applications | 1989 | SIGMOD | 5.2211593e-05 |
| 25 | Dependency Inference (Extended Abstract) | 1987 | VLDB | 0.00083070519 |
| 4,166 | Reasoning about Nested Functional Dependencies | 1999 | PODS | 6.3843679e-05 |
| 3,367 | Functional Dependencies on Cyclic Database Schemes | 1983 | SIGMOD | 7.1665323e-05 |
| 3,931 | On The Complexity And Axiomatizability Of Consistent Database States | 1984 | PODS | 6.6192327e-05 |
| 2,034 | The Implication And Finite Implication Problems For Typed Template Dependencies | 1982 | PODS | 9.7234933e-05 |
| 1,405 | Extending Dependencies with Conditions | 2007 | VLDB | 0.00012174499 |
| 3,478 | Functional Dependencies for Graphs | 2016 | SIGMOD | 7.0554625e-05 |
| 1,960 | Inference Rules for Functional and Inclusion Dependencies | 1983 | PODS | 9.9543811e-05 |
| 105 | Inclusion dependencies and their interaction with functional dependencies (Extended abstract) | 1982 | PODS | 0.00049082041 |