A Framework for Implementing Hypothetical Queries.
Timothy Griffin, Richard Hull:
A Framework for Implementing Hypothetical Queries.
SIGMOD Conference 1997: 231-242@inproceedings{DBLP:conf/sigmod/GriffinH97,
author = {Timothy Griffin and
Richard Hull},
editor = {Joan Peckham},
title = {A Framework for Implementing Hypothetical Queries},
booktitle = {SIGMOD 1997, Proceedings ACM SIGMOD International Conference
on Management of Data, May 13-15, 1997, Tucson, Arizona, USA},
publisher = {ACM Press},
year = {1997},
pages = {231-242},
ee = {http://doi.acm.org/10.1145/253260.253304, db/conf/sigmod/GriffinH97.html},
crossref = {DBLP:conf/sigmod/97},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
Previous approaches to supporting hypothetical queries have
been "eager": some representation of the hypothetical state
(or the corresponding delta) is materialized, and query evaluation
is filtered through that representation. This paper
develops a framework for evaluating hypothetical queries using
a "lazy" approach, or using a hybrid of eager and lazy approaches.
We focus on queries having the form "Q when {{U}}"
where Q is a relational algebra query and U is an update
expression. The value assigned to this query in state DB is
the value that Q would return in the state resulting from executing
U on DB. Nesting of the keyword when is permitted,
and U may involve a sequence of several atomic updates.
We present an equational theory for queries involving
when that can be used as a basis for optimization. This
theory is very different from traditional rules for the relational
algebra, because the semantics of when is unlike the
semantics of the algebra operators. Our theory is based on
the observation that hypothetical states can be represented
as substitutions, similar to those arising in functional and
logic programming. Furthermore, hypothetical queries of
the form Q when {{U}} can be thought of as representing
the suspended application of a substitution. Using the equational
theory we develop an approach to optimizing the evaluation
of hypothetical queries that uses deltas in the sense
of Heraclitus, and permits a range of evaluation strategies
from lazy to eager.
Copyright © 1997 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.
Online Version (ACM WWW Account required): Full Text in PDF Format
CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
Printed Edition
Joan Peckham (Ed.):
SIGMOD 1997, Proceedings ACM SIGMOD International Conference on Management of Data, May 13-15, 1997, Tucson, Arizona, USA.
ACM Press 1997 BibTeX
,
SIGMOD Record 26(2),
June 1997
Contents
[Index Terms]
[Full Text in PDF Format, 1430 KB]
References
- [ACCL91]
- ...
- [BGL96]
- Michael Benedikt, Timothy Griffin, Leonid Libkin:
Verifiable Properties of Database Transactions.
PODS 1996: 117-127 BibTeX
- [Bon90]
- Anthony J. Bonner:
Hypothetical Datalog: Complexity and Expressibility.
Theor. Comput. Sci. 76(1): 3-51(1990) BibTeX
- [Bon95]
- ...
- [DHK95]
- Gilles Dowek, Thérèse Hardin, Claude Kirchner:
Higher-Order Unification via Explicit Substitutions (Extended Abstract).
LICS 1995: 366-374 BibTeX
- [DHR96]
- Michael Doherty, Richard Hull, Mohammed Rupawalla:
Structures for Manipulating Proposed Updates in Object-Oriented Databases.
SIGMOD Conference 1996: 306-317 BibTeX
- [Dij75]
- Edsger W. Dijkstra:
Guarded Commands, Nondeterminacy and Formal Derivation of Programs.
Commun. ACM 18(8): 453-457(1975) BibTeX
- [Dij76]
- Edsger W. Dijkstra:
A Discipline of Programming.
Prentice-Hall 1976
BibTeX
- [GD87]
- Goetz Graefe, David J. DeWitt:
The EXODUS Optimizer Generator.
SIGMOD Conference 1987: 160-172 BibTeX
- [GH97]
- ...
- [GHJ+93]
- Shahram Ghandeharizadeh, Richard Hull, Dean Jacobs, Jaime Castillo, Martha Escobar-Molano, Shih-Hui Lu, Junhui Luo, Chiu Tsang, Gang Zhou:
On Implementing a Language for Specifying Active Database Execution Models.
VLDB 1993: 441-454 BibTeX
- [GHJ96]
- Shahram Ghandeharizadeh, Richard Hull, Dean Jacobs:
Heraclitus: Elevating Deltas to be First-Class Citizens in a Database Programming Language.
ACM Trans. Database Syst. 21(3): 370-426(1996) BibTeX
- [GR84]
- Dov M. Gabbay, Uwe Reyle:
N-Prolog: An Extension of Prolog with Hypothetical Implications I.
J. Log. Program. 1(4): 319-355(1984) BibTeX
- [GR85]
- Dov M. Gabbay:
N-Prolog: An Extension of Prolog with Hypothetical Implication II - Logical Foundations, and Negation as Failure.
J. Log. Program. 2(4): 251-283(1985) BibTeX
- [Gra93]
- Goetz Graefe:
Query Evaluation Techniques for Large Databases.
ACM Comput. Surv. 25(2): 73-170(1993) BibTeX
- [Gri81]
- David Gries:
The Science of Programming.
Springer 1981
BibTeX
- [HR92]
- ...
- [HS86]
- J. Roger Hindley, Jonathan P. Seldin:
Introduction to Combinators and Lambda-Calculus.
Cambridge University Press 1986
BibTeX
- [Les94]
- Pierre Lescanne:
From Lambda-sigma to Lambda-upsilon a Journey Through Calculi of Explicit Substitutions.
POPL 1994: 60-69 BibTeX
- [Llo87]
- John W. Lloyd:
Foundations of Logic Programming, 2nd Edition.
Springer 1987, ISBN 3-540-18199-7
BibTeX
- [Qia90]
- Xiaolei Qian:
An Axiom System for Database Transactions.
Inf. Process. Lett. 36(4): 183-189(1990) BibTeX
- [Qia91]
- Xiaolei Qian:
The Expressive Power of the Bounded-Iteration Construct.
Acta Inf. 28(7): 631-656(1991) 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
- [WS83]
- John Woodfill, Michael Stonebraker:
An Implementation of Hypothetical Relations.
VLDB 1983: 157-166 BibTeX
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:40:37 2009