A polynomial time algorithm for testing implications of a join dependency and embodied functional dependencies

摘要

The problem of deciding whether a full join dependency (JD) ⋈ [R] and a set of functional dependencies (FDs) F imply an embedded join dependency (EJD) ⋈ [S] is known to be NP-complete. We show that the problem can be decided in polynomial time if S ⊆ R and F is embedded in R. Our work uses arguments based on an extension of complete intersection graphs rather than tableaus. This approach has facilitated our results and should prove useful for future research.