The View Selection Problem for Regular Path Queries
The view selection problem consists of finding a set of views to materialize that can answer the given set of workload queries and is optimal in some sense. In this paper we study the view selection problem for regular path queries over semistructured dat
- PDF / 419,324 Bytes
- 12 Pages / 430 x 660 pts Page_size
- 65 Downloads / 180 Views
Abstract. The view selection problem consists of finding a set of views to materialize that can answer the given set of workload queries and is optimal in some sense. In this paper we study the view selection problem for regular path queries over semistructured data and two specific view-based query rewriting formalisms, namely single-word and arbitrary regular rewritings. We present an algorithm that for a given finite set of workload queries, i.e. for a set of regular languages, computes a set of views that can answer every query in the workload and has minimal possible cardinality. If, in addition, a database instance is given then one can construct a viewset such that its size, i.e. amount of space required to store results, is minimal on the database instance. Keywords: view selection problem, regular path queries, semigroups of regular languages.
1
Introduction
The problem of view based query processing plays an important role in many database applications, including information integration, query optimization, mobile computing and data warehousing. In its general form, the problem is stated as follows. Given a query over database schema and a set of materialized views over the same schema (i.e. a set of queries with precomputed answers – view extensions), is it possible to answer the query, completely or partially, using answers to the views? This question has been intensively studied for various data models and different assumptions on views semantic (e.g., [13,11,5,20]). The main approaches to view based query processing are query rewriting and query answering (see [13] for a survey). In query rewriting approach, given a query Q written in language Q, and a set of views V that are written in language V one should construct a rewriting R, in language R, such that Q(D) = R ◦ V(D) for each database instance D. It is worth noticing that query rewriting does not depend on view extensions and can be thought as an algorithm that describes how result of the query can be computed form the views. In contrast, query answering consists of direct computing of all answers to Q from the view extensions. The
This work has been supported in part by the Russian Federal Agency for Science and Innovations under grant 02.514.11.4078 and by the Russian Foundation for Basic Research under grant 08-01-00882-a.
E.S. Laber et al. (Eds.): LATIN 2008, LNCS 4957, pp. 121–132, 2008. c Springer-Verlag Berlin Heidelberg 2008
122
S. Afonin
connection between query rewriting and query answering studied in [20, 4]. In this paper we follow query rewriting approach and we shall say that a viewset V answers a query Q if there exists a rewriting of Q. The ability to answer a query using only the answers to views can significantly decrease query evaluation time. For example, in a mobile computing environment the application does not need to access the network in order to process user’s query. If the views can not completely answer a query, they can, nevertheless, speed up query processing, because some computations needed for the query p
Data Loading...
