Abstract
Materialized views, a rdbms silver bullet, demonstrate its efficacy in many applications, especially as a data warehousing/decison support system tool. The pivot of playing materialized views efficiently is view selection. Though studied for over thirty years in rdbms, the selection is hard to make in the context of xml databases, where both the semi-structured data and the expressiveness of xml query languages add challenges to the view selection problem. We start our discussion on producing minimal xml views (in terms of size) as candidates for a given workload (a query set). To facilitate intuitionistic view selection, we present a view graph (called vcube) to structurally maintain all generated views. By basing our selection on vcube for materialization, we propose two view selection strategies, targeting at space-optimized and space-time tradeoff, respectively. We built our implementation on top of Berkeley DB XML, demonstrating that significant performance improvement could be obtained using our proposed approaches.
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
Amer-Yahia, S., Cho, S., Lakshmanan, L.V.S., Srivastava, D.: Minimization of tree pattern queries. In: SIGMOD (2001)
Amer-Yahia, S., Koudas, N., Marian, A., Srivastava, D., Toman, D.: Structure and content scoring for XML. In: VLDB (2005)
Amer-Yahia, S., Lakshmanan, L.V.S., Pandit, S.: FleXPath: Flexible structure and full-text querying for XML. In: SIGMOD (2004)
Balmin, A., Özcan, F., Beyer, K.S., Cochrane, R., Pirahesh, H.: A framework for using materialized XPath views in XML query processing. In: VLDB (2004)
Baralis, E., Paraboschi, S., Teniente, E.: Materialized views selection in a multidimensional database. In: VLDB (1997)
Chirkova, R., Halevy, A.Y., Suciu, D.: A formal perspective on the view selection problem. In: VLDB (2001)
Fan, W., Geerts, F., Jia, X., Kementsietsidis, A.: Rewriting regular xpath queries on xml views. In: ICDE (2007)
Gribble, S.D., Halevy, A.Y., Ives, Z.G., Rodrig, M., Suciu, D.: What can database do for peer-to-peer? In: WebDB (2001)
Gupta, H.: Selection of views to materialize in a data warehouse. In: ICDT (1997)
Gupta, H., Mumick, I.S.: Selection of views to materialize under a maintenance cost constraint. In: ICDT (1999)
Harinarayan, V., Rajaraman, A., Ullman, J.D.: Implementing data cubes efficiently. In: SIGMOD Conference (1996)
Hopcroft, J.E., Ullman, J.D.: Set merging algorithms. SIAM J. Comput. 2(4) (1973)
Karloff, H.J., Mihail, M.: On the complexity of the view-selection problem. In: PODS (1999)
Kossmann, D.: The state of the art in distributed query processing. ACM Comput. Surv. 32(4) (2000)
Lakshmanan, L.V.S., Wang, H., Zhao, Z.J.: Answering tree pattern queries using views. In: VLDB (2006)
Mandhani, B., Suciu, D.: Query caching and view selection for XML databases. In: VLDB (2005)
Miklau, G., Suciu, D.: Containment and equivalence for an XPath fragment. In: PODS (2002)
Mumick, I.S., Quass, D., Mumick, B.S.: Maintenance of data cubes and summary tables in a warehouse. In: SIGMOD Conference (1997)
Polyzotis, N., Garofalakis, M.N., Ioannidis, Y.E.: Selectivity estimation for xml twigs. In: ICDE (2004)
Sawires, A., Tatemura, J., Po, O., Agrawal, D., Abbadi, A.E., Candan, K.S.: Maintaining XPath views in loosely coupled systems. In: VLDB (2006)
Sawires, A., Tatemura, J., Po, O., Agrawal, D., Candan, K.S.: Incremental maintenance of path expression views. In: SIGMOD Conference (2005)
Tang, N., Yu, J.X., Özsu, M.T., Choi, B., Wong, K.-F.: Multiple materialized view selection for XPath query rewriting. In: ICDE (2008)
Wang, W., Jiang, H., Lu, H., Yu, J.X.: Bloom histogram: Path selectivity estimation for xml data with updates. In: VLDB (2004)
Xu, W., Özsoyoglu, Z.M.: Rewriting XPath queries using materialized views. In: VLDB (2005)
Yang, J., Karlapalem, K., Li, Q.: Algorithms for materialized view design in data warehousing environment. In: VLDB (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tang, N., Yu, J.X., Tang, H., Özsu, M.T., Boncz, P. (2009). Materialized View Selection in XML Databases. In: Zhou, X., Yokota, H., Deng, K., Liu, Q. (eds) Database Systems for Advanced Applications. DASFAA 2009. Lecture Notes in Computer Science, vol 5463. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00887-0_55
Download citation
DOI: https://doi.org/10.1007/978-3-642-00887-0_55
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00886-3
Online ISBN: 978-3-642-00887-0
eBook Packages: Computer ScienceComputer Science (R0)