Semantics for Null Extended Nested Relations.

Mark Levene, George Loizou: Semantics for Null Extended Nested Relations. ACM Trans. Database Syst. 18(3): 414-459(1993)
  author    = {Mark Levene and
               George Loizou},
  title     = {Semantics for Null Extended Nested Relations},
  journal   = {ACM Trans. Database Syst.},
  volume    = {18},
  number    = {3},
  year      = {1993},
  pages     = {414-459},
  ee        = {, db/journals/tods/LeveneL93.html},
  bibsource = {DBLP,}


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.

Copyright © 1993 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 2, TODS 1991-1995, TKDE 1989-1992" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract, Index Terms and Review]
[Full Text in PDF Format, 2708 KB]


Serge Abiteboul, Nicole Bidoit: Non First Normal Form Relations: An Algebra Allowing Data Restructuring. J. Comput. Syst. Sci. 33(3): 361-393(1986) BibTeX
Paolo Atzeni, Maria Cristina De Bernardis: A New Basis for the Weak Instance Model. PODS 1987: 79-86 BibTeX
Paolo Atzeni, Nicola M. Morfuni: Functional Dependencies and Constraints on Null Values in Database Relations. Information and Control 70(1): 1-31(1986) BibTeX
Catriel Beeri, Moshe Y. Vardi: On the Properties of Join Dependencies. Advances in Data Base Theory 1979: 25-71 BibTeX
Nicole Bidoit: The Verso Algebra or How to Answer Queries with Fewer Joins. J. Comput. Syst. Sci. 35(3): 321-364(1987) BibTeX
Peter Buneman, Achim Jung, Atsushi Ohori: Using Powerdomains to Generalize Relational Databases. Theor. Comput. Sci. 91(1): 23-55(1991) BibTeX
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
E. F. Codd: Missing Information (Applicable and Inapplicable) in Relational Databases. SIGMOD Record 15(4): 53-78(1986) BibTeX
Latha S. Colby: A Recursive Algebra and Query Optimization for Nested Relations. SIGMOD Conference 1989: 273-283 BibTeX
Claude Delobel: Normalization and Hierarchical Dependencies in the Relational Data Model. ACM Trans. Database Syst. 3(3): 201-222(1978) BibTeX
Ronald Fagin, Alberto O. Mendelzon, Jeffrey D. Ullman: A Simplified Universal Relation Assumption and Its Properties. ACM Trans. Database Syst. 7(3): 343-360(1982) BibTeX
Ronald Fagin: Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. J. ACM 30(3): 514-550(1983) BibTeX
Patrick C. Fischer, Lawrence V. Saxton, Stan J. Thomas, Dirk Van Gucht: Interactions between Dependencies and Nested Relational Structures. J. Comput. Syst. Sci. 31(3): 343-354(1985) BibTeX
Marc H. Graham, Alberto O. Mendelzon, Moshe Y. Vardi: Notions of dependency satisfaction. J. ACM 33(1): 105-129(1986) BibTeX
Marc Gyssens, Jan Paredaens, Dirk Van Gucht: A uniform approach toward handling atomic and structured information in the nested relational database model. J. ACM 36(4): 790-825(1989) BibTeX
Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982) BibTeX
Tomasz Imielinski, Witold Lipski Jr.: Incomplete Information in Relational Databases. J. ACM 31(4): 761-791(1984) BibTeX
Gerhard Jaeschke, Hans-Jörg Schek: Remarks on the Algebra of Non First Normal Form Relations. PODS 1982: 124-138 BibTeX
Sushil Jajodia, Frederick N. Springsteel: Lossless Outer Joins with Incomplete Information. BIT 30(1): 34-41(1990) BibTeX
Phokion G. Kolaitis, Christos H. Papadimitriou: Why Not Negation by Fixpoint? PODS 1988: 231-239 BibTeX
Henry F. Korth: Optimization of Object-Retrieval Queries. OODBS 1988: 352-357 BibTeX
Nadine Lerat, Witold Lipski Jr.: Nonapplicable Nulls. Theor. Comput. Sci. 46(3): 67-82(1986) BibTeX
Mark Levene, George Loizou: Gamma-Acyclic Database Schemes and Nested Relations. NF² 1987: 313-323 BibTeX
Mark Levene, George Loizou: The Nested Relation Type Model: An Application of Domain Theory to Databases. Comput. J. 33(1): 19-30(1990) BibTeX
Mark Levene, George Loizou: A Fully Precise Null Extended Nested Relational Algebra. Fundam. Inform. 19(3/4): 303-342(1993) BibTeX
Y. Edmund Lien: Multivalued Dependencies with Null Values in Relational Data Bases. VLDB 1979: 61-66 BibTeX
Y. Edmund Lien: On the Equivalence of Database Models. J. ACM 29(2): 333-362(1982) BibTeX
Witold Lipski Jr.: On Semantic Issues Connected with Incomplete Information Databases. ACM Trans. Database Syst. 4(3): 262-296(1979) BibTeX
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
David Maier, Jeffrey D. Ullman, Moshe Y. Vardi: On the Foundations of the Universal Relation Model. ACM Trans. Database Syst. 9(2): 283-308(1984) BibTeX
Akifumi Makinouchi: A Consideration on Normal Form of Not-Necessarily-Normalized Relation in the Relational Data Model. VLDB 1977: 447-453 BibTeX
Alberto O. Mendelzon: Database States and Their Tableaux. ACM Trans. Database Syst. 9(2): 264-282(1984) BibTeX
Leslie L. Miller, Shashi K. Gadia, Suresh C. Kothari, K. C. Liu: Completeness Issues for Join Dependencies Derived from the Universal Relation Join Dependency. Inf. Process. Lett. 28(5): 269-274(1988) BibTeX
Z. Meral Özsoyoglu, Li-Yan Yuan: A New Normal Form for Nested Relations. ACM Trans. Database Syst. 12(1): 111-136(1987) BibTeX
Z. Meral Özsoyoglu, Li-Yan Yuan: On the Normalization in Nested Relational Databases. NF² 1987: 243-271 BibTeX
Mark A. Roth, Henry F. Korth, Abraham Silberschatz: Extended Algebra and Calculus for Nested Relational Databases. ACM Trans. Database Syst. 13(4): 389-417(1988) BibTeX
Mark A. Roth, Henry F. Korth, Abraham Silberschatz: Null Values in Nested Relational Databases. Acta Inf. 26(7): 615-642(1989) BibTeX
Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983) BibTeX
Yehoshua Sagiv: On Bounded Database Schemes and Bounded Horn-Clause Programs. SIAM J. Comput. 17(1): 1-22(1988) BibTeX
Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986) BibTeX
Edward Sciore: A Complete Axiomatization of Full Join Dependencies. J. ACM 29(2): 373-393(1982) BibTeX
Jacob Stein, David Maier: Relaxing the Universal Relation Scheme Assumption. PODS 1985: 76-84 BibTeX
Koichi Takeda: On the Uniqueness of Nested Relations. NF² 1987: 139-150 BibTeX
Stan J. Thomas, Patrick C. Fischer: Nested Relational Structures. Advances in Computing Research 3: 269-307(1986) BibTeX
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
Dirk Van Gucht, Patrick C. Fischer: Multilevel Nested Relational Structures. J. Comput. Syst. Sci. 36(1): 77-105(1988) BibTeX
Carlo Zaniolo: Database Relations with Null Values. J. Comput. Syst. Sci. 28(1): 142-166(1984) BibTeX

Referenced by

  1. Mengchi Liu: Partial and Complete Tuples and Sets in Deductive Databases. ADBIS (Short Papers) 1999: 200-206
  2. Jui-Shang Chiu, Arbee L. P. Chen: An Exploration of Relationships Among Exclusive Disjunctive Data. IEEE Trans. Knowl. Data Eng. 7(6): 928-940(1995)
  3. George Loizou, Philippos Pouyioutas: A Query Algebra for an Extended Object-Oriented Database Model. DASFAA 1991: 89-98
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:39:15 2008