zbMATH — the first resource for mathematics

Linear repeating points. (English) Zbl 0989.68036
Kuper, Gabriel (ed.) et al., Constraint databases. Berlin: Springer. 305-314 (2000).
This survey article by Pierre Wolper starts with giving some motivation as to what one has to bear in mind when searching for an appropriate representation of time in databases. Then one possible approach in this area is presented, namely the method of linear repeating points introduced by Kabanza, Stévenne, and Wolper in 1990. This approach can be characterized as follows:
Time is considered as the set of integers \({\mathbb Z}.\)
This approach can deal with any number of time attributes. However, typically, one will only consider 1 (= points) or 2 (= time interval) such attributes.
The basic notion to restrict the possible values that a time attribute may take is a linear repeating point (= lrp, for short). An lrp is simply an expression of the form \(c + k n\) for fixed constants \(c\) and \(k\), s.t. \(n\) may take any value from \({\mathbb Z},\) e.g., the lrp “\(2 + 3 n\)” represents the set \(\{ \dots, -7,-4, -1, 2, 5, 8, \dots\}\).
As a further restriction, linear equalities and inequalities between time attributes may be used, e.g., “\(X_i \leq 2 X_j + 10\)” means, that the \(i\)-th time attribute has to be less than or equal to twice the \(j\)-th time attribute plus 10. As for the expressiveness of these lrps with linear equalities/inequalities, two important facts are recalled. First, this approach is equivalent (in a sense made precise in this article) to Presburger arithmetic and, second, it is also equivalent to finite automata. For the latter equivalence, the construction by Boudet and Comon (1996) of a finite automaton corresponding to a linear equation is briefly sketched. Moreover, this article provides a good introduction to complexity results for the evaluation of first-order queries dealing with time. No matter what formalism one ultimately uses to represent values of time attributes, certain elementary operations (like union, intersection, negation, projection, …) and tests (like emptiness of a relation or of its complement) are crucial. In case of full Presburger arithmetics, the above operations are trivial but the tests are highly complex. For lrps with linear equalities/inequalities, this article recalls all known results on the complexity of the above operations and tests. In fact, apart from negation and testing the emptiness of the complement relation, all these operations and tests can be carried out in polynomial time. Finally, also the complexity results in case of deterministic or non-deterministic automata are briefly recalled. In summary, this is a well-written and interesting to read survey article on a possible approach to deal with time in databases. The author recalls the most important notions and results of this approach. He thereby pays particular attention to providing sufficient motivation to the reader. Moreover, he gives a good sketch of a nice construction relating this approach to finite automata.
For the entire collection see [Zbl 0935.00022].
68P15 Database theory