Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 4708))
Included in the following conference series:
1266Accesses
Abstract
Answering queries using views is the problem which examines how to derive the answers to a query when we only have the answers to a set of views. Constructing rewritings is a widely studied technique to derive those answers. In this paper we consider the problem of existence of rewritings in the case where the answers to the views uniquely determine the answers to the query. Specifically, we say that a view set\({\cal{V}}\)determines a queryQ if for any two databasesD1,D2 it holds:\({\cal{V}} (D_1) = {\cal{V}} (D_2)\) impliesQ(D1) = Q(D2). We consider the case where query and views are defined by conjunctive queries and investigate the question: If a view set\({\cal{V}}\) determines a queryQ, is there an equivalent rewriting ofQ using\({\cal{V}}\)? We present here interesting cases where there are such rewritings in the language of conjunctive queries. Interestingly, we identify a class of conjunctive queries, CQpath, for which a view set can produce equivalent rewritings for “almost all” queries which are determined by this view set. We introduce a problem which relates determinacy to query equivalence. We show that there are cases where restricted results can carry over to broader classes of queries.
This is a preview of subscription content,log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abiteboul, S., Duschka, O.M.: Complexity of answering queries using materialized views. In: PODS (1998)
Afrati, F., Li, C., Ullman, J.D.: Generating efficient plans using views. In: SIGMOD (2001)
Afrati, F., Li, C., Ullman, J.D.: Using views to generate efficient evaluation plans for queries. JCSS (to appear)
Afrati, F.N., Li, C., Mitra, P.: Rewriting queries using views in the presence of arithmetic comparisons. Theor. Comput. Sci. 368(1-2) (2006)
Agrawal, S., Chaudhuri, S., Narasayya, V.R.: Automated selection of materialized views and indexes in sql databases. In: Proc. of VLDB (2000)
Bayardo Jr., R.J., et al.: Infosleuth: Semantic integration of information in open and dynamic environments (experience paper). In: SIGMOD (1997)
Calvanese, D., De Giacomo, G., Lenzerini, M., Vardi, M.Y.: Lossless regular views. In: PODS, ACM, New York (2002)
Calvanese, D., De Giacomo, G., Lenzerini, M., Vardi, M.Y.: View-based query query processing: On the relationship between rewriting, answering and losslessness. In: International Conference on Database Theory (ICDT) (2005)
Chandra, A.K., Merlin, P.M.: Optimal implementation of conjunctive queries in relational data bases. In: STOC (1977)
Chaudhuri, S., Krishnamurthy, R., Potamianos, S., Shim, K.: Optimizing queries with materialized views. In: ICDE (1995)
Chawathe, S.S., et al.: The TSIMMIS project: Integration of heterogeneous information sources. In: IPSJ (1994)
Chekuri, C., Rajaraman, A.: Conjunctive query containment revisited. In: Afrati, F.N., Kolaitis, P.G. (eds.) ICDT 1997. LNCS, vol. 1186, Springer, Heidelberg (1996)
Duschka, O.M., Genesereth, M.R.: Answering recursive queries using views. In: PODS (1997)
Florescu, D., Levy, A., Suciu, D., Yagoub, K.: Optimization of run-time management of data intensive web-sites. In: Proc. of VLDB (1999)
Grumbach, S., Tininini, L.: On the content of materialized aggregate views. In: PODS (2000)
Haas, L.M., Kossmann, D., Wimmers, E.L., Yang, J.: Optimizing queries across diverse data sources. In: Proc. of VLDB (1997)
Halevy, A.Y.: Answering queries using views: A survey. VLDB Journal 10(4)
Ives, Z., Florescu, D., Friedman, M., Levy, A., Weld, D.: An adaptive query execution engine for data integration. In: SIGMOD (1999)
Levy, A., Mendelzon, A., Sagiv, Y., Srivastava, D.: Answering queries using views. In: PODS (1995)
Levy, A., Rajaraman, A., Ordille, J.J.: Querying heterogeneous information sources using source descriptions. In: Proc. of VLDB (1996)
Li, C., Bawa, M., Ullman, J.: Minimizing view sets without losing query-answering power. In: Van den Bussche, J., Vianu, V. (eds.) ICDT 2001. LNCS, vol. 1973, Springer, Heidelberg (2000)
Nash, A., Segoufin, L., Vianu, V.: Determinacy and rewriting of conjunctive queries using views: A progress report. In: Schwentick, T., Suciu, D. (eds.) ICDT 2007. LNCS, vol. 4353, Springer, Heidelberg (2006)
Rajaraman, A., Sagiv, Y., Ullman, J.D.: Answering queries using templates with binding patterns. In: PODS (1995)
Segoufin, L., Vianu, V.: Views and queries: Determinacy and rewriting. In: PODS, ACM Press, New York (2005)
Theodoratos, D., Sellis, T.: Data warehouse configuration. In: Proc. of VLDB (1997)
Ullman, J.D.: Information integration using logical views. In: Afrati, F.N., Kolaitis, P.G. (eds.) ICDT 1997. LNCS, vol. 1186, Springer, Heidelberg (1996)
Author information
Authors and Affiliations
National Technical University of Athens, Greece
Foto Afrati
- Foto Afrati
You can also search for this author inPubMed Google Scholar
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Afrati, F. (2007). Rewriting Conjunctive Queries Determined by Views. In: Kučera, L., Kučera, A. (eds) Mathematical Foundations of Computer Science 2007. MFCS 2007. Lecture Notes in Computer Science, vol 4708. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74456-6_9
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-540-74455-9
Online ISBN:978-3-540-74456-6
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative