Optimizing Relational Queries in Connection Hypergraphs: Nested Queries, Views, and Binding Propagations.

Jia Liang Han: Optimizing Relational Queries in Connection Hypergraphs: Nested Queries, Views, and Binding Propagations. VLDB J. 7(1): 1-11(1998)

@article{DBLP:journals/vldb/Han98,
  author    = {Jia Liang Han},
  title     = {Optimizing Relational Queries in Connection Hypergraphs: Nested
               Queries, Views, and Binding Propagations},
  journal   = {VLDB J.},
  volume    = {7},
  number    = {1},
  year      = {1998},
  pages     = {1-11},
  ee        = {db/journals/vldb/Han98.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We optimize relational queries using connection hypergraphs (CHGs). All operations including value-passing between SQL blocks can be set-oriented. By introducing partial evaluations, reordering operations can be achieved for nested queries. For a query using views, we merge CHGs for the views and the query into one CHG and then apply query optimization. Furthermore, we may simulate magic sets methods elegantly in a CHG. Sideways information-passing strategies (SIPS) in a CHG amount to partial evaluations of SIPS paths. We introduce the maximum SIPS strategy, which performs SIPS for all bindings and all SIPS paths for a query. The new method has several advantages. First, the maximum SIPS strategy can be more efficient than the previous SIPS based on simple heuristics. Second, it is conceptually simple and easy to implement. Third, the processing strategies may be incorporated with the search space for query execution plans, which is a proven optimization strategy introduced by System R. Fourth, it provides a general framework of query optimization and may potentially be used to optimize next-generation database systems.

Key Words

Relational query optimization - Connection hypergraphs - Partial evaluations - SIPS - Search space

Copyright © 1998 by Springer, Berlin, Heidelberg. Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice along with the full citation.

Online Edition (Springer)

Citation Page

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 5 Issue 2, JACM, VLDB-J, POS, ..." 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/An5-2 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" 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/aDVD2 or /dvd

References

[Bancilhon et al. 1986]: François Bancilhon, David Maier, Yehoshua Sagiv, Jeffrey D. Ullman: Magic Sets and Other Strange Ways to Implement Logic Programs. PODS 1986: 1-15
[Beeri and Ramakrishnan 1991]: Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. J. Log. Program. 10(1/2/3&4): 255-299(1991)
[Bernstein and Chiu 1981]: Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981)
[Han 1994a]: Jia Liang Han: Smallest-First Query Evaluation for Database Systems. Australasian Database Conference 1994: 64-78
[Han 1994b]: ...
[Han 1995]: ...
[Kim 1982]: Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982)
[Mumick and Pirahesh 1994]: Inderpal Singh Mumick, Hamid Pirahesh: Implementation of Magic-sets in a Relational Database System. SIGMOD Conference 1994: 103-114
[Mumick et al. 1990a]: Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic Conditions. PODS 1990: 314-330
[Mumick et al. 1990b]: Inderpal Singh Mumick, Sheldon J. Finkelstein, Hamid Pirahesh, Raghu Ramakrishnan: Magic is Relevant. SIGMOD Conference 1990: 247-258
[Mumick et al. 1990c]: Inderpal Singh Mumick, Hamid Pirahesh, Raghu Ramakrishnan: The Magic of Duplicates and Aggregates. VLDB 1990: 264-277
[Pirahesh et al. 1992]: Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan: Extensible/Rule Based Query Rewrite Optimization in Starburst. SIGMOD Conference 1992: 39-48
[Selinger et al. 1979]: Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34
[Swami 1989]: Arun N. Swami: Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques. SIGMOD Conference 1989: 367-376
[Swami and Gupta 1988]: Arun N. Swami, Anoop Gupta: Optimization of Large Join Queries. SIGMOD Conference 1988: 8-17
[Ullman 1982]: Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
[Ullman 1988]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents
[Ullman 1989]: Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents
[Wong and Youssefi 1976]: Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976)