A Polynomial Time Algorithm for Testing Implications of a Join Dependency and Embodied Functional Dependencies
Summary: Polynomial-time algorithm for testing whether X[R] and F imply X[S], under S ⊆ R and F embedded in R. Uses extended complete intersection graphs instead of tableaus, offering a new graph-based toolkit for join-dependency reasoning in data schemas. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. J. Leuchner
- 2. L. Miller
- 3. G. Slutzki
Incoming Citations (Sorted by Pagerank)
Showing 0 of 0 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 2 of 2 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,087 | The U. R. Strikes Back | 1982 | PODS | 0.00012330493 |
| 6,867 | Embedded Join Dependencies As A Tool For Decomposing Full Join Dependencies | 1985 | PODS | 5.8190903e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,019 | On Generating Near-Optimal Tableaux for Conditional Functional Dependencies | 2008 | VLDB | 0.00012687756 |
| 2,045 | Functional and Inclusion Dependencies: A Graph Theoretic Approach | 1984 | PODS | 9.3352295e-05 |
| 201 | Dependency Inference (Extended Abstract) | 1987 | VLDB | 0.00025738022 |
| 7,078 | Discovery Algorithms for Embedded Functional Dependencies | 2020 | SIGMOD | 5.7626216e-05 |
| 7,454 | On the Complexity of Join Predicates | 2001 | PODS | 5.6765587e-05 |
| 7,237 | Tree-Width and Functional Dependencies in Databases | 2008 | PODS | 5.7193914e-05 |
| 6,590 | Properties Of Database Schemata With Functional Dependencies | 1984 | PODS | 5.8883652e-05 |
| 2,919 | Functional Dependencies for Graphs | 2016 | SIGMOD | 8.0276138e-05 |
| 145 | Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract) | 1982 | PODS | 0.00029697141 |
| 12,935 | Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation | 1990 | SIGMOD | 5.1725247e-05 |