Querying sequence databases with transducers

Citation
Aj. Bonner et G. Mecca, Querying sequence databases with transducers, ACT INFORM, 36(7), 2000, pp. 511-544
Citations number
32
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
ACTA INFORMATICA
ISSN journal
00015903 → ACNP
Volume
36
Issue
7
Year of publication
2000
Pages
511 - 544
Database
ISI
SICI code
0001-5903(200001)36:7<511:QSDWT>2.0.ZU;2-K
Abstract
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.