Translation and Optimization of Logic Queries: The Algebraic Approach.
Stefano Ceri, Georg Gottlob, Luigi Lavazza:
Translation and Optimization of Logic Queries: The Algebraic Approach.
VLDB 1986: 395-402@inproceedings{DBLP:conf/vldb/CeriGL86,
author = {Stefano Ceri and
Georg Gottlob and
Luigi Lavazza},
editor = {Wesley W. Chu and
Georges Gardarin and
Setsuo Ohsuga and
Yahiko Kambayashi},
title = {Translation and Optimization of Logic Queries: The Algebraic
Approach},
booktitle = {VLDB'86 Twelfth International Conference on Very Large Data Bases,
August 25-28, 1986, Kyoto, Japan, Proceedings},
publisher = {Morgan Kaufmann},
year = {1986},
isbn = {0-934613-18-4},
pages = {395-402},
ee = {db/conf/vldb/CeriGL86.html},
crossref = {DBLP:conf/vldb/86},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
This paper presents an algebraic approach to
translation and optimization of logic queries. We
first develop a syntax directed translation from
rules of function-free logic programs to algebraic
equations; then we show solution methods for
independent equations and for systems of
interdependent equations. Such solutions define the
operational and fixpoint semantics of function-free
logic programs and queries. We also present
algebraic optimization methods for "top-down" and
"bottom-up" strategies; the former are useful if no
initial binding is provided with the query, while
the latter are useful if some arguments of the
query are bound to constant values.
Copyright © 1986 by the VLDB Endowment.
Permission to copy without fee all or part of this material is granted provided that the copies are not made or
distributed for direct commercial advantage, the VLDB
copyright notice and the title of the publication and
its date appear, and notice is given that copying
is by the permission of the Very Large Data Base
Endowment. To copy otherwise, or to republish, requires
a fee and/or special permission from the Endowment.
Online Paper
CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
Printed Edition
Wesley W. Chu, Georges Gardarin, Setsuo Ohsuga, Yahiko Kambayashi (Eds.):
VLDB'86 Twelfth International Conference on Very Large Data Bases, August 25-28, 1986, Kyoto, Japan, Proceedings.
Morgan Kaufmann 1986, ISBN 0-934613-18-4
Contents 
References
- [Aho79]
- Alfred V. Aho, Jeffrey D. Ullman:
The Universality of Data Retrieval Languages.
POPL 1979: 110-120
- [Apt82]
- Krzysztof R. Apt, Maarten H. van Emden:
Contributions to the Theory of Logic Programming.
J. ACM 29(3): 841-862(1982)
- [Bancilhon86]
- François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman:
Magic Sets and Other Strange Ways to Implement Logic Programs.
PODS 1986: 1-15
- [Camerini86]
- ...
- [Ceri85]
- ...
- [Ceri86]
- ...
- [Chandra82]
- Ashok K. Chandra, David Harel:
Horn Clauses and the Fixpoint Query Hierarchy.
PODS 1982: 158-163
- [Henshen84]
- Lawrence J. Henschen, Shamim A. Naqvi:
On compiling queries in recursive first-order databases.
J. ACM 31(1): 47-85(1984)
- [Marque-Pucheu84]
- G. Marque-Pucheu, J. Martin-Gallausiaux, Geneviève Jomier:
Interfacing Prolog and Relational Data Base Management Systems.
ICOD-2 Workshop on New Applications of Data Bases 1983: 225-244
- [Reiter78]
- Raymond Reiter:
On Closed World Data Bases.
Logic and Data Bases 1977: 55-76
- [Sacca86]
- Domenico Saccà, Carlo Zaniolo:
On the Implementation of a Simple Class of Logic Queries for Databases.
PODS 1986: 16-23
- [Ullman82]
- Jeffrey D. Ullman:
Principles of Database Systems, 2nd Edition.
Computer Science Press 1982, ISBN 0-914894-36-6
- [Ullman85]
- Jeffrey D. Ullman:
Implementation of Logical Query Languages for Databases.
ACM Trans. Database Syst. 10(3): 289-321(1985)
- [VanEmden76]
- Maarten H. van Emden, Robert A. Kowalski:
The Semantics of Predicate Logic as a Programming Language.
J. ACM 23(4): 733-742(1976)
Referenced by
- Maurice A. W. Houtsma, Annita N. Wilschut, Jan Flokstra:
Implementation and Performance Evaluation of a Parallel Transitive Closure Algorithm on PRISMA/DB.
VLDB 1993: 206-217
- Philippe De Smedt, Stefano Ceri, Marie-Anne Neimat, Ming-Chien Shan, Rafi Ahmed:
Recursive Functions in Iris.
ICDE 1993: 145-154
- Béatrice Finance, Georges Gardarin:
A Rule-Based Query Rewriter in an Extensible DBMS.
ICDE 1991: 248-256
- Weining Zhang, Clement T. Yu, Daniel Troy:
Necessary and Sufficient Conditions to Linearize Double Recursive Programs in Logic Databases.
ACM Trans. Database Syst. 15(3): 459-482(1990)
- Juhani Kuittinen, Otto Nurmi, Seppo Sippu, Eljas Soisalon-Soininen:
Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries.
VLDB 1990: 372-379
- Stefano Ceri, Georg Gottlob, Letizia Tanca:
What you Always Wanted to Know About Datalog (And Never Dared to Ask).
IEEE Trans. Knowl. Data Eng. 1(1): 146-166(1989)
- Georg Gottlob, Michael Schrefl, Markus Stumptner:
On the Interaction between Transitive Closure and Functional Dependencies.
MFDBS 1989: 187-206
- Shojiro Nishio, Masatsugu Nakahata, Eric G. Manning:
A New Recursive Query Evaluation Strategy Using Search History Information.
DASFAA 1989: 310-319
- Stefano Ceri, Stefano Crespi-Reghizzi, Georg Gottlob, F. Lamperti, Luigi Lavazza, Letizia Tanca, Roberto Zicari:
The Algres Project.
EDBT 1988: 551-555
- Wolfgang Nejdl:
Recursive Strategies for Answering Recursive Queries - The RQA/FQI Strategy.
VLDB 1987: 43-50
- Georges Gardarin:
Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs.
VLDB 1987: 21-30
- Stefano Ceri, Letizia Tanca:
Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries.
VLDB 1987: 31-41
- Weining Zhang, Clement T. Yu:
A Necessary Condition for a Doubly Recursive Rule to be Equivalent to a Linear Recursive Rule.
SIGMOD Conference 1987: 345-356
Last update Fri May 25 08:45:11 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
