An Approximation-Aware Algebra for XML Full-Text Queries

XQuery Full-Text is the proposed standard language for querying XML documents using either standard or full-text conditions; while full-text conditions can have a boolean or a ranked semantics, standard conditions must be satisfied for an element to be returned. This paper proposes a more general formal model that considers structural, value-based and full-text conditions as desiderata rather than mandatory constraints. The goal is achieved defining a set of relaxation operators that, given a path expression or a selection condition, return a set of relaxed path expressions or selection conditions. Algebraic approximated operators are defined for representing typical queries and returns either elements that perfectly respect the conditions and elements that answer to a relaxed version of the original query. A score reflecting the level of satisfaction of the original query is assigned to each result of the relaxed query.