Logical design of relational database schemes

ABSTRACT

We define extended conflict free dependencies in the context of functional and multivalued dependencies, and prove that there exists an acyclic, dependency preserving, 4NF database scheme if and only if the given set of dependencies has an extended conflict free cover. This condition can be checked in polynomial time. A polynomial time algorithm to obtain such a scheme for a given extended conflict free set of dependencies is also presented. The result is also applicable when the data dependencies consists of only functional dependencies, giving the necessary and sufficient condition for an acyclic, dependency preserving BCNF database scheme

REFERENCES

• BB: Catriel Beeri , Philip A. Bernstein, Computational problems related to the design of normal form relational schemas, ACM Transactions on Database Systems (TODS), v.4 n.1, p.30-59, March 1979 [doi>10.1145/320064.320066]
• Be: Bemstem, P A, Synthestzmg 3NF Rela- Uons From Funcuonal Dependem ~es, ACM TODS, Dec 1976, pp 247-298
• BFMY: Catriel Beeri , Ronald Fagin , David Maier , Mihalis Yannakakis, On the Desirability of Acyclic Database Schemes, Journal of the ACM (JACM), v.30 n.3, p.479-513, July 1983 [doi>10.1145/2402.322389]
• BK: Catriel Beeri , Michael Kifer, An integrated approach to logical design of relational database schemes, ACM Transactions on Database Systems (TODS), v.11 n.2, p.134-158, June 1986 [doi>10.1145/5922.214291]
• Fa: Ronald Fagin, Multivalued dependencies and a new normal form for relational databases, ACM Transactions on Database Systems (TODS), v.2 n.3, p.262-278, Sept. 1977 [doi>10.1145/320557.320571]
• Ga: Zvi Galil, An Almost Linear-Time Algorithm for Computing a Dependency Basis in a Relational Database, Journal of the ACM (JACM), v.29 n.1, p.96-102, Jan. 1982 [doi>10.1145/322290.322296]
• GR: Gösta Grahne , Kari-Jouko Räihä, Database Decomposition into Fourth Normal Form, Proceedings of the 9th International Conference on Very Large Data Bases, p.186-196, October 31-November 02, 1983
• Ka: Hirofumi Katsuno, An extension of conflict-free multivalued dependency sets, ACM Transactions on Database Systems (TODS), v.9 n.2, p.309-326, June 1984 [doi>10.1145/329.354]
• L1: Y. Edmund Lien, Hierarchical schemata for relational databases, ACM Transactions on Database Systems (TODS), v.6 n.1, p.48-69, March 1981 [doi>10.1145/319540.319546]
• L2: Y. Edmund Lien, On the Equivalence of Database Models, Journal of the ACM (JACM), v.29 n.2, p.333-362, April 1982 [doi>10.1145/322307.322311]
• OY1: Ozsoyoglu, Z.M and Yuan, L Y, Reduced MVDs and M=mmum Covers, Technical Report CES-84-06, Computer Engmeenng Dept., CWRU, (to appear m ACM-TODS)
• OY2: Z. Meral Özsoyoglu , Li-Yan Yuan, A normal form for nested relations, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.251-260, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325451]
• Ul: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• YO1: Meral Ozsoyoglu , Li Yan Yuan, Unifying functional and multivalued dependencies for relational database design, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.183-190, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15414]
• YO2: Yuan, L.Y, and Ozsoyoglu, Z M, lnteracttons between FDs and MVDs, and the Design of RelaUonal Database Schemes, Techmcal Report, Oct, 1986, Computer and Engineering Dept, CWRU

INDEX TERMS

Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema

General Terms:
Algorithms, Design, Management, Theory, Verification