ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Computing Queries from Derived Relations.

Per-Åke Larson, H. Z. Yang: Computing Queries from Derived Relations. VLDB 1985: 259-269
@inproceedings{DBLP:conf/vldb/LarsonY85,
  author    = {Per-{\AA}ke Larson and
               H. Z. Yang},
  editor    = {Alain Pirotte and
               Yannis Vassiliou},
  title     = {Computing Queries from Derived Relations},
  booktitle = {VLDB'85, Proceedings of 11th International Conference on Very
               Large Data Bases, August 21-23, 1985, Stockholm, Sweden},
  publisher = {Morgan Kaufmann},
  year      = {1985},
  pages     = {259-269},
  ee        = {db/conf/vldb/LarsonY85.html},
  crossref  = {DBLP:conf/vldb/85},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Assume that a set of derived relations are available in stored form. Given a query (or subquery), can it be computed from the derived rela- tions and, if so, how? Variants of this problem arise in several areas of query processing. Relation fragments stored at a site in a distributed database system, data- base snapshots, and intermediate results obtained dur- ing the processing of a query are all examples of stored, derived relations. In this paper we give neces- sary and sufficient conditions for when a query is com- putable from a single derived relation. It is assumed that both the query and the derived relation are defined by PSJ-expressions, that is, relational algebra expressions involving only projections, selections, and joins, in any combination. The solution is constructive: not only does it tell whether the query is computable or not, but it also shows how to compute it.

Copyright © 1985 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

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Alain Pirotte, Yannis Vassiliou (Eds.): VLDB'85, Proceedings of 11th International Conference on Very Large Data Bases, August 21-23, 1985, Stockholm, Sweden. Morgan Kaufmann 1985
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[AL80]
Michel E. Adiba, Bruce G. Lindsay: Database Snapshots. VLDB 1980: 86-91 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AS79]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[AS76]
Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson: System R: Relational Approach to Database Management. ACM Trans. Database Syst. 1(2): 97-137(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BAB82]
Edward Babb: Joined Normal Form: A Storage Encoding for Relational Databases. ACM Trans. Database Syst. 7(4): 588-614(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BL81]
...
[CP84]
Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FS82]
Sheldon J. Finkelstein: Common Subexpression Analysis in Database Applications. SIGMOD Conference 1982: 235-245 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MA83]
David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RH80]
Daniel J. Rosenkrantz, Harry B. Hunt III: Processing Conjunctive Predicates and Queries. VLDB 1980: 64-72 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RO82]
Nick Roussopoulos: View Indexing in Relational Databases. ACM Trans. Database Syst. 7(2): 258-290(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SY81]
Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SS81]
...
[SW76]
Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[UL82]
Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Mon Mar 15 03:55:49 2010 by Michael Ley (ley@uni-trier.de)