Sequences, Datalog and Transducers.
Giansalvatore Mecca, Anthony J. Bonner:
Sequences, Datalog and Transducers.
PODS 1995: 23-35@inproceedings{DBLP:conf/pods/MeccaB95,
author = {Giansalvatore Mecca and
Anthony J. Bonner},
title = {Sequences, Datalog and Transducers},
booktitle = {Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, May 22-25, 1995, San Jose,
California},
publisher = {ACM Press},
year = {1995},
isbn = {0-89791-730-8},
pages = {23-35},
ee = {http://doi.acm.org/10.1145/212433.212440, db/conf/pods/MeccaB95.html},
crossref = {DBLP:conf/pods/95},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
This paper develops a query language for sequence databases, such as
genome databases and text databases. The language, called
Sequence Datalog,
extends classical Datalog with interpreted function symbols
for manipulating sequences. It has both a clear operational and
declarative semantics, based on a new notion called the
extended active domain
of a database. The extended domain contains all the
sequences in the database and all their
subsequences. This idea leads
to a clear distinction between safe and unsafe recursion over
sequences: safe recursion stays inside the extended active domain,
while unsafe recursion does not. By carefully limiting the amount of
unsafe recursion, the paper develops a safe and expressive subset of
Sequence Datalog. As part of the development, a new type of
transducer is introduced, called a
generalized sequence transducer.
Unsafe recursion is allowed only within these generalized transducers.
Generalized transducers extend ordinary transducers by allowing them
to invoke other transducers as "subroutines." Generalized transducers
can be implemented in Sequence Datalog in a straightforward way.
Moreover, their introduction into the language leads to simple
conditions that guarantee safety and finiteness. This paper develops
two such conditions. The first condition expresses exactly the class
of PTIME sequence functions; and the second expresses exactly the
class of elementary sequence functions.
Copyright © 1995 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 Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 22-25, 1995, San Jose, California.
ACM Press 1995, ISBN 0-89791-730-8
Contents BibTeX
[Index Terms]
[Full Text in PDF Format, 1440 KB]
References
- [1]
- Serge Abiteboul, Victor Vianu:
Datalog Extensions for Database Queries and Updates.
J. Comput. Syst. Sci. 43(1): 62-124(1991) BibTeX
- [2]
- Antonio Albano, Luca Cardelli, Renzo Orsini:
Galileo: A Strongly-Typed, Interactive Conceptual Language.
ACM Trans. Database Syst. 10(2): 230-260(1985) BibTeX
- [3]
- Malcolm P. Atkinson, François Bancilhon, David J. DeWitt, Klaus R. Dittrich, David Maier, Stanley B. Zdonik:
The Object-Oriented Database System Manifesto.
DOOD 1989: 223-240 BibTeX
- [4]
- ...
- [5]
- François Bancilhon, Sophie Cluet, Claude Delobel:
A Query Language for the O2 Object-Oriented Database System.
DBPL 1989: 122-138 BibTeX
- [6]
- Stephen Bellantoni, Stephen A. Cook:
A New Recursion-Theoretic Characterization of the Polytime Functions (Extended Abstract).
STOC 1992: 283-293 BibTeX
- [7]
- Anthony J. Bonner:
Hypothetical Datalog: Complexity and Expressibility.
Theor. Comput. Sci. 76(1): 3-51(1990) BibTeX
- [8]
- Val Tannen, Peter Buneman, Limsoon Wong:
Naturally Embedded Query Languages.
ICDT 1992: 140-154 BibTeX
- [9]
- Ashok K. Chandra, David Harel:
Computable Queries for Relational Data Bases.
J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
- [10]
- Latha S. Colby, Edward L. Robertson, Lawrence V. Saxton, Dirk Van Gucht:
A Query Language for List-Based Complex Objects.
PODS 1994: 179-189 BibTeX
- [11]
- ...
- [12]
- Seymour Ginsburg, Xiaoyang Sean Wang:
Pattern Matching by Rs-Operations: Toward a Unified Approach to Querying Sequenced Data.
PODS 1992: 293-300 BibTeX
- [13]
- Gaston H. Gonnet:
Tutorial: Text Dominated Databases, Theory Practice and Experience.
PODS 1994: 301-302 BibTeX
- [14]
- Gösta Grahne, Matti Nykänen, Esko Ukkonen:
Reasoning about Strings in Databases.
PODS 1994: 303-312 BibTeX
- [15]
- Stéphane Grumbach, Tova Milo:
An Algebra for Pomsets.
ICDT 1995: 191-207 BibTeX
- [16]
- ...
- [17]
- Richard Hull, Jianwen Su:
On the Expressive Power of Database Queries with Intermediate Types.
J. Comput. Syst. Sci. 43(1): 219-267(1991) BibTeX
- [18]
- Neil Immerman:
Relational Queries Computable in Polynomial Time.
Information and Control 68(1-3): 86-104(1986) BibTeX
- [19]
- Neil Immerman, Sushant Patnaik, David W. Stemple:
The Expressiveness of a Family of Finite Set Languages.
PODS 1991: 37-52 BibTeX
- [20]
- John W. Lloyd:
Foundations of Logic Programming, 2nd Edition.
Springer 1987, ISBN 3-540-18199-7
BibTeX
- [21]
- ...
- [22]
- ...
- [23]
- ...
- [24]
- Joel E. Richardson:
Supporting Lists in a Data Model (A Timely Approach).
VLDB 1992: 127-138 BibTeX
- [25]
- ...
- [26]
- Douglas Stott Parker Jr., Eric Simon, Patrick Valduriez:
SVP: A Model Capturing Sets, Lists, Streams, and Parallelism.
VLDB 1992: 115-126 BibTeX
- [27]
- Michael Stonebraker, Lawrence A. Rowe, Bruce G. Lindsay, Jim Gray, Michael J. Carey, Michael L. Brodie, Philip A. Bernstein, David Beech:
Third-Generation Database System Manifesto - The Committee for Advanced DBMS Function.
SIGMOD Record 19(3): 31-44(1990) BibTeX
- [28]
- Scott L. Vandenberg, David J. DeWitt:
Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance.
SIGMOD Conference 1991: 158-167 BibTeX
- [29]
- Moshe Y. Vardi:
The Complexity of Relational Query Languages (Extended Abstract).
STOC 1982: 137-146 BibTeX
- [30]
- ...
- [31]
- ...
- [32]
- Pierre Wolper:
Temporal Logic Can Be More Expressive.
Information and Control 56(1/2): 72-99(1983) BibTeX
Referenced by
- Paolo Atzeni, Giansalvatore Mecca:
Cut & Paste.
PODS 1997: 144-153
- 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
- Leonid Libkin, Rona Machlin, Limsoon Wong:
A Query Language for Multidimensional Arrays: Design, Implementation, and Optimization Techniques.
SIGMOD Conference 1996: 228-239
- 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]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:12 2009