Abstract: Constraint databases that can be described by boolean combinations of polynomial inequalities over the reals have received ample research attention. In particular, the expressive power of first-order logic over the reals, as a constraint database query language, has been studied extensively. The difficulty of the effective evaluation of first-order queries, usually involving some form of quantifier elimination, has been largely neglected. The contribution of this paper is a discussion of various aspects that influence the efficiency of the evaluation of queries expressible in first-order logic over the reals. We emphasize the importance of data structures and their effect on the complexity of quantifier-elimination. We also propose a novel data model that supports data exploration and visualization as well as efficient query evaluation. In this context, we introduce the concept of sample point query. Finally, we show that a particular kind of sample point query cannot be evaluated in polynomial sequential time by means of branching parsimonious procedures.

Abstract: Constraint databases provide the framework for studying query languages with interpreted operations. While early research concentrated mostly on continuous domains (due to applications of CDBs in querying geographical data), the focus has recently switched to discrete domains, such as strings and trees, both ranked an unranked. In this talk I give a survey of recent results on decidable constraints over strings and trees that arise from automatic structures, and of query languages based on such constraints.

Abstract: We automatize the verification of termination, confluence and other properties (safety and liveness) for Event Condition Action rules by combing recent approaches to constraint-based abstraction with query evaluation techniques for constraint data bases. This is joint work with Hassan Ait-Kaci.