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):
- [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,