Incremental Maintenance for Materialized Views over

Semistructured data is not strictly typed like relational or object-oriented data and may be irregular or incom-plete. It often arises in practice, e.g., when heteroge-neous data sources are integrated or data is taken from the World Wide Web. Views over semistructured data can be used to filter the data and to restructure (or pro-vide structure to) it. To achieve fast query response time, these views are often materialized. This paper proposes an incremental maintenance algorithm for materialized views over semistructured data. We use the graph-based data model OEM and the query language Lorel, devel-oped at Stanford, as the framework for our work. our algorithm produces a set of queries that compute the up-dates to the view based upon an update of the source. We develop an analytic cost model and compare the cost of executing our incremental maintenance algorithm to that of recomputing the view. We show that for nearly all types of database updates, it is more efficient to ap-ply our incremental maintenance algorithm to the view than to recompute the view from the database, even when there are thousands of updates.