Using Semiouterjoins to Process Queries in Multidatabase Systems.

Hai-Yann Hwang, Umeshwar Dayal, Mohamed G. Gouda: Using Semiouterjoins to Process Queries in Multidatabase Systems. PODS 1984: 153-162
  author    = {Hai-Yann Hwang and
               Umeshwar Dayal and
               Mohamed G. Gouda},
  title     = {Using Semiouterjoins to Process Queries in Multidatabase Systems},
  booktitle = {Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, April 2-4, 1984, Waterloo, Ontario, Canada},
  publisher = {ACM},
  year      = {1984},
  isbn      = {0-89791-128-8},
  pages     = {153-162},
  ee        = {, db/conf/pods/HwangDG84.html},
  crossref  = {DBLP:conf/pods/84},
  bibsource = {DBLP,}


A multidatabase system provides a logically integrated view of existing, possibly inconsistent, databases. Logical integration is achieved primarily through the use of generalization, which can be modelled algebraically as a sequence of outerjoin and aggregation operations. Conventional distributed query processing techniques are inadequate for processing queries over views defined by outerjoins and aggregates. In a conventional distributed database system, selections and projections are inexpensive to process; hence joins have been the focus of most previous research. In a multidatabase system, however, even selections and projections can be as expensive as joins. The semiouterjoin operation can potentially reduce query processing costs. In general, there may be many different strategies based on semiouterjoins for processing a given query. The query optimization problem is to choose the most profitable of these strategies. This paper studies the query optimization problem for selection and projection queries. It develops linear-time solutions to the problem, and then extends these solutions to provide heuristics for joins and conjunctive queries.

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

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Third ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, April 2-4, 1984, Waterloo, Ontario, Canada. ACM 1984, ISBN 0-89791-128-8
Contents BibTeX

Online Edition: ACM Digital Library


Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX
Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981) BibTeX
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
Marco A. Casanova, Vânia Maria Ponte Vidal: Towards a Sound View Integration Methodology. PODS 1983: 36-47 BibTeX
Umeshwar Dayal: Processing Queries Over Generalization Hierarchies in a Multidatabase System. VLDB 1983: 342-353 BibTeX
Umeshwar Dayal, Hai-Yann Hwang: View Definition and Generalization for Database Integration in Multibase: A System for Heterogeneous Distributed Databases. Berkeley Workshop 1982: 203-238 BibTeX
Robert S. Epstein, Michael Stonebraker, Eugene Wong: Distributed Query Processing in a Relational Data Base System. SIGMOD Conference 1978: 169-180 BibTeX
Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979) BibTeX
Randy H. Katz, Nathan Goodman: View Processing in MULTIBASE, A Heterogeneous Database System. ER 1981: 257-277 BibTeX
Terry A. Landers, Ronni Rosenberg: An Overview of MULTIBASE. DDB 1982: 153-184 BibTeX
Patricia G. Selinger, Michel E. Adiba: Access Path Selection in Distributed Database Management Systems. ICOD 1980: 204-215 BibTeX
John Miles Smith, Diane C. P. Smith: Database Abstractions: Aggregation and Generalization. ACM Trans. Database Syst. 2(2): 105-133(1977) BibTeX

Referenced by

  1. Chiang Lee, Chia-Jung Chen: Query Optimization in Multidatabase Systems Considering Schema Conflicts. IEEE Trans. Knowl. Data Eng. 9(6): 941-955(1997)
  2. Peter Scheuermann, Eugene Inseok Chong: Role-based Query Processing in Multidatabase Systems. EDBT 1994: 95-108
  3. Arbee L. P. Chen: A Localized Approach to Distributed Query Processing. EDBT 1990: 188-202
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:33:45 2009