Reasoning about Strings in Databases.

Gösta Grahne, Matti Nykänen, Esko Ukkonen: Reasoning about Strings in Databases. PODS 1994: 303-312
  author    = {G{\"o}sta Grahne and
               Matti Nyk{\"a}nen and
               Esko Ukkonen},
  title     = {Reasoning about Strings in Databases},
  booktitle = {Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 24-26, 1994, Minneapolis,
  publisher = {ACM Press},
  year      = {1994},
  isbn      = {0-89791-642-5},
  pages     = {303-312},
  ee        = {, db/conf/pods/pods94-303.html},
  crossref  = {DBLP:conf/pods/94},
  bibsource = {DBLP,}


In order to enable the database programmer to reason about relations over strings of arbitrary length we introduce alignment logic, a modal extension of relational calculus. In addition to relations, a state in the model consists of a two-dimensional array where the strings are aligned on top of each other. The basic modality in the language (a transpose, or "slide") allows for a rearrangment of the alignment, and more complex formulas can be formed using a syntax reminiscent of regular expressions, in addition to the usual connectives and quantifiers. It turns out that the computational counterpart of the string-based portion of the logic is the class of multitape two-way finite state automata, which are devices particularly well suited for the implementation of string matching. A computational counterpart of the full logic is obtained from relational algebra by extending the selection operator into filters based on these multitape machines. Safety of formulas in alignment logic implies that new strings generated from old ones have to be of bounded length. While an undecidable property in general, this boundedness is decidable for an important subclass of formulas. As far as expressive power is concerned, alignment logic includes previous proposals for querying string databases, and gives full Turing computability. The language can be restricted to define exactly regular sets and sets in the polynomial hierarchy.

Copyright © 1994 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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 24-26, 1994, Minneapolis, Minnesota. ACM Press 1994, ISBN 0-89791-642-5
Contents BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 874 KB]


Zvi Galil, Joel I. Seiferas: Time-Space-Optimal String Matching. J. Comput. Syst. Sci. 26(3): 280-294(1983) 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, Edwin H. Spanier: Mappings of languages by two-tape devices. J. ACM 12(3): 423-434(1965) BibTeX
Seymour Ginsburg, Xiaoyang Sean Wang: Pattern Matching by Rs-Operations: Toward a Unified Approach to Querying Sequenced Data. PODS 1992: 293-300 BibTeX
Peter Pistor, Roland Traunmüller: A database language for sets, lists and tables. Inf. Syst. 11(4): 323-336(1986) BibTeX
Raghu Ramakrishnan, François Bancilhon, Abraham Silberschatz: Safety of Recursive Horn Clauses With Infinite Relations. PODS 1987: 328-339 BibTeX
Larry J. Stockmeyer: The Polynomial-Time Hierarchy. Theor. Comput. Sci. 3(1): 1-22(1976) BibTeX
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX
Pierre Wolper: Temporal Logic Can Be More Expressive. Information and Control 56(1/2): 72-99(1983) BibTeX

Referenced by

  1. Lei Sheng, Z. Meral Özsoyoglu, Gultekin Özsoyoglu: A Graph Query Language and Its Query Processing. ICDE 1999: 572-581
  2. Anthony J. Bonner, Giansalvatore Mecca: Querying String Databases with Transducers. DBPL 1997: 118-135
  3. Gösta Grahne, Matti Nykänen: Safety, Translation and Evaluation of Alignment Calculus. ADBIS 1997: 295-304
  4. Nevzat Hurkan Balkir, Eser Sükan, Gultekin Özsoyoglu, Z. Meral Özsoyoglu: VISUAL: A Graphical Icon-Based Query Language. ICDE 1996: 524-533
  5. Giansalvatore Mecca, Anthony J. Bonner: Sequences, Datalog and Transducers. PODS 1995: 23-35
  6. H. V. Jagadish, Alberto O. Mendelzon, Tova Milo: Similarity-Based Queries. PODS 1995: 36-45
  7. 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
  8. Giansalvatore Mecca, Anthony J. Bonner: Finite Query Languages for Sequence Databases. DBPL 1995: 12
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 23:34:11 2009