dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

Access Path Support for Referential Integrity in SQL2.

Theo Härder, Joachim Reinert: Access Path Support for Referential Integrity in SQL2. VLDB J. 5(3): 196-214(1996)
@article{DBLP:journals/vldb/HarderR96,
  author    = {Theo H{\"a}rder and
               Joachim Reinert},
  title     = {Access Path Support for Referential Integrity in SQL2},
  journal   = {VLDB J.},
  volume    = {5},
  number    = {3},
  year      = {1996},
  pages     = {196-214},
  ee        = {db/journals/vldb/HarderR96.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The relational model of data incorporates fundamental assertions for entity integrity and referential integrity. Recently, these so-called relational invariants were more precisely specified by the new SQL2 standard. Accordingly, they have to be guaranteed by a relational DBMS to its users and, therefore, all issues of semantics and implementation became very important. The specification of referential integrity embodies quite a number of complications including the MATCH clause and a collection of referential actions. In particular, MATCH PARTIAL turns out to be hard to understand and, if applied, difficult and expensive to maintain. In this paper, we identify the functional requirements for preserving referential integrity. At a level free of implementational considerations, the number and kinds of searches necessary for referential integrity maintenance are derived. Based on these findings, our investigation is focused on the question of how the functional requirements can be supported by implementation concepts in an efficient way. We determine the search cost for referential integrity maintenance (in terms of page references) for various possible access path structures. Our main result is that a combined access path structure is the most appropriatefor checking the regular MATCH option, whereas MATCH PARTIAL requires very expensive and complicated check procedures. If it cannot be avoided at all, the best support is achieved by a combination of multiple B*-trees.

Key Words

Referential integrity, Relational databases, SQL2, MATCH clause, Access path support

Copyright © 1996 by Springer, Berlin, Heidelberg. Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice along with the full citation.


Online Edition (Springer)

Citation Page

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

References

[Blasgen et al. 1977]
Mike W. Blasgen, Richard G. Casey, Kapali P. Eswaran: An Encoding Method for Multifield Sorting and Indexing. Commun. ACM 20(11): 874-878(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Codd 1970]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Comer 1979]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Database language SQL 1992]
...
[Database language SQL3]
...
[Date 1981]
C. J. Date: Referential Integrity. VLDB 1981: 2-12 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Date 1990]
...
[Gray 1978]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Härder 1978]
Theo Härder: Implementing a Generalized Access Path Structure for a Relational Database System. ACM Trans. Database Syst. 3(3): 285-298(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Markowitz 1991]
Victor M. Markowitz: Safe Referential Structures in Relational Databases. VLDB 1991: 123-132 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mohan 1990]
C. Mohan: ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes. VLDB 1990: 392-405 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mohan 1992]
C. Mohan, Frank E. Levine: ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging. SIGMOD Conference 1992: 371-380 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Nievergelt et al. 1984]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Nevalainen et al. 1979]
...
[Reinert 1993]
...
[Salzberg 1986]
Betty Salzberg: Grid File Concurrency. Inf. Syst. 11(3): 235-244(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Shaw 1990]
Phil Shaw: Database Language Standards: Past, Present, and Future. IBM Symposium: Database Systems of the 90s 1990: 55-80 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Valduriez 1987]
Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Wagner 1973]
Robert E. Wagner: Indexing Design Considerations. IBM Systems Journal 12(4): 351-367(1973) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Fri Sep 14 18:29:10 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page