Complexity of Views: Tree and Cyclic Schemas
Oded Shmueli, Alon Itai · SIAM Journal on Computing · 1987
In relational databases a view definition is a query against the database, and a view materialization is the result of applying the view definition to the current database. A view materialization over a database may change as relations in the database undergo modifications. Several problems concerning views are considered, many of which are shown to be hard (NP-complete or even $\Sigma _2^p $-complete). Each problem was treated for general databases and for the much simpler tree databases (also called acyclic databases). View related problems over fixed schemas, in which only the data is allowed to vary, were examined. Methods to handle this case were presented; their complexity is polynomial: for tree schemas the degree of the polynomial is independent of the schema structure while for cyclic schemas the degree depends on the schema structure. These methods may present a practical possibility for dynamic view maintenance.