Approximate Streamed Evaluation of XPath under Memory Constraints
Dominik Schwald, Dan Olteanu · 2003
This paper presents techniques for approximate evaluation of regular path queries against XML streams. Querying unbounded XML streams enforces new demands to query evaluators: As shown in [2], the memory needed for answering queries on unbounded XML streams is unbounded as well. Since this is not acceptable for real world applications, an approximate evaluation is thus required. Preliminary research showed that it is necessary to have several different approximation techniques for ensuring ’good’ query answers under memory constraints, because the definition of a ’good’ query answer, depends heavily on the application purpose. E.g. some applications can not accept false positives, but false negatives. The contributions of this paper consists in: (1) Motivating the need for application-sensitive approximate query answering by showing two application scenarios where different approximations are needed. (2) Introducing several approximation techniques and the mean to compose them via a language for approximation techniques called SAL (SPEX Approximation Language). SAL enhances the query evaluator SPEX[12] with the facility of approximate answers to regular path queries on XML streams. Real world application scenarios help to explain the topic throughout the whole paper.