ACM SIGMOD Anthology VLDB dblp.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}
}
BibTeX

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 ... BibTeX

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) BibTeX
[Codd 1970]
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
[Comer 1979]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
[Database language SQL 1992]
...
[Database language SQL3]
...
[Date 1981]
C. J. Date: Referential Integrity. VLDB 1981: 2-12 BibTeX
[Date 1990]
...
[Gray 1978]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[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) BibTeX
[Markowitz 1991]
Victor M. Markowitz: Safe Referential Structures in Relational Databases. VLDB 1991: 123-132 BibTeX
[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 BibTeX
[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 BibTeX
[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) BibTeX
[Nevalainen et al. 1979]
...
[Reinert 1993]
...
[Salzberg 1986]
Betty Salzberg: Grid File Concurrency. Inf. Syst. 11(3): 235-244(1986) BibTeX
[Shaw 1990]
Phil Shaw: Database Language Standards: Past, Present, and Future. IBM Symposium: Database Systems of the 90s 1990: 55-80 BibTeX
[Valduriez 1987]
Patrick Valduriez: Join Indices. ACM Trans. Database Syst. 12(2): 218-246(1987) BibTeX
[Wagner 1973]
Robert E. Wagner: Indexing Design Considerations. IBM Systems Journal 12(4): 351-367(1973) BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:31:28 2009