Querying sequence databases with transducers

This paper develops a database query language called Transducer Datalog mot ivated by the needs of a new and emerging class of database applications. I n these applications, such as text databases and genome databases, the stor age and manipulation of long character sequences is a crucial feature. The issues involved in managing this kind of data are not addressed by traditio nal database systems, either in theory or in practice. To address these iss ues, we recently introduced a new machine model called a generalized sequen ce transducer. These generalized transducers extend ordinary transducers by allowing them to invoke other transducers as "sub-routines." This paper es tablishes the computational properties of Transducer Datalog, a query langu age based on this new machine model. In the process, we develop a hierarchy of time-complexity classes based on the Ackermann function. The lower leve ls of this hierarchy correspond to well-known complexity classes, such as p olynomial time and hyper-exponential time. We establish a tight relationshi p between levels in this hierarchy and the depth of subroutine calls within Transducer Datalog programs. Finally we show that Transducer Datalog progr ams of arbitrary depth express exactly the sequence functions computable in primitive-recursive time.