Non SQL Query Languages

By Antoni Kokot and David West
October 11, 2005

Introduction

Ever since the first specification of SQL was approved in 1986 the terms SQL and relational database have been all but synonymous. It is important to note that they are not. Databases in some form or another long predate the formal definition of relational databases. Likewise, several query languages were developed to interact with relational databases before the existence of SQL. While the vast majority of databases nowadays use query languages that at least aspire to be SQL complaint, there are still a few that are not.

We focus on two such non-SQL query languages: D and Quel. D is a relatively new query language, but it seeks to combine the best of the old and the new. It seeks to return to the formal roots of relational databases by adhering more closely to the set theory that is the intellectual underpinning of relational databases. At the same time, it attempts to integrate support for objects and programming concepts directly into the query language. Quel is an old language, predating SQL. Unlike SQL or D, which trace their roots to relational algebra, Quel is strongly influenced by tuple calculus. While Quel's share of active databases is minor, it still plays a prominent role in legacy systems.

Formal Roots

Most formal definitions of databases are broad. For example, Elmarsi & Navathe define a database as "a collection of related data" (Elmarsi & Navathe, 2004, p. 4). When most people use the term database, they are actually referring to a specific type of database: the relational database. Relational databases were first formalized in 1970 by Dr. EF Codd (Codd, 1970) and since then have become the standard format for databases. Relational databases have all but supplanted the hierarchical and network databases that predated them. More recently, there have been attempts to integrate the concepts of objects with databases, with mixed results.

Relational databases rest on the theory of relational algebra and relational calculus. These two theories were later proven to be equivalent (Klug, 1982), in the sense that any expression in one can be rewritten as an expression in the other that returns the same results. Relational algebra is a declarative language that describes data in terms of relations and operations on those relations. The basic unit of relational algebra are relations. Relations are operated on by relational operators to form new relations. Six relational operators are sufficient to express any operation in relational algebra (Elmsari & Navathe, p. 163). These operators are:

Select
Project
Cartesian Product
Union
Difference
Rename

Other operations have been added for notational simplicity, these include the various join conditions and the intersection operator. Still other operations extend the basic set theory to provide additional functionality, such as the aggregate operators sum, maximum, and average.

In contrast, relational calculus has not played as prominent a role as relational algebra in the formulation of databases. Relational calculus is more abstract than relational algebra: it serves to define a result independent of a means to retrieve that result.

Example: D

Despairing of SQL's departure from relational theory, Date and Darwin have proposed a series of specifications for query languages that are truly relational. (While beyond the scope of this presentation, D has two other goals. It seeks to seamlessly integrate programming concepts within the query language and it seeks to natively support objects.) Date and Darwin state that any query language that meets their specifications is called 'D.' They also developed an actual implementation of D dubbed 'Tutorial D.' It differs from SQL in several respects:

Its syntax and vocabulary closely adheres to relational algebra notation.
Relations (tables) are sets, not multi-sets. Thus duplicates are not allowed, nor can attributes have an order.
Every operation returns a relation. Results can be freely assigned to new relations or nested anywhere in other operations.
Relations are fully normalized, null values are not allowed.

Only one database uses Tutorial D: Rel. Rel is still in alpha.

Example: Quel

Quel is another fully relational query language and actually predates SQL. Quel is based on relational calculus rather than relational algebra. Quel uses a more consistent syntax and provides seamless support for aggregate operations.

The following examples serve to distinguish Quel from SQL.

	SQL	Quel
Define	SQL Create	Quel Create
Populate	SQL Insert	Quel Append
List	SQL Select	Quel Retrieve
Summarize	SQL Totals	Quel Totals

The Future

Given SQL's massive market share, it is unlikely that anything will completely supplant it. This is especially true considering that most vendors to not use "pure" SQL, but instead add non-standard extensions to their query languages. This is a one directional process though. If standard SQL deviates from the relational algebra roots that spawned it, no vendor can return to those roots and still remain compliant with standard SQL. While non-SQL query languages could possibly gain a niche as teaching tools or legacy systems, it is unlikely they will gain widespread acceptance.

The most promising source of future development in query languages is one not yet mentioned: Query By Example (QBE). QBE allows users to specify their queries through a graphical user interface. While it can be debated whether QBE is truly a new query language or simply new interface that automatically generates queries in existing query languages, there is little debate that allowing users to specify their queries graphically is a large improvement in usability.

Web Resources

An example of a database in quel and sql:
http://rvcc2.raritanval.edu/~jsulliva/Database/weekly05.html

Ingres V8 Reference Manual:
http://www.cs.fit.edu/fitonly/ingres2.html

The Third Manifesto:
http://www.thethirdmanifesto.com/

Rel, An Implementation of Date and Darwen's “Tutorial D”
http://dbappbuilder.sourceforge.net/Rel.html

Publications

Aho, A. and Ullman, J, "Univerality of Data Retrieval Languages, " Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of Programming Languages (1979).

Codd, E.F., “A Relational Model for large Shared Data Banks,” Communications of the ACM, Vol. 13, No. 7 (June 1970).

Date, C. J., “A Critique of the SQL Database Language, ” ACM SIGMOD Record, 14(3) (November 1984).

Date, C.J. and Darwen, Hugh, Foundation for Object/Relational Databases – The Third Manifesto , Second Edition, Addison Wesley (2004).

Date, C.J. and Darwen, Hugh, Foundation for Future Database Systems: The Third Manifesto , First Edition, Addison Wesley (1998).

Darwen, Hugh and Date, CJ, “The Third Manifesto,” SIGMOD Record, Vol 24, No 1 (March 1995).

Elmasri, Ramez and Navathe, Shamkant, Fundamentals of Database Systems , Fourth Edition, Addison Wesley (2004). See generally bibliography at the end of chapters 6 and 8.

Klug, A., "Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions," Journal of the Association of Computing Machines, Vol. 29, No. 3 (July 1982)

Stonebraker, M., Wong, E., and Kreps, P, “Design and implementation of INGRES,” CM Transactions on Database Systems, 1(3) (1976).