dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

Reasoning about Strings in Databases.

Gösta Grahne, Matti Nykänen, Esko Ukkonen: Reasoning about Strings in Databases. PODS 1994: 303-312
@inproceedings{DBLP:conf/pods/GrahneNU94,
  author    = {G{\"o}sta Grahne and
               Matti Nyk{\"a}nen and
               Esko Ukkonen},
  editor    = {Victor Vianu},
  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,
               Minnesota, USA},
  publisher = {ACM Press},
  year      = {1994},
  isbn      = {0-89791-642-5},
  pages     = {303-312},
  ee        = {http://doi.acm.org/10.1145/182591.182656, db/conf/pods/pods94-303.html},
  crossref  = {DBLP:conf/pods/94},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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 ...

Printed Edition

Victor Vianu (Ed.): Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 24-26, 1994, Minneapolis, Minnesota, USA. ACM Press 1994, ISBN 0-89791-642-5
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library

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

References

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

Last update Fri Sep 14 17:28:33 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page