Sequence Datalog: Declarative string manipulation in databases
Lecture notes in computer sciencePublished 1 January 1996
Anthony J. Bonner, Giansalvatore Mecca
Citations3
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The semantics of Sequence Datalog, a logic for querying sequence databases, is presented, and it is shown how this language can be used to perform structural recursion over sequences.
Abstract
We investigate logic-based query languages for sequence databases, that is, databases in which strings of symbols over a fixed alphabet can occur. We discuss different approaches to querying strings, including Prolog and Datalog with function symbols, and argue that all of them have important limitations. We then present the semantics of Sequence Datalog, a logic for querying sequence databases, and show how this language can be used to perform structural recursion over sequences.
Keywords
Computer Science
Foundations of Logic Programming
4,159 Citations1984John W. Lloyd
Foundations of databases
3,400 Citations1994Serge Abiteboul, Richard Hull +1 more
Programming in Prolog
1,761 Citations1984William F. Clocksin, Chris Mellish
Surveys in computer scienceLogic Programming and Databases
746 Citations1990Stefano Ceri, Georg Gottlob +1 more
IEEE Transactions on Knowledge and Data EngineeringWhat you always wanted to know about Datalog (and never dared to ask)
691 Citations1989Stefano Ceri, Georg Gottlob +1 more
The syntax and semantics of Datalog and its use for querying a relational database are presented, and the most relevant methods for achieving efficient evaluations of Daloog queries are presented.
Elsevier eBooksThe Object-Oriented Database System Manifesto
609 Citations1990Malcolm Atkinson, David J. DeWitt +4 more
This paper attempts to define an object-oriented database system and takes a position, not so much expecting it to be the final word as to erect a provisional landmark to orient further debate.
Journal of the ACMContributions to the Theory of Logic Programming
586 Citations1982Krzysztof R. Apt, M. H. van Emden
It is shown that nondeterministic flowchart schemata of bounded nondeterminacy are modeled by this special case of Hom clauses, and the connection between finite failure and greatest fixpoint is used to give a semantic characterization of termination, blocking, and nontermination of such flowchart Schemata.
Journal of Computer and System SciencesComputable queries for relational data bases
440 Citations1980Ashok K. Chandra, David Harel
The main result is the completeness of a simple programming language which can be thought of as consisting of the relational algebra augmented with the power of iteration.
Journal of Computer and System SciencesDatalog extensions for database queries and updates
256 Citations1991Serge Abiteboul, Victor Vianu
Deterministic and non-deterministic extensions of Datalog with fixpoint semantics are proposed, and their expressive power characterized, to overcome the limited expressive power available with purely declarative semantics.
Lecture notes in computer scienceNaturally embedded query languages
151 Citations1992Val Breazu-Tannen, Peter Buneman +1 more
A progression of sublanguages in this paradigm that have increasing expressive power are described, and robust conceptual restrictions are illustrated thus exhibiting interesting additional properties.
Structural recursion as a query language
120 Citations1992Val Breazu-Tannen, Peter Buneman +1 more
A programming paradigm that tries to get close to both the semantic simplicity of relational algebra, and the expressive power of unrestricted programming languages, and it is expected that lower-level programming, and therefore better optimization will be feasible.
Sequences, Datalog and transducers
55 Citations1995Giansalvatore Mecca, Anthony J. Bonner
By carefully limiting the amount of unsafe recursion, the paper develops a safe and expressive subset of Sequence Datalog, which has both a clear operational and declarative semantics, based on a new notion called the extended active domain of a database.
Theoretical Computer ScienceHypothetical datalog: complexity and expressibility
55 Citations1990Anthony J. Bonner
It is shown that augmenting Horn-clause logic with hypothetical addition increases its data-complexity from PTIME to PSPACE, and any typed generic query that is computable in PSPACE can be expressed as a stratified rulebase of hypothetical additions and deletions.
Supporting Lists in a Data Model (A Timely Approach)
48 Citations1992Joel E. Richardson
A new framework based on Boolean circuits for evaluating the truth of an assertion on a given list is described, which provides many opportunities for optimization and parallelism, and it lends insight to the meaning and complexity of a temporal formula.
Pattern matching by Rs-operations
34 Citations1992Seymour Ginsburg, Xiaoyang Wang
To illustrate the applicability of the concepts to database queries, rs-operations and SL are used in an algebra and a calculus, respectively, over an extended relational data model containing sequences.
Reasoning about strings in databases
25 Citations1994Gösta Grahne, Matti Nykänen +1 more
Lecture notes in computer scienceAn algebra for pomsets
20 Citations1995Stéphane Grumbach, Tova Milo
An algebra for pomsets is introduced, which generalizes traditional algebras for (nested) sets, bags and lists and yields the same expressive power as fixpoint logic with counting on relational databases.
A query language for list-based complex objects
17 Citations1994Latha S. Colby, Edward L. Robertson +2 more
A simple syntactic constraint allows the growth rate of the intermediate results to be tightly controlled which restricts the expressiveness of the language to PTIME.
SVP - a Model Capturing Sets, Streams, and Parallelism
14 Citations1998D. Stott Parker, Eric Simon +1 more
It is shown that many useful database mappings have a divide-and-conquer format when specified using collections, and that this specification exposes parallelism.
Lecture notes in computer scienceLOGIDATA+: Deductive Databases with Complex Objects
14 Citations1993Paolo Atzeni
Modeling semantic integrity constraints in object-oriented database schemas and effective implementation of negation in database logic query languages are studied.
Electronic workshops in computingFinite Query Languages for Sequence Databases
7 Citations1995Giansalvatore Mecca, Anthony J. Bonner
The main idea is to use safe recursion to control and limit unsafe recursion, and the definition of a finite form of recursion called domain bounded recursion is presented, which is a characterization of its complexity and expressive power.