Semantics for null extended nested relations

ABSTRACT

The nested relational model extends the flat relational model by relaxing the first normal form assumption in order to allow the modeling of complex objects. Much of the previous work on the nested relational model has concentrated on defining the data structures and query language for the model. The work done on integrity constraints in nested relations has mainly focused on characterizing subclasses of nested relations and defining normal forms for nested relations with certain desirable properties. In this paper we define the semantics of nested relations, which may contain null values, in terms of integrity constraints, called null extended data dependencies, which extend functional dependencies and join dependencies encountered in flat relational database theory. We formalize incomplete information in nested relations by allowing only one unmarked generic null value, whose semantics we do not further specify. The motivation for the choice of a generic null is our desire to investigate only fundamental semantics which are common to all unmarked null types. This lead us to define a preorder on nested relations, which allows us to measure the relative information content of nested relations. We also define a procedure, called the extended chase procedure, for testing satisfaction of null extended data dependencies and for making inferences by using these null extended data dependencies. The extended chase procedure is shown to generalize the classical chase procedure, which is of major importance in flat relational database theory. As a consequence of our approach we are able to capture the novel notion of losslessness in nested relations, called herein null extended lossless decomposition. Finally, we show that the semantics of nested relations are a natural extension of the semantics of flat relations.

REFERENCES

• 1: Serge Abiteboul , Nicole Bidoit, Non first normal form relations: An algebra allowing data restructuring, Journal of Computer and System Sciences, v.33 n.3, p.361-393, Dec. 1986 [doi>10.1016/0022-0000(86)90058-9]
• 2: S. Abiteboul , P. C. Fischer , H. -J. Schek, Nested relations and complex objects in databases, Springer-Verlag New York, Inc., New York, NY, 1989
• 3: P. Atzeni , M. C. De Bernardis, A new basis for the weak instance model, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.79-86, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28667]
• 4: Paolo Atzeni , Nicola M Morfuni, Functional dependencies and constraints on Null values in database relations, Information and Control, v.70 n.1, p.1-31, July 1986 [doi>10.1016/S0019-9958(86)80022-5]
• 5: BEER~, C., AND VARDI, M. Y. On the properties of join dependencies. In Advances ~n Dalabase Theory, Vol. 1, H. Gallaire, J. Minker, and J. M. Nicholas, Eds., Plenum Press, New York, 1981, 25 72.
• 6: N. Bidoit, The Verso algebra or how to answer queries with fewer joins, Journal of Computer and System Sciences, v.35 n.3, p.321-364, Dec. 1987 [doi>10.1016/0022-0000(87)90019-5]
• 7: Peter Buneman , Achim Jung , Atsushi Ohori, Using powerdomains to generalize relational databases, Theoretical Computer Science, v.91 n.1, p.23-55, Dec. 9, 1991 [doi>10.1016/0304-3975(91)90266-5 ]
• 8: E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
• 9: E. F. Codd, Missing information (applicable and inapplicable) in relational databases, ACM SIGMOD Record, v.15 n.4, p.53-53, Dec. 1986 [doi>10.1145/16301.16303]
• 10: Latha S. Colby, A recursive algebra and query optimization for nested relations, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.273-283, June 1989, Portland, Oregon, United States
• 11: 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]
• 12: Ronald Fagin , Alberto O. Mendelzon , Jeffrey D. Ullman, A simplied universal relation assumption and its properties, ACM Transactions on Database Systems (TODS), v.7 n.3, p.343-360, Sept. 1982 [doi>10.1145/319732.319735]
• 13: Ronald Fagin, Degrees of acyclicity for hypergraphs and relational database schemes, Journal of the ACM (JACM), v.30 n.3, p.514-550, July 1983 [doi>10.1145/2402.322390]
• 14: P C Fischer , L V Saxton , S J Thomas , D Van Gucht, Interactions between dependencies and nested relational structures, Journal of Computer and System Sciences, v.31 n.3, p.343-354, December 1985 [doi>10.1016/0022-0000(85)90057-1]
• 15: Marc H. Graham , Alberto O. Mendelzon , Moshe Y. Vardi, Notions of dependency satisfaction, Journal of the ACM (JACM), v.33 n.1, p.105-129, Jan. 1986 [doi>10.1145/4904.4798]
• 16: GUREVICH, Y., AND SELAH, S. Fixed-point extensions of first-order logic. Ann. Pure Appl. Logic 32 (1986), 265-280.
• 17: Marc Gyssens , Dirk van Gucht, A uniform approach toward handling atomic and structured information in the nested relational database model, Journal of the ACM (JACM), v.36 n.4, p.790-825, Oct. 1989 [doi>10.1145/76359.76364]
• 18: HARARY, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.
• 19: Peter Honeyman, Testing satisfaction of functional dependencies, Journal of the ACM (JACM), v.29 n.3, p.668-677, July 1982 [doi>10.1145/322326.322330]
• 20: Tomasz Imieliński , Witold Lipski, Jr., Incomplete Information in Relational Databases, Journal of the ACM (JACM), v.31 n.4, p.761-791, Oct. 1984 [doi>10.1145/1634.1886]
• 21: G. Jaeschke , H. J. Schek, Remarks on the algebra of non first normal form relations, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588133]
• 22: S. Jajodia , F. N. Springsteel, Lossless outer joins with incomplete information, BIT, v.30 n.1, p.34-41, 1990 [doi>10.1007/BF01932129]
• 23: Phokion G. Kolaitis , Christos H. Papadimitriou, Why not negation by fixpoint?, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.231-239, March 1988, Austin, Texas, United States [doi>10.1145/308386.308446]
• 24: H. F. Korth, Optimization of object-retrieval queries, Lecture notes in computer science on Advances in object-oriented database systems, p.352-357, September 1988, Bad Mu:9Ainster am Stein-Edernburg, Germany
• 25: N Lerat , W Lipski, Jr., Nonapplicable nulls, Theoretical Computer Science, v.46 n.1, p.67-82, Oct. 1986
• 26: M. Levene , G. Loizou, Modelling incomplete information in complex objects, Proceedings of the seventh British national conference on Databases, p.241-259, February 1990, Heriot-Watt Univ., Englnad
• 27: Mark Levene , George Loizou, &ggr;-acyclic database schemes and nested relations, Nested relations and complex objects in databases, Springer-Verlag New York, Inc., New York, NY, 1989
• 28: M. Levene , G. Loizou, The nested relation type model: an application of domain theory to databases, The Computer Journal, v.33 n.1, p.19-30, Feb. 1990 [doi>10.1093/comjnl/33.1.19]
• 29: Mark Levene , George Loizou, A fully precise null extended nested relational algebra, Fundamenta Informaticae, v.19 n.3-4, p.303-342, Nov./Dec. 1993
• 30: LEVENE, M. The Nested Umversal Re{atwn Database Model. Lecture Notes in Computer Science vol 595. Springer-Verlag, Berhm 1992.
• 31: LISN, Y.E. Multivalued dependencies with null values in relational databases. In Proceedrags of 5th International Conference on Very Large Data Bases (Rio de Janeiro, 1979), 61-66.
• 32: 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]
• 33: Witold Lipski, Jr., On semantic issues connected with incomplete information databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.262-296, Sept. 1979 [doi>10.1145/320083.320088]
• 34: David Maier , Alberto O. Mendelzon , Yehoshua Sagiv, Testing implications of data dependencies, ACM Transactions on Database Systems (TODS), v.4 n.4, p.455-469, Dec. 1979 [doi>10.1145/320107.320115]
• 35: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 36: David Maier , Jeffrey D. Ullman , Moshe Y. Vardi, On the foundations of the universal relation model, ACM Transactions on Database Systems (TODS), v.9 n.2, p.283-308, June 1984 [doi>10.1145/329.318580]
• 37: MAKINOUCHI, A. A consideration on normal form of not-necessarily-normalized relation in the relational data model In Proceedings of 3rd Internatmnal Conference on Very Large Data Bases (Tokyo, 1977), 447-453.
• 38: Alberto O. Mendelzon, Database states and their tableaux, ACM Transactions on Database Systems (TODS), v.9 n.2, p.264-282, June 1984 [doi>10.1145/329.318579]
• 39: Leslie L. Miller , S. K. Gadia , S. Kothari , K. C. Liu, Completeness issues for join dependencies derived from the universal relation join dependency, Information Processing Letters, v.28 n.5, p.269-274, Aug. 12, 1988 [doi>10.1016/0020-0190(88)90202-5 ]
• 40: MIURA, T., MORIYA, K., AND ARISAWA, H. Normalizing non first normal form relations. In Proceedings of 6th Advanced Database Symposium (Tokyo, Aug. 1986), Information Processing Society of Japan, 65-71.
• 41: Z. Meral Ozsoyoglu , Li-Yan Yuan, A new normal form for nested relations, ACM Transactions on Database Systems (TODS), v.12 n.1, p.111-136, March 1987 [doi>10.1145/12047.13676]
• 42: Z. Meral Ozsoyoglu , Li-Yan Yuan, On the normalization in nested relational databases, Nested relations and complex objects in databases, Springer-Verlag New York, Inc., New York, NY, 1989
• 43: Mark A. Roth , Herry F. Korth , Abraham Silberschatz, Extended algebra and calculus for nested relational databases, ACM Transactions on Database Systems (TODS), v.13 n.4, p.389-417, Dec. 1988 [doi>10.1145/49346.49347]
• 44: M. A. Roth , H. F. Korth , A. Silberschatz, Null values in nested relational databases, Acta Informatica, v.26 n.7, p.615-642, Sep. 1989 [doi>10.1007/BF00288974]
• 45: Yehoshua Sagiv, A characterization of globally consistent databases and their correct access paths, ACM Transactions on Database Systems (TODS), v.8 n.2, p.266-286, June 1983 [doi>10.1145/319983.319988]
• 46: Yehoshua Sagiv, On bounded database schemes and bounded Horn-clause programs, SIAM Journal on Computing, v.17 n.1, p.1-12, Feb. 1988 [doi>10.1137/0217001]
• 47: H J Schek , M H Scholl, The relational model with relation-valued attributes, Information Systems, v.11 n.2, p.137-147, 1986 [doi>10.1016/0306-4379(86)90003-7]
• 48: David A. Schmidt, Denotational semantics: a methodology for language development, William C. Brown Publishers, Dubuque, IA, 1986
• 49: Edward Sciore, A Complete Axiomatization of Full Join Dependencies, Journal of the ACM (JACM), v.29 n.2, p.373-393, April 1982 [doi>10.1145/322307.322313]
• 50: Jacob Stein , David Maier, Relaxing the universal relation scheme assumption, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.76-84, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325415]
• 51: Koichi Takeda, On the uniqueness of nested relations, Nested relations and complex objects in databases, Springer-Verlag New York, Inc., New York, NY, 1989
• 52: rpHOMAS, 8. J., AND FISCHER, P.C. Nested relational structures. In Advances ~n Computl, ng 269-307.
• 53: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 54: Dirk van Gucht , Patrick C. Fischer, Multilevel nested relational structures, Journal of Computer and System Sciences, v.36 n.1, p.77-105, February 1988 [doi>10.1016/0022-0000(88)90021-9]
• 55: ZANIOLO, C. Database relations with null values. J. Comput. Syst. Scz. 28, i (Feb. 1984), 142-166.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Normal forms
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Algorithms, Languages, Theory

Keywords:
extended chase, nested relations, null extended algebra, null extended data dependencies, nulls