We have investigated a new model for cardinal direction information which works with points, lines, line segments and extended regions. We have investigated the use of this model in spatial database management systems based on constraint technology. We have studied the composition operation in this model and proposed polynomial time algorithms for the consistency checking problem. This work is led by Spiros Skiadopoulos.
We are interested in precise characterizations of classes of tractable constraints. In 1995 we studied the problems of deciding consistency and performing variable elimination for Horn disjunctive linear constraints. Horn disjunctive linear constraints are disjunctions of weak linear inequalities and disequations with at most one inequality per disjunction. This new class of constraints extends the class of generalized linear constraints originally studied by Lassez and McAloon. The most important result here is that deciding consistency of a set of constraints in this class can be done in PTIME. This has also been proved independently by Peter Jonsson and Christer Backstrom.
Together with David Cohen, Peter Jeavons and Peter Jonsson we have extended the above PTIME result and showed that a certain intuitive property called independence is sufficient to ensure tractability of a general form of disjunctive constraints. Many previous results on tractable classes of disjunctive constraints can now be seen to be instances of our general theory. More recently Matthias Broxvall, Peter Jonsson and Jochen Renz have extended this result and showed that independence is also necessary. All of us think that these results are very nice!
Kostas Stergiou and Manolis Koubarakis have extended the framework of simple temporal problems studied originally by Dechter, Meiri and Pearl to consider disjunctions of the form X1-Y1 <= R1 OR X2-Y2 <= R2 OR ... OR Xn-Yn <= Rn where X1, X2, ...,Xn, Y1, Y2, ...,Yn are variables ranging over the real numbers, R1, R2, ...,Rn are real constants, and n >= 1.
We have implemented four progressively more efficient algorithms for the consistency checking problem for this class of temporal constraints: backtracking, backjumping, forward checking and forward checking with backjumping. We have also implemented the fail first heuristic in conjunction with forward checking and forward checking with backjumping. We have partially ordered the above algorithms according to the number of visited search nodes and the number of performed consistency checks. To achieve this result, we modified slightly the methodology and proofs of Kondrak and van Beek, for binary constraint satisfaction problems, although our problem is non-binary. We have also studied the performance of the above algorithms experimentally using randomly generated sets of data. Finally, we have carried out a series of experimental results on the location of the hard region. The results show that hard problems occur at a critical value of the ratio of disjunctions to variables.
In the Ph.D. thesis of Manolis Koubarakis (National Technical University of Athens, 1994) we developed the scheme of indefinite constraint databases and concentrated on instances of this scheme where the constraints are temporal. Our work starts from the premise that an important requirement of advanced temporal applications (e.g., planning and scheduling) is the ability to deal with definite, indefinite, finite and infinite temporal information. We proposed that a combination of classical relational databases and temporal constraint networks offers a powerful framework which addresses the database needs of these applications. We have also studied the complexity of query processing in such databases.
In this context we have also studied the complexity of query processing in the case that the constraints belong to various subclasses of linear constraints.