ACM SIGMOD Anthology TODS dblp.uni-trier.de

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)
@article{DBLP:journals/tods/LeveneL93,
  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        = {http://doi.acm.org/10.1145/155271.155275, db/journals/tods/LeveneL93.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

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.

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]

References

[1]
Serge Abiteboul, Nicole Bidoit: Non First Normal Form Relations: An Algebra Allowing Data Restructuring. J. Comput. Syst. Sci. 33(3): 361-393(1986) BibTeX
[2]
...
[3]
Paolo Atzeni, Maria Cristina De Bernardis: A New Basis for the Weak Instance Model. PODS 1987: 79-86 BibTeX
[4]
Paolo Atzeni, Nicola M. Morfuni: Functional Dependencies and Constraints on Null Values in Database Relations. Information and Control 70(1): 1-31(1986) BibTeX
[5]
Catriel Beeri, Moshe Y. Vardi: On the Properties of Join Dependencies. Advances in Data Base Theory 1979: 25-71 BibTeX
[6]
Nicole Bidoit: The Verso Algebra or How to Answer Queries with Fewer Joins. J. Comput. Syst. Sci. 35(3): 321-364(1987) BibTeX
[7]
Peter Buneman, Achim Jung, Atsushi Ohori: Using Powerdomains to Generalize Relational Databases. Theor. Comput. Sci. 91(1): 23-55(1991) BibTeX
[8]
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
[9]
E. F. Codd: Missing Information (Applicable and Inapplicable) in Relational Databases. SIGMOD Record 15(4): 53-78(1986) BibTeX
[10]
Latha S. Colby: A Recursive Algebra and Query Optimization for Nested Relations. SIGMOD Conference 1989: 273-283 BibTeX
[11]
Claude Delobel: Normalization and Hierarchical Dependencies in the Relational Data Model. ACM Trans. Database Syst. 3(3): 201-222(1978) BibTeX
[12]
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
[13]
Ronald Fagin: Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. J. ACM 30(3): 514-550(1983) BibTeX
[14]
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
[15]
Marc H. Graham, Alberto O. Mendelzon, Moshe Y. Vardi: Notions of dependency satisfaction. J. ACM 33(1): 105-129(1986) BibTeX
[16]
...
[17]
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
[18]
...
[19]
Peter Honeyman: Testing satisfaction of functional dependencies. J. ACM 29(3): 668-677(1982) BibTeX
[20]
Tomasz Imielinski, Witold Lipski Jr.: Incomplete Information in Relational Databases. J. ACM 31(4): 761-791(1984) BibTeX
[21]
Gerhard Jaeschke, Hans-Jörg Schek: Remarks on the Algebra of Non First Normal Form Relations. PODS 1982: 124-138 BibTeX
[22]
Sushil Jajodia, Frederick N. Springsteel: Lossless Outer Joins with Incomplete Information. BIT 30(1): 34-41(1990) BibTeX
[23]
Phokion G. Kolaitis, Christos H. Papadimitriou: Why Not Negation by Fixpoint? PODS 1988: 231-239 BibTeX
[24]
Henry F. Korth: Optimization of Object-Retrieval Queries. OODBS 1988: 352-357 BibTeX
[25]
Nadine Lerat, Witold Lipski Jr.: Nonapplicable Nulls. Theor. Comput. Sci. 46(3): 67-82(1986) BibTeX
[26]
...
[27]
Mark Levene, George Loizou: Gamma-Acyclic Database Schemes and Nested Relations. NF² 1987: 313-323 BibTeX
[28]
Mark Levene, George Loizou: The Nested Relation Type Model: An Application of Domain Theory to Databases. Comput. J. 33(1): 19-30(1990) BibTeX
[29]
Mark Levene, George Loizou: A Fully Precise Null Extended Nested Relational Algebra. Fundam. Inform. 19(3/4): 303-342(1993) BibTeX
[30]
...
[31]
Y. Edmund Lien: Multivalued Dependencies with Null Values in Relational Data Bases. VLDB 1979: 61-66 BibTeX
[32]
Y. Edmund Lien: On the Equivalence of Database Models. J. ACM 29(2): 333-362(1982) BibTeX
[33]
Witold Lipski Jr.: On Semantic Issues Connected with Incomplete Information Databases. ACM Trans. Database Syst. 4(3): 262-296(1979) BibTeX
[34]
David Maier, Alberto O. Mendelzon, Yehoshua Sagiv: Testing Implications of Data Dependencies. ACM Trans. Database Syst. 4(4): 455-469(1979) BibTeX
[35]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX
[36]
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
[37]
Akifumi Makinouchi: A Consideration on Normal Form of Not-Necessarily-Normalized Relation in the Relational Data Model. VLDB 1977: 447-453 BibTeX
[38]
Alberto O. Mendelzon: Database States and Their Tableaux. ACM Trans. Database Syst. 9(2): 264-282(1984) BibTeX
[39]
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
[40]
...
[41]
Z. Meral Özsoyoglu, Li-Yan Yuan: A New Normal Form for Nested Relations. ACM Trans. Database Syst. 12(1): 111-136(1987) BibTeX
[42]
Z. Meral Özsoyoglu, Li-Yan Yuan: On the Normalization in Nested Relational Databases. NF² 1987: 243-271 BibTeX
[43]
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
[44]
Mark A. Roth, Henry F. Korth, Abraham Silberschatz: Null Values in Nested Relational Databases. Acta Inf. 26(7): 615-642(1989) BibTeX
[45]
Yehoshua Sagiv: A Characterization of Globally Consistent Databases and Their Correct Access Paths. ACM Trans. Database Syst. 8(2): 266-286(1983) BibTeX
[46]
Yehoshua Sagiv: On Bounded Database Schemes and Bounded Horn-Clause Programs. SIAM J. Comput. 17(1): 1-22(1988) BibTeX
[47]
Hans-Jörg Schek, Marc H. Scholl: The relational model with relation-valued attributes. Inf. Syst. 11(2): 137-147(1986) BibTeX
[48]
...
[49]
Edward Sciore: A Complete Axiomatization of Full Join Dependencies. J. ACM 29(2): 373-393(1982) BibTeX
[50]
Jacob Stein, David Maier: Relaxing the Universal Relation Scheme Assumption. PODS 1985: 76-84 BibTeX
[51]
Koichi Takeda: On the Uniqueness of Nested Relations. NF² 1987: 139-150 BibTeX
[52]
Stan J. Thomas, Patrick C. Fischer: Nested Relational Structures. Advances in Computing Research 3: 269-307(1986) BibTeX
[53]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[54]
Dirk Van Gucht, Patrick C. Fischer: Multilevel Nested Relational Structures. J. Comput. Syst. Sci. 36(1): 77-105(1988) BibTeX
[55]
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
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:15 2008