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 |
|---|---|---|---|---|
| 920 | The U. R. Strikes Back | 1982 | PODS | 0.00015338004 |
| 6,033 | Embedded Join Dependencies As A Tool For Decomposing Full Join Dependencies | 1985 | PODS | 5.2415551e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,188 | On Generating Near-Optimal Tableaux for Conditional Functional Dependencies | 2008 | VLDB | 0.00013441729 |
| 2,058 | Functional and Inclusion Dependencies: A Graph Theoretic Approach | 1984 | PODS | 9.6585264e-05 |
| 25 | Dependency Inference (Extended Abstract) | 1987 | VLDB | 0.00083101742 |
| 7,366 | Discovery Algorithms for Embedded Functional Dependencies | 2020 | SIGMOD | 4.7515248e-05 |
| 5,553 | On the Complexity of Join Predicates | 2001 | PODS | 5.439162e-05 |
| 6,949 | Tree-Width and Functional Dependencies in Databases | 2008 | PODS | 4.8898337e-05 |
| 6,603 | Properties Of Database Schemata With Functional Dependencies | 1984 | PODS | 4.9971153e-05 |
| 2,450 | Functional Dependencies for Graphs | 2016 | SIGMOD | 8.7882979e-05 |
| 144 | Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract) | 1982 | PODS | 0.00041462501 |
| 12,925 | Polynomial Time Designs toward Both BCNF and Efficient Data Manipulation | 1990 | SIGMOD | 4.1945683e-05 |