Formal semantics of SQL queries

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Formal semantics of SQL queries

Full text

Pdf (1.39 MB)

Source

ACM Transactions on Database Systems (TODS) archive
Volume 16 , Issue 3 (September 1991) table of contents

Pages: 513 - 534

Year of Publication: 1991

ISSN:0362-5915

Authors

M. Negri	Univ. di Brescia, Brescia, Italy
G. Pelagatti	Politecnico di Milano, Milan, Italy
L. Sbattella	Politecnico di Milano, Milan, Italy

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 27, Downloads (12 Months): 207, Citation Count: 9

Additional Information:

abstract references cited by index terms review collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/111197.111212 What is a DOI?

ABSTRACT

The semantics of SQL queries is formally defined by stating a set of rules that determine a syntax-driven translation of an SQL query to a formal model. The target model, called Extended Three Valued Predicate Calculus (E3VPC), is largely based on a set of well-known mathematical concepts. The rules which allow the transformation of a general E3VPC expression to a Canonical Form, which can be manipulated using traditional, two-valued predicate calculus are also given; in this way, problems like equivalence analysis of SQL queries are completely solved. Finally, the fact that reasoning about the equivalence of SQL queries using two-valued predicate calculus, without taking care of the real SQL semantics can lead to errors is shown, and the reasons for this are analyzed.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. V. Aho , Y. Sagiv , J. D. Ullman, Efficient optimization of a class of relational expressions, ACM Transactions on Database Systems (TODS), v.4 n.4, p.435-454, Dec. 1979 [doi>10.1145/320107.320112]
	2	AHO, A. V., SAGIV, Y., AND ULLMAN, J.D. Equivalence of relational expressions. SIAM J. Comput. 8 (1979), 218-246.
	3	AMERICAN NATIONAL STANDARD INSTITUTE. American National Standard Database Language SQL. ISO/TC97/SC21/WG5-15, n. 90, Washington D.C., 1985.
	4	Günter von Bültzingsloewen, Translating and Optimizing SQL Queries Having Aggregates, Proceedings of the 13th International Conference on Very Large Data Bases, p.235-243, September 01-04, 1987
	5	Stefano Ceri , Georg Gottlob, Translating SQL into relational algebra: optimization, semantics, and equivalence of SQL queries, IEEE Transactions on Software Engineering, v.11 n.4, p.324-345, April 1985 [doi>10.1109/TSE.1985.232223]
	6	CHAMBERLIN, D. D. ET AL. Sequel 2: A unified approach to data definition, manipulation, and control. IBM J. Res. Dev. 20 (1976), 560-575.
	7	CODD, E.F. Understanding relations (Installment 7) FDT Bull. ACM-SIGMOD 7 (1975), 23-28.
	8	E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
	9	C J Date, A guide to the SQL standard, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	10	Umeshwar Dayal, Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers, Proceedings of the 13th International Conference on Very Large Data Bases, p.197-208, September 01-04, 1987
	11	GALLAIRE, H. Impacts of logic on data bases. In Proceedings of the 7th Conference on Very Large Data Bases (Cannes, 1981).
	12	Richard A. Ganski , Harry K. T. Wong, Optimization of nested SQL queries revisited, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.23-33, May 27-29, 1987, San Francisco, California, United States
	13	Georg Gottlob , Roberto Zicari, Closed World Databases Opened Through Null Values, Proceedings of the 14th International Conference on Very Large Data Bases, p.50-61, August 29-September 01, 1988
	14	GRANT, J. Null values in a relational database. Inf. Process. Lett. 5 (1977), 156-157.
	15	Matthias Jarke , Joachim W. Schmidt, Query processing strategies in the PASCAL/R relational database management system, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582402]
	16	Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984 [doi>10.1145/356924.356928]
	17	Won Kim, On optimizing an SQL-like nested query, ACM Transactions on Database Systems (TODS), v.7 n.3, p.443-469, Sept. 1982 [doi>10.1145/319732.319745]
	18	KLUG, A. On inequality tableaux. Computer Science Tech Rep. 403, Univ. of Wisconsin, Madison, 1980.
	19	Anthony Klug, Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions, Journal of the ACM (JACM), v.29 n.3, p.699-717, July 1982 [doi>10.1145/322326.322332]
	20	Witold Lipski, Jr., On semantic issues connected with incomplete information databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.262-296, Sept. 1979 [doi>10.1145/320083.320088]
	21	NEGRI, M., PELAGATTI, G., AND SBATTELLA, L. The effect of three-valued predicates on the semantics and equivalence of SQL queries Tech Rep. 85-27, Dip di Elettromca, Politecnico di Milano, 1985.
	22	Arnon Rosenthal , David Reiner, An architecture for query optimization, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582401]
	23	Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
	24	P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
	25	John Miles Smith , Philip Yen-Tang Chang, Optimizing the performance of a relational algebra database interface, Communications of the ACM, v.18 n.10, p.568-579, Oct. 1975 [doi>10.1145/361020.361025]
	26	Donald F. Stanat , David F. McAllister, Discrete Mathematics in Computer Science, Prentice Hall Professional Technical Reference, 1977
	27	Yannis Vassiliou, Null values in data base management a denotational semantics approach, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582123]
	28	Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]

CITED BY 9

	H.-J. Klein, How to modify SQL queries in order to guarantee sure answers, ACM SIGMOD Record, v.23 n.3, p.14-20, Sept. 1994
	Surajit Chaudhuri, Optimization of real conjunctive queries, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.59-70, May 25-28, 1993, Washington, D.C., United States
	Yannis E. Ioannidis , Raghu Ramakrishnan, Containment of conjunctive queries: beyond relations as sets, ACM Transactions on Database Systems (TODS), v.20 n.3, p.288-324, Sept. 1995
	Aris Tsois , Timos Sellis, The generalized pre-grouping transformation: aggregate-query optimization in the presence of dependencies, Proceedings of the 29th international conference on Very large data bases, p.644-655, September 09-12, 2003, Berlin, Germany
	César A. Galindo-Legaria, Outerjoins as disjunctions, ACM SIGMOD Record, v.23 n.2, p.348-358, June 1994
	G. N. Paulley , Per-Åke Larson, Exploiting uniqueness in query optimization, Proceedings of the 1993 conference of the Centre for Advanced Studies on Collaborative research: distributed computing, October 24-28, 1993, Toronto, Ontario, Canada
	Richard Thomas Snodgrass , S. Gomez , E. McKenzie, Aggregates in the Temporal Query Language TQuel, IEEE Transactions on Knowledge and Data Engineering, v.5 n.5, p.826-842, October 1993
	Hock Chan , Keng Siau , Kwok-Kee Wei, The effect of data model, system and task characteristics on user query performance: an empirical study, ACM SIGMIS Database, v.29 n.1, Winter 1997
	E. Bertino , M. Negri , G. Pelagatti , L. Sbattella, Object-Oriented Query Languages: The Notion and the Issues, IEEE Transactions on Knowledge and Data Engineering, v.4 n.3, p.223-237, June 1992

INDEX TERMS

Primary Classification:
H. Information Systems
H.2 DATABASE MANAGEMENT
H.2.3 Languages

Nouns: SQL

Additional Classification:
F. Theory of Computation
F.3 LOGICS AND MEANINGS OF PROGRAMS

H. Information Systems
H.2 DATABASE MANAGEMENT
H.2.4 Systems
Subjects: Query processing
H.3 INFORMATION STORAGE AND RETRIEVAL
H.3.3 Information Search and Retrieval
Subjects: Query formulation

General Terms:
Design, Languages, Theory

Keywords:
SQL, query equivalence, query semantics

REVIEW

"Marcos P. Sivitanides : Reviewer"

The objective of this paper, as stated in the first section, is to give a complete formal definition of the semantics of SQL queries by stating a set of rules determining a syntax-driven translation of an SQL query to a formal model called ext more...

Collaborative Colleagues:

M. Negri: colleagues

G. Pelagatti: colleagues

L. Sbattella: colleagues

Peer to Peer - Readers of this Article have also read:

Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein
Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM 34, 12
Ellen Francik , Susan Ehrlich Rudman , Donna Cooper , Stephen Levine
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE conference on Design automation
Gwo-Dong Chen , Daniel D. Gajski

Adobe Acrobat

QuickTime

Windows Media Player

Real Player