Demand-Driven Incremental Object Queries
This work addresses the challenge of efficient query processing for dynamic object queries in information systems, offering incremental improvements for applications like distributed algorithms and probabilistic queries.
The paper tackles the problem of efficiently implementing complex, nested object queries that can change arbitrarily, by proposing an automatic method that transforms queries and data into relations and incrementally maintains invariants. The method achieves analyzed complexities and shows significant improvements over prior work in experiments across various applications.
Object queries are essential in information seeking and decision making in vast areas of applications. However, a query may involve complex conditions on objects and sets, which can be arbitrarily nested and aliased. The objects and sets involved as well as the demand---the given parameter values of interest---can change arbitrarily. How to implement object queries efficiently under all possible updates, and furthermore to provide complexity guarantees? This paper describes an automatic method. The method allows powerful queries to be written completely declaratively. It transforms demand as well as all objects and sets into relations. Most importantly, it defines invariants for not only the query results, but also all auxiliary values about the objects and sets involved, including those for propagating demand, and incrementally maintains all of them. Implementation and experiments with problems from a variety of application areas, including distributed algorithms and probabilistic queries, confirm the analyzed complexities, trade-offs, and significant improvements over prior work.