• Articles • Previous Articles     Next Articles

Accomplishing Deterministic XML Query Optimization

Dun-Ren Che   

  1. Department of Computer Science, Southern Illinois University, Carbondale, IL 62901, U.S.A.
  • Received:2004-04-07 Revised:2004-10-13 Online:2005-05-10 Published:2005-05-10

As the popularity of XML (eXtensible Markup Language) keeps growingrapidly, the management of XML compliant structured-document databaseshas become a very interesting and compelling research area. Queryoptimization for XML structured-documents stands out as one of the mostchallenging research issues in this area because of the much enlargedoptimization (search) space, which is a consequence of the intrinsiccomplexity of the underlying data model of XML data. We thereforepropose to apply deterministic transformations on query expressions tomost aggressively prune the search space and fast achieve a sufficientlyimproved alternative (if not the optimal) for each incoming queryexpression. This idea is not just exciting but practically attainable.This paper first provides an overview of our optimization strategy, andthen focuses on the key implementation issues of our rule-basedtransformation system for XML query optimization in a databaseenvironment. The performance results we obtained from experimentationshow that our approach is a valid and effective one.

Key words: Virtual technology; test program migration; IC test software environment;

[1] Fernandez M F et al. SilkRoute: Trading betweenrelations and XML. Computer Networks 2000, 33(1-6): 723--745.

[2] Florescu D, Kossmann D. Storing and querying XML datausing an RDMBS. IEEE Data Engineering Bulletin 1999, 22(3): 27--34.

[3] Shanmugasundaram J, Tufte K, He G et al. Relational databases for querying XML documents: Limitationsand opportunities. In Proc. VLDB 1999, pp.302--314.

[4] Bohannon P, Freire J, Roy P, Simeon J. From XML schema torelations: A cost-based approach to XML storage. In Proc.18th Int. Conf. Data Engineering (ICDE) 2002, pp.64--75.

[5] 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.

[6] Surjanto B, Ritter N, Loeser H. XML content management basedon object-relational database technology. In Proc. The 1st Int.Conf. Web Information Systems Engineering (WISE) Hong Kong, June2000, pp.70--79.

[7] McHugh J, Abiteboul S, Goldman R et al. Lore:A database management system for semistructured data. SIGMODRecord Sep. 1997, 26(3): pp.54--66.

[8] Che D, Aberer K. A heuristics-based approach to queryoptimization in structured document databases. In Proc. 1999Int. Database Engineering & Application Symposium Montreal, Canada,Aug. 2--4, 1999, pp.24--33.

[9] Salminen A et al. PAT expressions: An algebra for textsearch. Acta Linguistica Hungarica 1994, 41(1): 277--306.

[10] Bǒhm K, Aberer K, Neuhold E J, Yang X. Structureddocument storage and refined declarative and navigational access mechanisms inHyperStorM. The VLDB Journal Nov. 1997, 6(4): 296--311.

[11] Clark J, DeRose S. XML path language (Xpath) version 1.0.http://www.w3.org/TR/1999/REC-xpath-19991116

[12] 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/

[13] Che D, Aberer K, ǒzsu M T. Query Optimization in XMLStructured-Document Database Systems (Manuscript in preparation for -The VLDBJournal ).

[14] Che D. Implementation issues of a deterministic transformationsystem for structured document query optimization. In Proc. 2003Int. Database Engineering & Application Symposium Hong Kong, July16-18-4, 2003, pp.268--277.

[15] McHugh J, Widom J. Query optimization for XML. In Proc.VLDB Edinburgh, Scotland, Sep. 1999, pp.315--326.

[16] Fernandez M F, Suciu D. Optimizing regular pathexpressions using graph schemas. In Proc. 14th Int. Conf. DataEngineering Orlando, USA, Feb. 23--27, 1998, pp.14--23.

[17] Flesca S, Furfaro F, Masciari E. On the minimization ofXpath queries. In Proc. VLDB 2003, pp.153--164.

[18] Amer-Yahia S, Cho S, Lakshmanan L, Srivastava D.Minimization of tree pattern queries. In Proc. ACM Conf. Managementof Data (SIGMOD) 2001, pp.497--508.

[19] Wood P T. Containment for Xpath fragments under DTDconstraints. In Proc. 9th Int. Conf. Database Theory Jan. 2003,pp.300--314.

[20] Kwong A, Gertz M. Schema-based optimization of Xpathexpressions. Technical Report, Univ. Dept. ComputerScience, 2001.

[21] Bǒhm K, Aberer K, ǒzsu M T, Gayer K. Queryoptimization for structured documents based on knowledge on the documenttype definition. In Proc. IEEE Int. Forum on Research and TechnologyAdvances in Digital Libraries (ADL'98) Santa Barbara,April 22--24, 1998, pp.196--205.
[1] Wang Xiaoming; Yang Qiaolin;. Using Virtual ATE Model to Migrate Test Programs [J]. , 1995, 10(4): 289-297.
Full text



[1] Lian Lin; Zhang Yili; Tang Changjie;. A Non-Recursive Algorithm Computing Set Expressions[J]. , 1988, 3(4): 310 -316 .
[2] Yao Rong; Kang Tai; Chen Tinghuai;. Algorithms for the Determination of Cutsets in a Hypergraph[J]. , 1990, 5(1): 41 -46 .
[3] Han Jianchao; Shi Zhongzhi;. Formalizing Default Reasoning[J]. , 1990, 5(4): 374 -378 .
[4] Cai Shijie; Zhang Fuyan;. A Fast Algorithm for Polygon Operations[J]. , 1991, 6(1): 91 -96 .
[5] Fei Xianglin; Liao Lei; Wang Hezhen; Wang Chengzao;. Structured Development Environment Based on the Object-Oriented Concepts[J]. , 1992, 7(3): 193 -201 .
[6] Zhou Yong; Tang Zesheng;. Constructing Isosurfaces from 3D Data Sets Taking Account of Depth Sorting of Polyhedra[J]. , 1994, 9(2): 117 -127 .
[7] Wang Hui; Liu Dayou; Wang Yafei;. Sequential Back-Propagation[J]. , 1994, 9(3): 252 -260 .
[8] Cao Cungen;. Expansion Nets and Expansion Processes of Elementary Net Systems[J]. , 1995, 10(4): 325 -333 .
[9] Yao Shu; Zhang Bo;. Situated Learning of a Behavior-Based Mobile Robot Path Planner[J]. , 1995, 10(4): 375 -379 .
[10] Hu Shimin;. A Subdivision Scheme for Rational Triangular Bézier Surfaces[J]. , 1996, 11(1): 9 -16 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved