The formal framework of the Hyper View system

Abstract

In this report, we introduce the graph rewriting formalism on which the HyperView System is based. We first present a data model for clustered graphs and our notion of graph schemata and graph layers. Then we formalize our concept of nondeleting typed graph rewriting rules with application conditions on attributes based on the Algebraic Single Push Out Approach to graph transformation and present the construction of the derived graph resulting from applying a rule. The main contribution of this report is the formalization of an efficient strategy for materializing HyperViews based on demand-driven rule activation. We introduce the notion of an oracle against which queries in form of graph patterns can be posed. We show how to combine the rule set of a HyperView with an oracle to form a more powerful oracle that materializes this HyperView as a response to queries against it. Finally we treat the problem of avoiding the introduction of redundancies in view graphs by reusing already materialized graph elements.