Regular Sequence Operations and Their Use in Database Queries

摘要

Operations on sequences are a basic component of database queries that extract information from sequenced data. This paper introduces a family of regular sequence operations (called rs-operations) to be used in such queries. The family is based on a simple pattern matching mechanism using regular expressions as its patterns, and includes most of the “natural” operations on sequences. Properties of the family are examined. In particular, operations in the family are characterized by a mechanical device called generic a-transducer, and the expressive power of the family is studied through an investigation of finite generators of the operations. The usage of the rs-operations in database queries is illustrated through an extended relational data model. Two equivalent query languages, one algebraic and the other calculus, are given in the model. In these query languages, rs-operations are the only components used for dealing with sequences.