Safety, Translation and Evaluation of Alignment Calculus.

Gösta Grahne, Matti Nykänen: Safety, Translation and Evaluation of Alignment Calculus. ADBIS 1997: 295-304
  author    = {G{\"o}sta Grahne and
               Matti Nyk{\"a}nen},
  title     = {Safety, Translation and Evaluation of Alignment Calculus},
  booktitle = {Proceedings of the First East-European Symposium on Advances
               in Databases and Information Systems (ADBIS'97), St.-Petersburg,
               September 2-5, 1997. Volume 1: Regular Papers},
  publisher = {Nevsky Dialect},
  year      = {1997},
  pages     = {295-304},
  ee        = {db/conf/adbis/GrahneN97.html},
  crossref  = {DBLP:conf/adbis/97},
  bibsource = {DBLP,}


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.

Copyright © 1997 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 5, SSDBM, DBPL, KRDB, ADBIS, COOPIS, SIGBDP" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX


Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX
Nevzat Hurkan Balkir, Eser Sükan, Gultekin Özsoyoglu, Z. Meral Özsoyoglu: VISUAL: A Graphical Icon-Based Query Language. ICDE 1996: 524-533 BibTeX
Surajit Chaudhuri, Kyuseok Shim: Optimization of Queries with User-defined Predicates. VLDB 1996: 87-98 BibTeX
Martha Escobar-Molano, Richard Hull, Dean Jacobs: Safety and Translation of Calculus Queries with Scalar Functions. PODS 1993: 253-264 BibTeX
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
Seymour Ginsburg, Xiaoyang Sean Wang: Pattern Matching by Rs-Operations: Toward a Unified Approach to Querying Sequenced Data. PODS 1992: 293-300 BibTeX
Gösta Grahne, Matti Nykänen, Esko Ukkonen: Reasoning about Strings in Databases. PODS 1994: 303-312 BibTeX
Sheila A. Greibach: Checking Automata and One-Way Stack Languages. J. Comput. Syst. Sci. 3(2): 196-217(1969) BibTeX
John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02988-X
Ravi Krishnamurthy, Raghu Ramakrishnan, Oded Shmueli: A Framework for Testing Safety and Effective Computability. J. Comput. Syst. Sci. 52(1): 100-124(1996) BibTeX
Giansalvatore Mecca, Anthony J. Bonner: Sequences, Datalog and Transducers. PODS 1995: 23-35 BibTeX
Raghu Ramakrishnan, François Bancilhon, Abraham Silberschatz: Safety of Recursive Horn Clauses With Infinite Relations. PODS 1987: 328-339 BibTeX
Joel E. Richardson: Supporting Lists in a Data Model (A Timely Approach). VLDB 1992: 127-138 BibTeX
David B. Searls: String Variable Grammar: A Logic Grammar Formalism for the Biological Language of DNA. J. Log. Program. 24(1&2): 73-102(1995) BibTeX
Praveen Seshadri, Miron Livny, Raghu Ramakrishnan: SEQ: A Model for Sequence Databases. ICDE 1995: 232-239 BibTeX
Larry J. Stockmeyer: The Polynomial-Time Hierarchy. Theor. Comput. Sci. 3(1): 1-22(1976) BibTeX
Bharathi Subramanian, Theodore W. Leung, Scott L. Vandenberg, Stanley B. Zdonik: The AQUA Approach to Querying Lists and Trees in Object-Oriented Databases. ICDE 1995: 80-89 BibTeX
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
Andreas Weber: On the Lengths of Values in a Finite Transducer. Acta Inf. 29(6/7): 663-687(1992) BibTeX
Pierre Wolper: Temporal Logic Can Be More Expressive. Information and Control 56(1/2): 72-99(1983) BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 22:56:33 2009