language: en

Incremental View Maintenance for Active Documents

Serge Abiteboul Pierre Bourhis ? Bogdan Marinoiu
INRIA Orsay ? and University Paris Sud
rstname.lastname@inria.fr July 23, 2007

Abstract In this paper, we develop algorithmic datalogbased foundations for the incremental processing of tree-pattern queries over active documents, i.e. document with incoming streams of data. We dene query satisability for such documents based on a logic with 3-values: true, false forever, and false for now. Also, given an active document and a query, part of the document (and in particular, some incoming streams) may become irrelevant for the query of interest. We introduce an incremental algorithm for detecting such useless data and streams, essential for implementing garbage collection. We also provide complexity analysis for the problems we study.

Keywords XML, active XML, active document, incremental evaluation, view maintenance, tree-pattern query, datalog, monitoring, stream processing

1 Introduction