Materialization and Incremental Update of Path Information

We consider the problem of efficiently processing recursive path queries in deductive database systems, and propose a semi-materialized encoding structure as an attractive approach that provides a balance between efficiency of retrieval and feasibility of storage. We also present incremental algorithms that enable the effects of updates to the underlying database to be reflected in the materialized information. Performance simulations indicate that the techniques presented in this paper can significantly speed the processing of path queries at an acceptable level of storage overhead.