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},
  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},
  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}
}

BibTeX

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

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]

References

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

Referenced by

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

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]