View disassembly: A rewrite that extracts portions of views

摘要

We explore a new form of view rewrite called view disassembly. The objective is to rewrite views in order to "remove" certain sub-views (or unfoldings) of the view. This becomes pertinent for complex views which may be defined over other views and which may involve union. Such complex views arise necessarily in environments such as data warehousing and mediation over heterogeneous databases. View disassembly can be used for view and query optimization, preserving data security, making use of cached queries and materialized views, and view maintenance. We provide computational complexity results of view disassembly. One question is whether the unfoldings to be removed effectively cover the view, meaning that the disassembled view is effectively the empty view, evaluating to the empty table. We illustrate the complexity to determine when a collection of unfoldings cover the view definition. The problem is NP-hard with respect to the number of unfoldings to remove, but not with respect to the size (complexity) of the view definition. We next consider rewrites optimal in the size of the rewritten (disassembled) view. We prove that this task is NP-hard for a special class of views, but this time NP-hard in a worse way: it is NP-hard this time with respect to the size of the view definition in addition to the number of unfoldings to be removed. In general, we suspect the problem is computationally even harder, and we show that the general problem is in Π_2~p. However, we provide good news too. We identify a pertinent class of unfoldings for which the removal of such unfoldings always results in a simpler disassembled view than the original view itself. We also develop an algorithm that finds rewrites equivalent to the disassembled view which are, in a sense, locally optimal. The algorithm establishes a cover completion by finding a (minimal) collection of unfoldings of the view that, along with the unfoldings to be removed, covers the original view. This approach is effectively tractable, unlike the search for globally, or absolutely, optimal rewrites. Furthermore, we show that these cover-completion rewrites are preferable to absolutely optimal rewrites in many ways.