The Experts below are selected from a list of 36 Experts worldwide ranked by ideXlab platform
George Loizou - One of the best experts on this subject based on the ideXlab platform.
-
Database design for incomplete relations
ACM Transactions on Database Systems, 1999Co-Authors: Mark Levene, George LoizouAbstract:Although there has been a vast amount of research in the area ofrelational database design, to our knowledge, there has been very little work that considers whether this theory is still valid when relations in the database may be incomplete. When relations are incomplete and thus contain null values the problem of whether satisfaction is additive arises. Additivity is the property of the equivalence of the satisfaction of a set of functional dependencies (FDs) F with the individual satisfaction of each member of F in an incomplete relation. It is well known that in general, satisfaction of FDs is not additive. Previously we have shown that satisfaction is additive if and only if the set of FDs is monodependent. We conclude that monodependence is a fundamental desirable property of a set of FDs when considering incomplete information in relational database design. We show that, when the set of FDs F either satifies the intersection property or the split-freeness property, then the problem of finding an optimum cover of F can be solved in polynomial time in the size of F; in general, this problem is known to be NP-complete. We also show that when F satisfies the split-freeness property then deciding whether there is a Superkey of cardinality k or less can be solved in polynomial time in the size of F, since all the keys have the same cardinality. If F only satisfies the intersection property then this problem is NP-complete, as in the general case. Moreover, we show that when F either satisfies the intersection property or the split-freeness property then deciding whether an attribute is prime can be solved in polynomial time in the size of F; in general, this problem is known to be NP-complete. Assume that a relation schema R is an appropriate normal form with respect to a set of FDs F. We show that when F satisfies the intersection property then the notions of second normal form and third normal form are equivalent. We also show that when R is in Boyce-Codd Normal Form (BCNF), then F is monodependent if and only if either there is a unique key for R, or for all keys X for R, the cardinality of X is one less than the number of attributes associated with R. Finally, we tackle a long-standing problem in relational database theory by showing that when a set of FDs F over R satisfies the intersection property, it also satisfies the split-freeness property (i.e., is monodependent), if and only if every lossless join decomposition of R with respect to F is also dependecy preserving. As a corollary of this result we are able to show that when F satisfies the intersection property, it also satisfies the intersection property, it also satisfies the split-freeness property(i.e., is monodependent), if and only if every lossless join decomposition of R, which is in BCNF, is also dependency preserving. Our final result is that when F is monodependent, then there exists a unique optimum lossless join decomposition of R, which is in BCNF, and is also dependency preserving. Furthermore, this ultimate decomposition can be attained in polynomial time in the size of F.
-
Database design for incomplete relations
1999Co-Authors: Mark Levene, George LoizouAbstract:Although there has been a vast amount of research in the area of relational database design, to our knowledge, there has been very little work that considers whether this theory is still valid when relations in the database may be incomplete. When relations are incomplete and thus contain null values the problem of whether satisfaction is additive arises. Additivity is the property of the equivalence of the satisfaction of a set of functional dependencies (FDs) F with the individual satisfaction of each member of F in an incomplete relation. It is well known that, in general, satisfaction of FDs is not additive. Previously we have shown that satisfaction is additive if and only if the set of FDs is monodependent. We conclude that monodependence is a fundamental desirable property of a set of FDs when considering incomplete information in relational database design. We show that, when the set of FDs F either satisfies the intersection property or the split-freeness property, then the problem of finding an optimum cover of F can be solved in polynomial time in the size of F; in general, this problem is known to be NP-complete. We also show that when F satisfies the split-freeness property then deciding whether there is a Superkey of cardinality k or less can be solved in polynomial time in the size of F, since all the keys have the same cardinality. If
Mark Levene - One of the best experts on this subject based on the ideXlab platform.
-
Database design for incomplete relations
ACM Transactions on Database Systems, 1999Co-Authors: Mark Levene, George LoizouAbstract:Although there has been a vast amount of research in the area ofrelational database design, to our knowledge, there has been very little work that considers whether this theory is still valid when relations in the database may be incomplete. When relations are incomplete and thus contain null values the problem of whether satisfaction is additive arises. Additivity is the property of the equivalence of the satisfaction of a set of functional dependencies (FDs) F with the individual satisfaction of each member of F in an incomplete relation. It is well known that in general, satisfaction of FDs is not additive. Previously we have shown that satisfaction is additive if and only if the set of FDs is monodependent. We conclude that monodependence is a fundamental desirable property of a set of FDs when considering incomplete information in relational database design. We show that, when the set of FDs F either satifies the intersection property or the split-freeness property, then the problem of finding an optimum cover of F can be solved in polynomial time in the size of F; in general, this problem is known to be NP-complete. We also show that when F satisfies the split-freeness property then deciding whether there is a Superkey of cardinality k or less can be solved in polynomial time in the size of F, since all the keys have the same cardinality. If F only satisfies the intersection property then this problem is NP-complete, as in the general case. Moreover, we show that when F either satisfies the intersection property or the split-freeness property then deciding whether an attribute is prime can be solved in polynomial time in the size of F; in general, this problem is known to be NP-complete. Assume that a relation schema R is an appropriate normal form with respect to a set of FDs F. We show that when F satisfies the intersection property then the notions of second normal form and third normal form are equivalent. We also show that when R is in Boyce-Codd Normal Form (BCNF), then F is monodependent if and only if either there is a unique key for R, or for all keys X for R, the cardinality of X is one less than the number of attributes associated with R. Finally, we tackle a long-standing problem in relational database theory by showing that when a set of FDs F over R satisfies the intersection property, it also satisfies the split-freeness property (i.e., is monodependent), if and only if every lossless join decomposition of R with respect to F is also dependecy preserving. As a corollary of this result we are able to show that when F satisfies the intersection property, it also satisfies the intersection property, it also satisfies the split-freeness property(i.e., is monodependent), if and only if every lossless join decomposition of R, which is in BCNF, is also dependency preserving. Our final result is that when F is monodependent, then there exists a unique optimum lossless join decomposition of R, which is in BCNF, and is also dependency preserving. Furthermore, this ultimate decomposition can be attained in polynomial time in the size of F.
-
Database design for incomplete relations
1999Co-Authors: Mark Levene, George LoizouAbstract:Although there has been a vast amount of research in the area of relational database design, to our knowledge, there has been very little work that considers whether this theory is still valid when relations in the database may be incomplete. When relations are incomplete and thus contain null values the problem of whether satisfaction is additive arises. Additivity is the property of the equivalence of the satisfaction of a set of functional dependencies (FDs) F with the individual satisfaction of each member of F in an incomplete relation. It is well known that, in general, satisfaction of FDs is not additive. Previously we have shown that satisfaction is additive if and only if the set of FDs is monodependent. We conclude that monodependence is a fundamental desirable property of a set of FDs when considering incomplete information in relational database design. We show that, when the set of FDs F either satisfies the intersection property or the split-freeness property, then the problem of finding an optimum cover of F can be solved in polynomial time in the size of F; in general, this problem is known to be NP-complete. We also show that when F satisfies the split-freeness property then deciding whether there is a Superkey of cardinality k or less can be solved in polynomial time in the size of F, since all the keys have the same cardinality. If
Ronald Fagin - One of the best experts on this subject based on the ideXlab platform.
-
A normal form for preventing . . .
2013Co-Authors: Hugh Darwen, C. J. Date, Ronald FaginAbstract:We introduce a new normal form, called essential tuple normal form (ETNF), for relations in a relational database where the constraints are given by functional dependencies and join dependencies. ETNF lies strictly between fourth normal form and fifth normal form (5NF, also known as projection-join normal form). We show that ETNF, although strictly weaker than 5NF, is exactly as effective as 5NF in eliminating redundancy of tuples. Our definition of ETNF is semantic, in that it is defined in terms of tuple redundancy. We give a syntactic characterization of ETNF, which says that a relation schema is in ETNF if and only if it is in Boyce-Codd normal form and some component of every explicitly declared join dependency of the schema is a Superkey
Yahiko Kambayashi - One of the best experts on this subject based on the ideXlab platform.
-
Super-Key Classes for Updating Materialized Derived Classes in Object Bases
Springer-Verlag, 1993Co-Authors: Tetsuya Furukawa Yahiko Kambayashi, Tetsuya Furukawa, Yahiko KambayashiAbstract:We describe data structures that allow efficient updates of materialized classes derived from relationship of classes in object bases. Materialization of derived classes reduces costs of retrievals and increases costs of updates. Costs of updates increase remarkably when several paths of objects derive the same object. If object bases satisfy the Superkey condition proposed in this paper, consistencies of object bases are maintained by local navigations and the remarkable increase of the costs is avoided. Any object base can be transformed to satisfy the Superkey condition by adding extra classes and their objects. In this manner, increasing redundancies allows efficient updates
Levene Mark - One of the best experts on this subject based on the ideXlab platform.
-
A lattice view of functional dependencies in incomplete relations
University of Szeged Institute of Informatics, 1995Co-Authors: Levene MarkAbstract:Functional Dependencies (or simply FDs) are by far the most common integrity constraint in the real world. When relations are incomplete and thus contain null values the problem of whether satisfaction is additive arises. Additivity is the property of the equivalence of the satisfaction of a set of functional dependencies (FDs), F, with the individual satisfaction of each member of F in an incomplete relation. It is well known that, in general, satisfaction of FDs is not additive. Previously we have shown that satisfaction is additive if and only if the set of FDs is monodependent. Thus monodependence of a set of FDs is a desirable property when relations may be incomplete. A set of FDs is monodependent if it satisfies both the intersection property and the split-freeness property. (The two defining properties of monodependent sets of FDs correspond to the two defining properties of conflict-free sets of multivalued data dependencies.) We investigate the properties of the lattice £(F) of closed sets of a monodependent set of FDs F over a relation schema R. We show an interesting connection between monodependent sets of FDs and exchange and antiexchange lattices. In addition, we give a characterisation of the intersection property in terms of the existence of certain distributive sublattices of £(F). Assume that a set of FDs F satisfies the intersection property. We show that the cardinality of the family .M(F) of meet-irreducible closed sets in £(F) is polynomial in the number of attributes associated with R; in general, this number is exponential. Thus an Armstrong relation for F having a polynomial number of tuples in the number of attributes associated with R can be generated. As a corollary we show that the prime attribute problem can be solved in polynomial time in the size of F; in general, the prime attribute problem is NP-complete. We also show that F satisfies the intersection property if and only if the cardinality of each element in A'i(F) is greater than or equal to the cardinality of the attribute set of R minus two. Using this result we are able to show that the Superkey of cardinality k problem is still NP-complete when F is restricted to satisfy the intersection property. Finally, we show that separatory sets of FDs are monodependent
