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 
[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)
- [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
- [GiS65]
- Seymour Ginsburg, Edwin H. Spanier:
Mappings of languages by two-tape devices.
J. ACM 12(3): 423-434(1965)
- [GiW92]
- Seymour Ginsburg, Xiaoyang Sean Wang:
Pattern Matching by Rs-Operations: Toward a Unified Approach to Querying Sequenced Data.
PODS 1992: 293-300
- [HeS93]
- ...
- [PiT86]
- Peter Pistor, Roland Traunmüller:
A database language for sets, lists and tables.
Inf. Syst. 11(4): 323-336(1986)
- [RBS87]
- Raghu Ramakrishnan, François Bancilhon, Abraham Silberschatz:
Safety of Recursive Horn Clauses With Infinite Relations.
PODS 1987: 328-339
- [Ric92]
- ...
- [SaK83]
- ...
- [Sto77]
- Larry J. Stockmeyer:
The Polynomial-Time Hierarchy.
Theor. Comput. Sci. 3(1): 1-22(1976)
- [Ull88]
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume I.
Computer Science Press 1988, ISBN 0-7167-8158-1
Contents - [Var82]
- Moshe Y. Vardi:
The Complexity of Relational Query Languages (Extended Abstract).
STOC 1982: 137-146
- [Wol83]
- Pierre Wolper:
Temporal Logic Can Be More Expressive.
Information and Control 56(1/2): 72-99(1983)
Last update Fri Sep 14 17:28:33 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
