Efficient Optimization of a Class of Relational Expressions (Abstract).

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions (Abstract). SIGMOD Conference 1978: 39

@inproceedings{DBLP:conf/sigmod/AhoSU78,
  author    = {Alfred V. Aho and
               Yehoshua Sagiv and
               Jeffrey D. Ullman},
  editor    = {Eugene I. Lowenthal and
               Nell B. Dale},
  title     = {Efficient Optimization of a Class of Relational Expressions (Abstract)},
  booktitle = {Proceedings of the 1978 ACM SIGMOD International Conference on
               Management of Data, Austin, Texas, May 31 - June 2, 1978},
  publisher = {ACM},
  year      = {1978},
  pages     = {39},
  ee        = {http://doi.acm.org/10.1145/509252.509268, db/conf/sigmod/AhoSU78.html},
  crossref  = {DBLP:conf/sigmod/78},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Many useful database queries can be formulated in terms of expressions whose operands are relations and whose operators are the relational operations select, project, and join. This paper investigates the computational complexity of optimizing relational expressions of this form under a variety of cost measures. A matrix, called a tableau, is proposed as a conventient representative for the value of an expression. Functional dependencies can be used to imply additional equivalences among tableaux. The optimization problem is shown to be NP-complete, but we can give a polynomial time algorithm to optimize tableaux that correspond to an important subclass of expressions.

Copyright © 1978 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.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod7592 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

BibTeX

Printed Edition

Eugene I. Lowenthal, Nell B. Dale (Eds.): Proceedings of the 1978 ACM SIGMOD International Conference on Management of Data, Austin, Texas, May 31 - June 2, 1978. ACM 1978 BibTeX
Contents

Online Edition: ACM Digital Library

Journal Version

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions. ACM Trans. Database Syst. 4(4): 435-454(1979) BibTeX

Referenced by

D. M. Chiu, Y. C. Ho: A Methodology for Interpreting Tree Queries Into Optimal Semi-Join Expressions. SIGMOD Conference 1980: 169-178
Sylvia L. Osborn: Towards a Universal Relation Interface. VLDB 1979: 52-60
Yehoshua Sagiv, Mihalis Yannakakis: Equivalence among Relational Expressions with the Union and Difference Operation. VLDB 1978: 535-548

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]