This paper develops a query language for sequence databases, such as genome
databases and text databases. Unlike relational data, queries over sequent
ial data can easily produce infinite answer sets since the universe of sequ
ences is infinite, even for a finite alphabet. The challenge is to develop
query languages that are both highly expressive and finite. This paper deve
lops such a language as a subset of a logic for string databases called Seq
uence Datalog. The main idea is to use safe recursion to control and limit
unsafe recursion. The main results are the definition of a finite form of r
ecursion, called domain-bounded recursion, and a characterization of its co
mplexity and expressive power. Although finite, the resulting class of prog
rams is highly expressive since its data complexity is complete for the ele
mentary functions.