A case study of the difficulty of quantifier elimination in constraint databases: the alibi query in moving object databases - Computer Science > Logic in Computer ScienceReportar como inadecuado




A case study of the difficulty of quantifier elimination in constraint databases: the alibi query in moving object databases - Computer Science > Logic in Computer Science - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: In the constraint database model, spatial and spatio-temporal data are storedby boolean combinations of polynomial equalities and inequalities over the realnumbers. The relational calculus augmented with polynomial constraints is thestandard first-order query language for constraint databases. Although theexpressive power of this query language has been studied extensively, thedifficulty of the efficient evaluation of queries, usually involving some formof quantifier elimination, has received considerably less attention. Theinefficiency of existing quantifier-elimination software and the intrinsicdifficulty of quantifier elimination have proven to be a bottle-neck for forreal-world implementations of constraint database systems. In this paper, wefocus on a particular query, called the \emph{alibi query}, that asks whethertwo moving objects whose positions are known at certain moments in time, couldhave possibly met, given certain speed constraints. This query can be seen as aconstraint database query and its evaluation relies on the elimination of ablock of three existential quantifiers. Implementations of general purposeelimination algorithms are in the specific case, for practical purposes, tooslow in answering the alibi query and fail completely in the parametric case.The main contribution of this paper is an analytical solution to the parametricalibi query, which can be used to answer this query in the specific case inconstant time. We also give an analytic solution to the alibi query at a fixedmoment in time. The solutions we propose are based on geometric argumentationand they illustrate the fact that some practical problems require creativesolutions, where at least in theory, existing systems could provide a solution.



Autor: Bart Kuijpers, Walied Othman, Rafael Grimson

Fuente: https://arxiv.org/







Documentos relacionados