Hierarchical schemata for relational databases

ABSTRACT

Most database design methods for the relational model produce a flat database, that is, a family of relations with no explicit interrelational connections. The user of a flat database is likely to be unaware of certain interrelational semantics. In contrast, the entity-relationship model provides schema graphs as a description of the database, as well as for navigating the database. Nevertheless, the user of an entity-relationship database may still commit semantic errors, such as performing a lossy join. This paper proposes a nonflat, or hierarchical, view of relational databases. Relations are grouped together to form relation hierarchies in which lossless joins are explicitly shown whereas lossy joins are excluded. Relation hierarchies resemble the schema graphs in the entity-relationship model. An approach to the design of relation hierarchies is outlined in the context of data dependencies and relational decomposition. The approach consists of two steps; each is described as an algorithm. Algorithm DEC decomposes a given universal relation according to a given set of data dependencies and produces a set of nondecomposable relation schemes. This algorithm differs from its predecessors in that it produces no redundant relation schemes. Algorithm RH further structures the relation schemes produced by Algorithm DEC into a hierarchical schema. These algorithms can be useful software tools for database designers.

REFERENCES

• 1: A. V. Aho , C. Beeri , J. D. Ullman, The theory of joins in relational databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.297-314, Sept. 1979 [doi>10.1145/320083.320091]
• 2: BEEm, C. On the membership problem for multivalued dependencies in relational database systems. Tech. Rep. 229, Dep. Electrical Engineering and Computer Science, Princeton Univ., Princeton, N.J., Sept. 1977.
• 3: BEERI, C., BERNSTEIN, P.A., AND GOODMAN, N. A sophisticate's introduction to database normalization theory. Proc. 4th Int. Conf. Very Large Data Bases, West Berlin, Germany, Sept. 1978, pp. 113-124.
• 4: Catriel Beeri , Ronald Fagin , John H. Howard, A complete axiomatization for functional and multivalued dependencies in database relations, Proceedings of the 1977 ACM SIGMOD international conference on Management of data, August 03-05, 1977, Toronto, Ontario, Canada [doi>10.1145/509404.509414]
• 5: Philip A. Bernstein, Synthesizing third normal form relations from functional dependencies, ACM Transactions on Database Systems (TODS), v.1 n.4, p.277-298, Dec. 1976 [doi>10.1145/320493.320489]
• 6: Peter Pin-Shan Chen, The entity-relationship model—toward a unified view of data, ACM Transactions on Database Systems (TODS), v.1 n.1, p.9-36, March 1976 [doi>10.1145/320434.320440]
• 7: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 8: CODD, E.F. Further normalization of the database relational model. In Data Base Systems, Courant Computer Science Symposium 6. Prentice-Hall, Englewood Cliffs, N.J., 1972, pp. 33-64.
• 9: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 10: Claude Delobel, Normalization and hierarchical dependencies in the relational data model, ACM Transactions on Database Systems (TODS), v.3 n.3, p.201-222, Sept. 1978 [doi>10.1145/320263.320271]
• 11: 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]
• 12: FAGIN, R. The decomposition versus the synthetic approach to relational data base design. Proc. 3rd int. Conf. Very Large Data Bases, Tokyo, Japan, Oct. 1977, pp. 441-446.
• 13: LIEN, Y.E. Multivalued dependencies with null values in relational data bases. Proc. 5th Int. Conf. Very Large Data Bases, Rio de Janeiro, Brazil, Oct. 1979, pp. 61-66.
• 14: Alberto O. Mendelzon, On Axiomatizing Multivalued Dependencies in Relational Databases, Journal of the ACM (JACM), v.26 n.1, p.37-44, Jan. 1979 [doi>10.1145/322108.322112]
• 15: RISSANEN, J. Theory of relations for databases--A tutorial survey. Proc. Syrup. Mathematical Foundations of Computer Science, 1978, Zakopane, Poland, Lecture Notes for Computer Science, vol. 64, Springer-Verlag, pp. 536-551.
• 16: SAGIV, Y. An algorithm for inferring multivalued dependencies with an application to propositional logic. Tech. Rep., Dep. Computer Science, Univ. Illinois at Urbana-Champaign, Urbana, Ill, 1979.
• 17: YANG, J.N. A query language and data base management for relational model. Ph.D. Dissertation, Univ. California, Berkeley, Sept. 1974.
• 18: Carlo Antonio Zaniolo, Analysis and design of relational schemata for database systems., 1976

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

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

General Terms:
Algorithms, Design

Keywords:
database design, lossless join, multivalued dependency, relation normalization