QT-selectors

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.

Find subassemblies (S) used by more than one assembly (A):

• [S] quant (#>1)A in PartOf

(Answer: screw, which is used by two assemblies, cover and fixture.)

Find subassemblies used by more than one assembly in quantities (Q) of 2:

• [S] quant (#>1)A where Q=2 in PartOf

(Answer: screw, again.)

(Compare the T-selector which finds subassemblies used in quantities of 2:

• [S] where Q=2 in PartOf

Answer: screw, plug, connector.)

Find subassemblies used by an even number of assemblies:

• [S] quant (# mod 2 = 0)A in PartOf

(Answer: screw, yet again.)

Find quantities which have at least one subassembly of two assemblies:

• [Q] quant (#>=1)S, (#=2)A in PartOf

(Answer: 2, which applies to screw in both cover and fixture.)

On the other hand,

• [Q] quant (#=2)A in PartOf

gives 1 (applies to wallplug through two different subassemblies) and 2 (above).
And

• [Q] quant (#=2)A, (#>=1)S in PartOf

gives an empty result.

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

• T. H. Merrett "The Extended Relational Algebra, A Basis for Query Languages" Databases: Improving Usability and Responsiveness 1978 Academic Press pp.99-128

• T. H. Merrett "Aldat: a Retrospective on a Work in ProgresS" Information Systems 32(4),2007.

• T. H. Merrett "Database programming".

Links

Aldat, Aldat Relational Algebra