Correctness of Query Execution Strategies in Distributed Databases.

@article{DBLP:journals/tods/CeriP83,
  author    = {Stefano Ceri and
               Giuseppe Pelagatti},
  title     = {Correctness of Query Execution Strategies in Distributed Databases},
  journal   = {ACM Trans. Database Syst.},
  volume    = {8},
  number    = {4},
  year      = {1983},
  pages     = {577-607},
  ee        = {http://doi.acm.org/10.1145/319996.320009, db/journals/tods/CeriP83.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

A major requirement of a Distributed DataBase Management System (DDBMS) is to enable users to write queries as though the database were not distributed (distribution transparency). The DDBMS transforms the user's queries into execution strategies, that is, sequences of operations on the various nodes of the network and of transmissions between them. An execution strategy on a distributed database is correct if it returns the same result as if the query were applied to a nondistributed database.

This paper analyzes the correctness problem for query execution strategies. A formal model, called Multirelational Algebra, is used as a unifying framework for this purpose. The problem of proving the correctness of execution strategies is reduced to the problem of proving the equivalence of two expressions of Multirelational Algebra. A set of theorems on equivalence is given in order to facilitate this task.

The proposed approach can be used also for the generation of correct execution strategies, because it defines the rules which allow the transformation of a correct strategy into an equivalent one. This paper does not deal with the problem of evaluating equivalent strategies, and therefore is not in itself a proposal for a query optimizer for distributed databases. However, it constitutes a theoretical foundation for the design of such optimizers.

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

Joint ACM SIGMOD / IEEE Computer Society Anthology

• 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/An3-1 or /cdrom

• 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

[1]

Morton M. Astrahan, Donald D. Chamberlin: Implementation of a Structured English Query Language. Commun. ACM 18(10): 580-588(1975) BibTeX

[2]

Philip A. Bernstein, David W. Shipman, James B. Rothnie Jr.: Concurrency Control in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 18-51(1980) BibTeX

[3]

Philip A. Bernstein, Dah-Ming W. Chiu: Using Semi-Joins to Solve Relational Queries. J. ACM 28(1): 25-40(1981) BibTeX

[4]

Stefano Ceri, Giuseppe Pelagatti: Allocation of Operations in Distributed Database Access. IEEE Trans. Computers 31(2): 119-129(1982) BibTeX

[5]

Stefano Ceri, Giuseppe Pelagatti: An Upper Bound on the Number of Execution Nodes for a Distributed Join. Inf. Process. Lett. 12(1): 46-48(1981) BibTeX

[6]

...

[7]

...

[8]

Shi-Kuo Chang, Wu-Haung Cheng: A Methodology for Structured Database Decomposition. IEEE Trans. Software Eng. 6(2): 205-218(1980) BibTeX

[9]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[10]

Dean Daniels, Patricia G. Selinger, Laura M. Haas, Bruce G. Lindsay, C. Mohan, Adrian Walker, Paul F. Wilms: An Introduction to Distributed Query Compilation in R*. DDB 1982: 291-309 BibTeX

[11]

Umeshwar Dayal, Nathan Goodman, Randy H. Katz: An Extended Relational Algebra with Control over Duplicate Elimination. PODS 1982: 117-123 BibTeX

[12]

Robert S. Epstein, Michael Stonebraker, Eugene Wong: Distributed Query Processing in a Relational Data Base System. SIGMOD Conference 1978: 169-180 BibTeX

[13]

Antonio L. Furtado, Larry Kerschberg: An Algebra of Quotient Relations. SIGMOD Conference 1977: 1-8 BibTeX

[14]

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

[15]

Alan R. Hevner, S. Bing Yao: Query Processing in Distributed Database Systems. IEEE Trans. Software Eng. 5(3): 177-187(1979) BibTeX

[16]

Won Kim: On Optimizing an SQL-like Nested Query. ACM Trans. Database Syst. 7(3): 443-469(1982) BibTeX

[17]

...

[18]

Samy A. Mahmoud, J. Spruce Riordon, K. C. Toth: Distributed Database Partitioning and Query Processing. IFIP TC-2 Working Conference on Data Base Architecture 1979: 32-51 BibTeX

[19]

Paolo Paolini, Giuseppe Pelagatti: Formal Definition of Mappings in a Data Base. SIGMOD Conference 1977: 40-46 BibTeX

[20]

...

[21]

James B. Rothnie Jr., Philip A. Bernstein, Stephen Fox, Nathan Goodman, Michael Hammer, T. A. Landers, Christopher L. Reeve, David W. Shipman, Eugene Wong: Introduction to a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 5(1): 1-17(1980) BibTeX

[22]

Nan C. Shu, Barron C. Housel, Vincent Y. Lum: CONVERT: A High Level Translation Definition Language for Data Conversion. Commun. ACM 18(10): 557-567(1975) BibTeX

[23]

John Miles Smith, Philip Yen-Tang Chang: Optimizing the Performance of a Relational Algebra Database Interface. Commun. ACM 18(10): 568-579(1975) BibTeX

[24]

Michael Stonebraker, Eugene Wong, Peter Kreps, Gerald Held: The Design and Implementation of INGRES. ACM Trans. Database Syst. 1(3): 189-222(1976) BibTeX

[25]

Stanley Y. W. Su, Herman Lam, Der Her Lo: Transformation of Data Traversals and Operations in Application Programs to Account for Semantic Changes of Databases. ACM Trans. Database Syst. 6(2): 255-294(1981) BibTeX

[26]

Robert W. Taylor, James P. Fry, Ben Shneiderman, Diane C. P. Smith, Stanley Y. W. Su: Database Program Conversion: A Framework for Research. VLDB 1979: 299-312 BibTeX

[27]

Irving L. Traiger, Jim Gray, Cesare A. Galtieri, Bruce G. Lindsay: Transactions and Consistency in Distributed Database Systems. ACM Trans. Database Syst. 7(3): 323-342(1982) BibTeX

[28]

Jeffrey D. Ullman: Principles of Database Systems, 1st Edition. Computer Science Press 1980
BibTeX

[29]

...

Referenced by

1. Hao Chen, Chengwen Liu: Maintenance of Placement Dependency in Distributed Multidatabase Systems. DASFAA 1999: 339-346
2. Christian Kalus, Peter Dadam: Flexible Relations - Operational Support of Variant Relational Structures. VLDB 1995: 539-550
3. Sophie Cluet, Guido Moerkotte: Efficient Evaluation of Aggregates on Bulk Types. DBPL 1995: 8
4. Helmut Kaufmann, Moira C. Norrie: Relaxation of Correctness in Database Systems. ADBIS 1995: 90-105
5. Carlo Meghini, Costantino Thanos: The Complexity of Operations on a Fragmented Relation. ACM Trans. Database Syst. 16(1): 56-87(1991)
6. David Eichmann, D. Alton: A Polymorphic Relational Algebra and Its Optimization. ICDE 1991: 680-689
7. Arnon Rosenthal, David S. Reiner: Extending the Algebraic Framework of Query Processing to Handle Outerjoins. VLDB 1984: 334-343