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 fami ly of regular sequence operations (called rs-operations) to be used in such queries. The family is based on a simple pattern matching mechan ism using regular expressions as its patterns, and includes most of th e ''natural'' operations on sequences. Properties of the family are ex amined. In particular, operations in the family are characterized by a mechanical device called generic a-transducer, and the expressive pow er of the family is studied through an investigation of finite generat ors of the operations. The usage of the rs-operations in database quer ies is illustrated through an extended relational data model. Two equi valent query languages, one algebraic and the other calculus, are give n in the model. In these query languages, rs-operations are the only c omponents used for dealing with sequences. (C) 1998 Academic Press.