Sequence Datalog: Declarative String Manipulation in Databases

. We investigate logic-based query languages for sequence databases, that is, databases in which strings of symbols over a fixed alphabet can occur. We discuss different approaches to querying strings, including Prolog and Datalog with function symbols, and argue that all of them have important limitations. We then present the semantics of Sequence Datalog, a logic for querying sequence databases, and show how this language can be used to perform structural recursion over sequences. 1 Introduction In the last decade, new applications (e.g. CAD and CASE) have been a powerful driving force in the development of new database technology. New paradigms have arisen (e.g. object oriented databases [4]) that provide greater flexibility than the traditional relational model. However, in some application areas, such as genome databases [14] and text databases [16], there is still a need for greater flexibility, both in data representation and manipulation. These applications are characterized ..