Safety, Translation and Evaluation of Alignment Calculus

In this paper we pursue the study of Alignment Calculus, a declarative string database query language that supports both string querying and restructuring. This language is aimed for applications such as molecular biology databases, where the basic data type is a string, and the queries are combinatorial in nature. The declarative nature of our language does, however, require some additional effort in its implementation. Here we solve this problem by first defining a domain independent syntactic subset of the full language and then developing a query evaluation mechanism for this sublanguage. This mechanism then handles the required restructuring operations in a finite manner.