The Design and Implementation of a Sequence Database System

Abstract

This paper discusses the design and implementation of SEQ, a database system with support for sequence data. SEQ models a sequence as an ordered collection of records, and supports a declarative sequence query language based on an algebra of query operators, thereby permitting algebraic query optimization and evaluation. SEQ has been built as a component of the PREDATOR database system that provides support for relational and other kinds of complex data as well. There are three distinct contributions made in this paper. (1) We describe the specification of sequence queries using the SEQUIN query language. (2) We quantitatively demonstrate the importance of various storage and optimization techniques by studying their effect on performance. (3) We present a novel nested design paradigm used in PREDATOR to combine sequence and relational data. 1 Introduction Much real-life information contains logical ordering relationships between data items. "Sequence data" refers to data that is ord...