Technical Report CS0312

Title: Complexity of Views: Tree and Gyclic Schemas
Authors: O. Shmueli and A. Itai
Abstract: 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 to p)-complete). Each problem was treated for general databases and for the much simpler tree databases (also called acyclic database).

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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1984
To the main CS technical reports page

Computer science department, Technion