Efficient sequenced temporal integrity checking

Wei Li, Richard T. Snodgrass, Shiyan Deng, Vineel K. Gattu, Aravindan Kasthurirangan

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


Primary key and referential integrity are the most widely used integrity constraints in relational databases. Each has a sequenced analogue in temporal databases, in which the constraint must apply independently at every point in time. In this paper, we assume a stratum approach, which expresses the checking in conventional SQL, as triggers on period-stamped relations. We evaluate several novel approaches that exploit B+-tree indexes to enable efficient checking of sequenced primary key (SPK) and referential integrity (SRI) constraints. We start out with a brute force SPK algorithm, then adapt the Relational Intervaltree overlap algorithm. After that, we propose a new method, the Straight Traversal algorithm, which utilizes the B+-tree more directly to identify when multiple key values are present. Our evaluation, on two platforms, shows that Straight Traversal algorithm approaches the performance of built-in nontemporal primary key and referential integrity checking, with constant time per tuple.

Original languageEnglish (US)
Pages (from-to)131-140
Number of pages10
JournalProceedings - International Conference on Data Engineering
StatePublished - 2001
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems

Cite this