Abstract | ||
---|---|---|
Database schemes with functional dependencies are considered. The satisfying states of these schemes are those having representative instances that satisfy all the xfunctional dependencies. All states are assumed to be finite. A database scheme is fdacyclic if all its pairwise consistent satisfying states are also join consistent. If the relation schemes of a database scheme are closed under the functional dependencies, then the database scheme is fd-acyclic if and only if it is acyclic (i.e., its corresponding hypergraph is acyclic). If a cover of the functional dependencies is embedded in the database scheme, then fd-acyclicity can be tested in polynomial time. |
Year | DOI | Venue |
---|---|---|
1986 | 10.1145/6012.15422 | PODS |
Keywords | Field | DocType |
polynomial time,satisfiability,functional dependency | Alternating polynomial,Discrete mathematics,Computer science,Square-free polynomial,Degree of a polynomial,Monic polynomial,Matrix polynomial | Conference |
Citations | PageRank | References |
14 | 25.44 | 14 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yehoshua Sagivt | 1 | 59 | 53.02 |
Oded Shmueli | 2 | 1670 | 785.41 |