Abstract
As the popularity of XML (eXtensible Markup Language) keeps growing rapidly, the management of XML compliant structured-document databases has become a very interesting and compelling research area. Query optimization for XML structured-documents stands out as one of the most challenging research issues in this area because of the much enlarged optimization (search) space, which is a consequence of the intrinsic complexity of the underlying data model of XML data. We therefore propose to apply deterministic transformations on query expressions to most aggressively prune the search space and fast achieve a sufficiently improved alternative (if not the optimal) for each incoming query expression. This idea is not just exciting but practically attainable. This paper first provides an overview of our optimization strategy, and then focuses on the key implementation issues of our rule-based transformation system for XML query optimization in a database environment. The performance results we obtained from experimentation show that our approach is a valid and effective one.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Fernandez M F et al. SilkRoute: Trading between relations and XML. Computer Networks, 2000, 33(1-6): 723–745.
Florescu D, Kossmann D. Storing and querying XML data using an RDMBS. IEEE Data Engineering Bulletin, 1999, 22(3): 27–34.
Shanmugasundaram J, Tufte K, He G et al. Relational databases for querying XML documents: Limitations and opportunities. In Proc. VLDB, 1999, pp.302–314.
Bohannon P, Freire J, Roy P, Simeon J. From XML schema to relations: A cost-based approach to XML storage. In Proc. 18th Int. Conf. Data Engineering (ICDE), 2002, pp.64–75.
Klettke M, Meyer H. XML and object-relational database systems — Enhancing structural mappings based on statistics. In Proc. Int. Workshop on the Web and Databases (WebDB), Dallas, May 2000, pp.63–68.
Surjanto B, Ritter N, Loeser H. XML content management based on object-relational database technology. In Proc. the 1st Int. Conf. Web Information Systems Engineering (WISE), Hong Kong, June 2000, pp.70–79.
McHugh J, Abiteboul S, Goldman R et al. Lore: A database management system for semistructured data. SIGMOD Record, Sep. 1997, 26(3): pp.54–66.
Che D, Aberer K. A heuristics-based approach to query optimization in structured document databases. In Proc. 1999 Int. Database Engineering & Application Symposium, Montreal, Canada, Aug. 2–4, 1999, pp.24–33.
Salminen A et al. PAT expressions: An algebra for text search. Acta Linguistica Hungarica, 1994, 41(1): 277–306.
Böhm K, Aberer K, Neuhold E J, Yang X. Structured document storage and refined declarative and navigational access mechanisms in HyperStorM. The VLDB Journal, Nov. 1997, 6(4): 296–311.
Clark J, DeRose S. XML path language (XPath) version 1.0. http://www.w3.org/TR/1999/REC-xpath-19991116/
Boag S, Chamberlin D, Fernandez M F et al. XQuery 1.0: An XML query language. http://www.w3.org/TR/2004/WD-xquery-20040723/
Che D, Aberer K, Özsu M T. Query Optimization in XML Structured-Document Database Systems (Manuscript in preparation for {The VLDB Journal}).
Che D. Implementation issues of a deterministic transformation system for structured document query optimization. In Proc. 2003 Int. Database Engineering & Application Symposium, Hong Kong, July 16-18-4, 2003, pp.268–277.
McHugh J, Widom J. Query optimization for XML. In Proc. VLDB, Edinburgh, Scotland, Sep. 1999, pp.315–326.
Fernandez M F, Suciu D. Optimizing regular path expressions using graph schemas. In Proc. 14th Int. Conf. Data Engineering, Orlando, USA, Feb. 23–27, 1998, pp.14–23.
Flesca S, Furfaro F, Masciari E. On the minimization of Xpath queries. In Proc. VLDB, 2003, pp.153–164.
Amer-Yahia S, Cho S, Lakshmanan L, Srivastava D. Minimization of tree pattern queries. In Proc. ACM Conf. Management of Data (SIGMOD), 2001, pp.497–508.
Wood P T. Containment for XPath fragments under DTD constraints. In Proc. 9th Int. Conf. Database Theory, Jan. 2003, pp.300–314.
Kwong A, Gertz M. Schema-based optimization of XPath expressions. Technical Report, Univ. Dept. Computer Science, 2001.
Böhm K, Aberer K, Özsu M T, Gayer K. Query optimization for structured documents based on knowledge on the document type definition. In Proc. IEEE Int. Forum on Research and Technology Advances in Digital Libraries (ADL’98), Santa Barbara, April 22–24, 1998, pp.196–205.
Author information
Authors and Affiliations
Corresponding author
Additional information
Dun-Ren Che is an assistant professor in the Dept. Computer Science, Southern Illinois University at Carbondale, U.S.A. He received his Ph.D. degree in computer science from the Beijing University of Aeronautics and Astronautics, Beijing, China in 1994. Afterwards, he gained several years of postdoctoral research experience in different institutes. His recent research interest covers two major areas: advanced database technology (currently focused on XML database management) and Bioinformatics.
Rights and permissions
About this article
Cite this article
Che, DR. Accomplishing Deterministic XML Query Optimization. J Comput Sci Technol 20, 357–366 (2005). https://doi.org/10.1007/s11390-005-0357-x
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/s11390-005-0357-x