Title
On Finite FD-Acyclicity
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 Sagivt15953.02
Oded Shmueli21670785.41