Copyright ©2007 T. H. Merrett

QT-selectors

Wikipedia categories: programming languages, databases

Motivation

Most database languages are query languages, as opposed to general-purpose programming languages. Programming, at least for secondary storage, should include querying. So, in a general-purpose programming language for secondary storage there should be an operator to support arbitrary querying. In a relational language, this operator should support arbitrary querying of a single relation. (Other operators of the relational algebra can be used to assemble such a single relation, if necessary, from various other source relations.)

Overview

In the Aldat programming language for secondary storage, the T-selector is a combination of the projection and selection operators of the classical relational algebra. T stands for tuple, and the selection condition of the T-selector is restricted to acting on a single tuple at a time: it must evaluate to true or false for each individual tuple of the relation. (See the Aldat Relational Algebra.)

The QT-selector adds quantifiers to the T-selector and permits logical conditions to be evaluated over sets of tuples. Together with the T-selector as a special case, it provides a very flexible query capability over the single relation or relational expression that is its operand.

Examples

Here are some QT-selector queries over the relation PartOf, describing an electric wallplug.
PartOf( A S Q )
wallplug cover 1
wallplug fixture 1
cover screw 2
cover plate 1
fixture screw 2
fixture plug 2
plug connector 2
plug mould 1
Find subassemblies (S) used by more than one assembly (A): Find subassemblies used by more than one assembly in quantities (Q) of 2: Find subassemblies used by an even number of assemblies: Find quantities which have at least one subassembly of two assemblies:

Discussion

QT-selectors include one or more quantified attributes, with each attribute preceded by a single quantifier and each quantifier followed by a single attribute. The quantifier is a parenthesized boolean expression, called the quantifier expression. The quantifier expression may be arbitrarily complicated and must contain one or more occurrences of the quantifier symbol, #.

A quantified attribute, such as (#>1)A, is prononced "the number of different values of A is >1".

There is also, not illustrated, a "proportion-of" quantifier symbol to supplement the "number-of" quantifier symbol, #. These two symbols between them capture all the quantifications of predicate logic, and far surpass them. For example, "some" and "all" are easily expressed; so are "exactly 2" and so on.

QT-selectors are read from right to left: first the T-selector condition (after where), if any, is evaluated; then the rightmost quantifier, followed in order, by quantifiers to its left; finally the projection is done on the list of projection attributes.

If a QT-selector has more than one quantified attribute, the expressions are separated from each other by a comma.

The order of the quantified expressions is important: the examples show that (#>=1)S, (#=2)A gives a different result from (#=2)A, (#>=1)S. This is not an error: quantifier order also matters in the Aristotelian quantifiers of predicate logic: (some)x,(all)y : x>y differs from (all)y,(some)x : x>y.

Since the difference between the two examples on (#>=1)S, (#=2)A and (#=2)A, (#>=1)S is hardly apparent in the natural-language (say, English) interpretation of the QT-selectors, natural language is clearly an unreliable medium for query formulation. It is pretty hopeless to attempt to build a natural-language query processor in the absence of a powerful feedback mechanism to confirm with the user what the intended query was.

On the other hand, QT-selectors translate easily into natural language, and most practical queries translate easily from natural language into QT-selectors.

Implementation of any QT-selector can be done in a single pass of its operand relation, once the relation has been sorted on the attributes of the QT-selector, rightmost within next-rightmost within .. within leftmost.

Further Reading

Links

Aldat,
Aldat Relational Algebra,