|
Article Excerpt
The Structured Query Language (SQL) forms a substantial component of introductory database courses and is supported by almost every commercial database product. One disadvantage of SQL is that it does not provide a universal quantification construct. Queries that have twisted universal and existential quantifiers can be stunning for students, practitioners, or even instructors. Universal quantification exists in natural languages and proliferates in our daily logic. Experience shows that students can infer the rigorous logic, such as the tuple relational calculus, from natural language queries, but find it cumbersome to translate it to SQL. To bridge this gap, this article develops a systematic method to translate tuple relational calculus queries to SQL. This is accomplished by introducing the SQL-Normal-From of tuple relational calculus from which generating SQL code is straightforward. The approach is illustrated by a series of examples. This method was voluntarily adopted by a vast majority of students when it was introduced in a third-year introductory course on database systems.
**********
SQL is the most commonly used language in commercial relational database management systems, such as Oracle, SQL Server, and Ingress, and forms a substantial component of undergraduate courses on database systems (Date, 2000; Elmasri & Navathe, 2000; Korth, Silberschatz, & Sudarshan, 1999). As noted by Date (1984), SQL has many shortcomings. One major disadvantage of SQL is its lack of a direct support to a universal quantification construct. The for all and every English phrases can be satisfied in SQL through negating its existential quantifier construct EXISTS. However, when these phrases become nested and twisted with each other and with existential phrases, translating the English query to SQL can be a very subtle process, even for the most experienced. Quantification in SQL is far more complex than joining and grouping. Yet, Resiner (1981) reported that users even have some difficulties using the SQL join and group constructs. Date (2000) proposed some work techniques to avoid the use of quantification in SQL. Nevertheless, these proposed techniques require other constructs that are not supported in many commercial implementations of SQL, as Date (2000) warned. Thus, the use of quantifiers in SQL is unavoidable.
The use of universal quantifiers to comprehend and express the for all and every phrases is more natural and intuitive than negating existential quantifiers. Consider the following statement:
Every company, which is destroying at least one forest, is savage, and every person who lives in Canada is concerned (1) about such companies.
This statement could be equivalently written in English, eliminating all universal quantifiers (every phrases) as follows:
It is not true that there is a company that is destroying at least one forest and this company is not savage, or there is a person who lives in Canada and who is not concerned about that company.
The simplicity of the use of universal versus existential quantifiers in this example is evident. This is still true even after resolving the ambiguity that results from determining the scope of "It is not true that." Moreover, only "bracketing" the rest of the statement, something that requires more than English, can eliminate this ambiguity.
The use of implications with universal quantifiers is also a natural and intuitive way to express the for all and every English phrases. Furthermore, programmers, including students in the Computing disciplines, are accustomed to the use of if-then constructs. Rewriting the example with implications (if-then), results in the following:
For every c, if c is a company that is destroying at least one forest f then c is savage and for every p, if p is a person living in Canada then p is concerned about c.
It can be easily confirmed that this statement is easier to express and understand than the following, which does not use implications, although it is logically equivalent to the previous one:
For every c, either c is not a company or there is no forest f that c is destroying or c is savage, and for every p, either p is not a person or p does not live in Canada or p is not concerned about c.
Experience shows that students find it easier to translate English phrases to first-order predicate logical expressions than to SQL. This is due to the fact that universal quantification is abundant in our natural language use, but expressing it in SQL requires the negation of existential quantification, which can be quite unintuitive. The tuple relational calculus theoretical query language (Codd, 1972) is among the concepts that students learn in the same course with SQL. It uses first-order predicate logic and can be used as an intermediate step between English queries and SQL (Date, 1992).
This tutorial presents a systematic, easy-to-follow method to translate relational calculus expressions to SQL queries. The approach is demonstrated by example, using a handful of English queries with complicated quantification structures. These are first rewritten in tuple relational calculus using both kinds of quantification and using implication with universal quantifiers. Then, a sequence of well-defined steps to translate these calculus expressions to a special...
|
