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/sup +/-tree indexes to enable efficient checking of sequenced primary key (SPK) and sequenced referential integrity (SRI) constraints. We start out with a brute-force SPK algorithm, then adapt the relational interval-tree overlap algorithm. After that, we propose a new method, the straight traversal algorithm, which utilizes the B/sup +/-tree more directly in order to identify when multiple key values are present. Our evaluation, on two platforms, shows that the straight traversal algorithm approaches the performance of built-in nontemporal primary key and referential integrity checking, with a constant time per tuple.