Holistic twig joins

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Holistic twig joins: optimal XML pattern matching

Full text

Pdf (1.34 MB)

Source

International Conference on Management of Data archive
Proceedings of the 2002 ACM SIGMOD international conference on Management of data table of contents

Madison, Wisconsin

SESSION: Research sessions: XML II table of contents

Pages: 310 - 321

Year of Publication: 2002

ISBN:1-58113-497-5

Authors

Nicolas Bruno	Columbia University
Nick Koudas	AT&T Labs---Research
Divesh Srivastava	AT&T Labs---Research

Sponsor

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 33, Downloads (12 Months): 210, Citation Count: 151

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/564691.564727 What is a DOI?

ABSTRACT

XML employs a tree-structured data model, and, naturally, XML queries specify patterns of selection predicates on multiple elements related by a tree structure. Finding all occurrences of such a twig pattern in an XML database is a core operation for XML query processing. Prior work has typically decomposed the twig pattern into binary structural (parent-child and ancestor-descendant) relationships, and twig matching is achieved by: (i) using structural join algorithms to match the binary relationships against the XML database, and (ii) stitching together these basic matches. A limitation of this approach for matching twig patterns is that intermediate result sizes can get large, even when the input and output sizes are more manageable.In this paper, we propose a novel holistic twig join algorithm, TwigStack, for matching an XML query twig pattern. Our technique uses a chain of linked stacks to compactly represent partial results to root-to-leaf query paths, which are then composed to obtain matches for the twig pattern. When the twig pattern uses only ancestor-descendant relationships between elements, TwigStack is I/O and CPU optimal among all sequential algorithms that read the entire input: it is linear in the sum of sizes of the input lists and the final result list, but independent of the sizes of intermediate results. We then show how to use (a modification of) B-trees, along with TwigStack, to match query twig patterns in sub-linear time. Finally, we complement our analysis with experimental results on a range of real and synthetic data, and query twig patterns.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Structural Joins: A Primitive for Efficient XML Query Pattern Matching, Proceedings of the 18th International Conference on Data Engineering, p.141, February 26-March 01, 2002
	2	S. Boag, D. Chamberlin, M. Fernandez, D. Florescu, J. Robie, J. Simeon, and M. Stefanescu XQuery 1.0: An XML Query Language. W3C Working Draft. Available from http://www.w3.org/TR/xquery, Dec. 2001.
	3	N. Bruno, N. Koudas, D. Srivastava. Holistic Twig Joins: Optimal XML Pattern Matching. Technical Report. Columbia University. March 2002.
	4	Michael J. Carey , Jerry Kiernan , Jayavel Shanmugasundaram , Eugene J. Shekita , Subbu N. Subramanian, XPERANTO: Middleware for Publishing Object-Relational Data as XML Documents, Proceedings of the 26th International Conference on Very Large Data Bases, p.646-648, September 10-14, 2000
	5	Donald D. Chamberlin , Jonathan Robie , Daniela Florescu, Quilt: An XML Query Language for Heterogeneous Data Sources, Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.1-25, May 18-19, 2000
	6	Mariano P. Consens , Tova Milo, Optimizing queries on files, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.301-312, May 24-27, 1994, Minneapolis, Minnesota, United States
	7	Mariano P. Consens , Tova Milo, Algebras for querying text regions (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.11-22, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212437]
	8	A. Deutsch, M. Fernandez, D. Florescu, A. Levy, and D. Suciu. XML-QL: A query language for XML. Available from http://www.w3.org/TR/NOTE-xml-ql., 1998.
	9	D. DeWitt, J. Naughton, and D. Schneider. An evaluation of non equijoin algorithms. Proceedings of ACM SIGMOD, 1991.
	10	Mary Fernández , Wang-Chiew Tan , Dan Suciu, SilkRoute: trading between relations and XML, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.723-745, June 2000, Amsterdam, The Netherlands
	11	Thorsten Fiebig , Guido Moerkotte, Evaluating Queries on Structure with eXtended Access Support Relations, Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.125-136, May 18-19, 2000
	12	D. Florescu and D. Kossman. Storing and querying XML data using an RDMBS. IEEE Data Engineering Bulletin, 22(3):27-34, 1999.
	13	Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
	14	Nick Koudas , Kenneth C. Sevcik, Size separation spatial join, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.324-335, May 11-15, 1997, Tucson, Arizona, United States
	15	Ming-Ling Lo , Chinya V. Ravishankar, Spatial hash-joins, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.247-258, June 04-06, 1996, Montreal, Quebec, Canada
	16	Jason McHugh , Serge Abiteboul , Roy Goldman , Dallas Quass , Jennifer Widom, Lore: a database management system for semistructured data, ACM SIGMOD Record, v.26 n.3, p.54-66, Sept. 1997 [doi>10.1145/262762.262770]
	17	Jason McHugh , Jennifer Widom, Query Optimization for XML, Proceedings of the 25th International Conference on Very Large Data Bases, p.315-326, September 07-10, 1999
	18	U. of Washington. The Tukwila system. Available from http://data.cs.washington.edu/integration/tukwila/.
	19	U. of Wisconsin. The Niagara system. Available from http://www.cs.wisc.edu/niagara/.
	20	Jignesh M. Patel , David J. DeWitt, Partition based spatial-merge join, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.259-270, June 04-06, 1996, Montreal, Quebec, Canada
	21	Dallan Quass , Jennifer Widom , Roy Goldman , Kevin Haas , Qingshan Luo , Jason McHugh , Svetlozar Nestorov , Anand Rajaraman , Hugo Rivero , Serge Abiteboul , Jeff Ullman , Janet Wiener, LORE: a Lightweight Object REpository for semistructured data, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.549, June 04-06, 1996, Montreal, Quebec, Canada
	22	Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
	23	Jayavel Shanmugasundaram , Eugene J. Shekita , Rimon Barr , Michael J. Carey , Bruce G. Lindsay , Hamid Pirahesh , Berthold Reinwald, Efficiently Publishing Relational Data as XML Documents, Proceedings of the 26th International Conference on Very Large Data Bases, p.65-76, September 10-14, 2000
	24	Jayavel Shanmugasundaram , Kristin Tufte , Chun Zhang , Gang He , David J. DeWitt , Jeffrey F. Naughton, Relational Databases for Querying XML Documents: Limitations and Opportunities, Proceedings of the 25th International Conference on Very Large Data Bases, p.302-314, September 07-10, 1999
	25	XMach-1. Available from http://dbs.uni-leipzig.de/en/projekte/XML/XmlBenchmarking.html.
	26	The XML benchmark project. Available from http://www.xml-benchmark.org.
	27	Chun Zhang , Jeffrey Naughton , David DeWitt , Qiong Luo , Guy Lohman, On supporting containment queries in relational database management systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.425-436, May 21-24, 2001, Santa Barbara, California, United States

CITED BY 151

	Shurug Al-Khalifa , H. V. Jagadish, Multi-level operator combination in XML query processing, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
	Joonho Kwon , Praveen Rao , Bongki Moon , Sukho Lee, FiST: scalable XML document filtering by sequencing twig patterns, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Stelios Paparizos , Yuqing Wu , Laks V. S. Lakshmanan , H. V. Jagadish, Tree logical classes for efficient evaluation of XQuery, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	David DeHaan , David Toman , Mariano P. Consens , M. Tamer Özsu, A comprehensive XQuery to SQL translation using dynamic interval encoding, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
	Shurug Al-Khalifa , Cong Yu , H. V. Jagadish, Querying structured text in an XML database, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
	Yanlei Diao , Mehmet Altinel , Michael J. Franklin , Hao Zhang , Peter Fischer, Path sharing and predicate evaluation for high-performance XML filtering, ACM Transactions on Database Systems (TODS), v.28 n.4, p.467-516, December 2003
	Yi Chen , Susan B. Davidson , Yifeng Zheng, BLAS: an efficient XPath processing system, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Zografoula Vagena , Nick Koudas , Divesh Srivastava , Vassilis J. Tsotras, Answering order-based queries over XML data, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan
	Beverly Yang , Marcus Fontoura , Eugene Shekita , Sridhar Rajagopalan , Kevin Beyer, Virtual cursors for XML joins, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	Yi Chen , George A. Mihaila , Susan B. Davidson , Sriram Padmanabhan, EXPedite: a system for encoded XML processing, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	Haifeng Jiang , Hongjun Lu , Wei Wang, Efficient processing of XML twig queries with OR-predicates, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Juliana Freire , Michael Benedikt, Managing XML Data: An Abridged Overview, Computing in Science and Engineering, v.6 n.4, p.12-19, July 2004
	H. V. Jagadish , Laks V. S. Lakshmanan , Monica Scannapieco , Divesh Srivastava , Nuwee Wiwatwattana, Colorful XML: one hierarchy isn't enough, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Raghav Kaushik , Rajasekar Krishnamurthy , Jeffrey F. Naughton , Raghu Ramakrishnan, On the integration of structure indexes and inverted lists, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
	Jiaheng Lu , Ting Chen , Tok Wang Ling, Efficient processing of XML twig patterns with parent child edges: a look-ahead approach, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	Jongik Kim , Sang Ho Lee , Hyoung-Joo Kim, Efficient structural joins with clustered extents, Information Processing Letters, v.91 n.2, p.69-75, 31 July 2004
	Hanyu Li , Mong Li Lee , Wynne Hsu , Chao Chen, An evaluation of XML indexes for structural join, ACM SIGMOD Record, v.33 n.3, September 2004
	Martin Theobald , Ralf Schenkel , Gerhard Weikum, An efficient and versatile query engine for TopX search, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Hyunchul Kang , Seungchul Han , Younghyun Kim, Schemes of storing XML query cache, Proceedings of the sixteenth Australasian database conference, p.55-64, January 01, 2005, Newcastle, Australia
	Ning Zhang , Peter J. Haas , Vanja Josifovski , Guy M. Lohman , Chun Zhang, Statistical learning techniques for costing XML queries, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Jiaheng Lu , Ting Chen , Tok Wang Ling, TJFast: effective processing of XML twig pattern matching, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan
	Wanhong Xu , Z. Meral Özsoyoglu, Rewriting XPath queries using materialized views, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Wang Lian , Nikos Mamoulis , David Wai-lok Cheung , S. M. Yiu, Indexing Useful Structural Patterns for XML Query Processing, IEEE Transactions on Knowledge and Data Engineering, v.17 n.7, p.997-1009, July 2005
	Kevin Beyer , Roberta J. Cochrane , Vanja Josifovski , Jim Kleewein , George Lapis , Guy Lohman , Bob Lyle , Fatma Özcan , Hamid Pirahesh , Normen Seemann , Tuong Truong , Bert Van der Linden , Brian Vickery , Chun Zhang, System RX: one part relational, one part XML, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Nikolaus Augsten , Michael Böhlen , Johann Gamper, Approximate matching of hierarchical data using pq-grams, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Ting Chen , Jiaheng Lu , Tok Wang Ling, On boosting holism in XML twig pattern matching using structural indexing techniques, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Georg Gottlob , Christoph Koch , Reinhard Pichler, Efficient algorithms for processing XPath queries, ACM Transactions on Database Systems (TODS), v.30 n.2, p.444-491, June 2005
	Charles L. A. Clarke, Controlling overlap in content-oriented XML retrieval, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil
	Li Chen , Amarnath Gupta , M. Erdem Kurul, Stack-based algorithms for pattern matching on DAGs, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Wei Wang , Haifeng Jiang , Hongzhi Wang , Xuemin Lin , Hongjun Lu , Jianzhong Li, Efficient processing of XML path queries using the disk-based F&B Index, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Stelios Paparizos , H. V. Jagadish, Pattern tree algebras: sets or sequences?, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Mirella M. Moro , Zografoula Vagena , Vassilis J. Tsotras, Tree-pattern queries on a lightweight XML processor, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	K. Hima Prasad , P. Sreenivasa Kumar, Efficient indexing and querying of XML data using modified Prüfer sequences, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
	Barbara Catania , Beng Chin Ooi , Wenqiang Wang , Xiaoling Wang, Lazy XML updates: laziness as a virtue, of update and structural join efficiency, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Stéphane Bressan , Barbara Catania , Zoé Lacroix , Ying Guang Li , Anna Maddalena, Accelerating queries by pruning XML documents, Data & Knowledge Engineering, v.54 n.2, p.211-240, August 2005
	Hao He , Haixun Wang , Jun Yang , Philip S. Yu, Compact reachability labeling for graph-structured data, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
	Kyung-Sub Min , Hyoung-Joo Kim, A path-based node filtering method for efficient structural joins, Information Processing Letters, v.95 n.5, p.480-486, 15 September 2005
	William M. Shui , Franky Lam , Damien K. Fisher , Raymond K. Wong, Querying and maintaining ordered XML data using relational databases, Proceedings of the sixteenth Australasian database conference, p.85-94, January 01, 2005, Newcastle, Australia
	Marcus Fontoura , Vanja Josifovski , Eugene Shekita , Beverly Yang, Optimizing cursor movement in holistic twig joins, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
	Shu-Yao Chien , Vassilis J. Tsotras , Carlo Zaniolo , Donghui Zhang, Supporting complex queries on multiversion XML documents, ACM Transactions on Internet Technology (TOIT), v.6 n.1, p.53-84, February 2006
	Zografoula Vagena , Mirella M. Moro , Vassilis J. Tsotras, Twig query processing over graph-structured XML data, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France
	Qiankun Zhao , Sourav S. Bhowmick , Le Gruenwald, Mining conserved XML query paths for dynamic-conscious caching, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
	Carl-Christian Kanne , Matthias Brantner , Guido Moerkotte, Cost-sensitive reordering of navigational primitives, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	Jiaheng Lu , Tok Wang Ling , Chee-Yong Chan , Ting Chen, From region encoding to extended dewey: on efficient processing of XML twig pattern matching, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Attila Barta , Mariano P. Consens , Alberto O. Mendelzon, Benefits of path summaries in an XML query optimizer supporting multiple access methods, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Sudipto Guha , H. V. Jagadish , Nick Koudas , Divesh Srivastava , Ting Yu, Integrating XML data sources using approximate joins, ACM Transactions on Database Systems (TODS), v.31 n.1, p.161-207, March 2006
	P. Mark Pettovello , Farshad Fotouhi, MTree: an XML XPath graph index, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
	Christian Mathis , Theo Härder , Michael Haustein, Locking-aware structural join operators for XML query processing, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	Eugene Wu , Yanlei Diao , Shariq Rizvi, High-performance complex event processing over streams, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	Hua-Gang Li , S. Alireza Aghili , Divyakant Agrawal , Amr El Abbadi, FLUX: fuzzy content and structure matching of XML range queries, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland
	Mirella M. Moro , Zografoula Vagena , Vassilis J. Tsotras, Evaluating structural summaries as access methods for XML, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland
	Young-Ho Park , Kyu-Young Whang , Byung Suk Lee , Wook-Shin Han, Efficient evaluation of linear path expressions on large-scale heterogeneous XML documents using information retrieval techniques, Journal of Systems and Software, v.79 n.2, p.180-190, February 2006
	A. Balmin , T. Eliaz , J. Hornibrook , L. Lim , G. M. Lohman , D. Simmen , M. Wang , C. Zhang, Cost-based optimization in DB2 XML, IBM Systems Journal, v.45 n.2, p.299-319, January 2006
	K. Beyer , R. Cochrane , M. Hvizdos , V. Josifovski , J. Kleewein , G. Lapis , G. Lohman , R. Lyle , M. Nicola , F. Özcan , H. Pirahesh , N. Seemann , A. Singh , T. Truong , R. C. Van der Linden , B. Vickery , C. Zhang , G. Zhang, DB2 goes hybrid: integratng native XML and XQuery with relational data and SQL, IBM Systems Journal, v.45 n.2, p.271-298, January 2006
	Qun Chen , Andrew Lim , Kian Win Ong , Ji Qing Tang, Indexing graph-structured XML data for efficient structural join operation, Data & Knowledge Engineering, v.58 n.2, p.159-179, August 2006
	Andrey Balmin , Fatma Özcan , Ashutosh Singh , Edison Ting, Grouping and optimization of XPath expressions in DB2^® pureXML, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	J. T. Yao , M. Zhang, A Fast Tree Pattern Matching Algorithm for XML Query, Proceedings of the 2004 IEEE/WIC/ACM International Conference on Web Intelligence, p.235-241, September 20-24, 2004
	Qun Chen , Andrew Lim , Kian Win Ong, Enabling structural summaries for efficient update and workload adaptation, Data & Knowledge Engineering, v.64 n.3, p.558-579, March, 2008
	Xiaoying Wu , Stefanos Souldatos , Dimitri Theodoratos , Theodore Dalamagas , Timos Sellis, Efficient evaluation of generalized path pattern queries on XML data, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
	Praveen Rao , Bongki Moon, Sequencing XML data and query twigs for fast pattern matching, ACM Transactions on Database Systems (TODS), v.31 n.1, p.299-345, March 2006
	Peter Boncz , Torsten Grust , Maurice van Keulen , Stefan Manegold , Jan Rittinger , Jens Teubner, MonetDB/XQuery: a fast XQuery processor powered by a relational engine, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	Te Li , Qihong Shao , Yi Chen, PEPX: a query-friendly probabilistic XML database, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
	Zhewei Jiang , Cheng Luo , Wen-Chi Hou, An efficient one-phase holistic twig join algorithm for XML data, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
	Nikolaus Augsten , Michael Böhlen , Johann Gamper, An incrementally maintainable index for approximate lookups in hierarchical data, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Ning Zhang , M. Tamer Özsu , Ihab F. Ilyas , Ashraf Aboulnaga, FIX: feature-based indexing technique for XML documents, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	K. Selçuk Candan , Wang-Pin Hsiung , Songting Chen , Junichi Tatemura , Divyakant Agrawal, AFilter: adaptable XML filtering with prefix-caching suffix-clustering, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Laks V. S. Lakshmanan , Hui Wang , Zheng Zhao, Answering tree pattern queries using views, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	Songting Chen , Hua-Gang Li , Junichi Tatemura , Wang-Pin Hsiung , Divyakant Agrawal , K. Selçuk Candan, Twig²Stack: bottom-up processing of generalized-tree-pattern queries over XML documents, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
	S. Alireza Aghili , Hua-Gang Li , Divyakant Agrawal , Amr El Abbadi, TWIX: twig structure and content matching of selective queries using binary labeling, Proceedings of the 1st international conference on Scalable information systems, p.42-es, May 30-June 01, 2006, Hong Kong
	Christoph Koch, Processing queries on tree-structured data efficiently, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Qun Chen , Andrew Lim , Kian Win Ong , Jiqing Tang, Indexing XML documents for XPath query processing in external memory, Data & Knowledge Engineering, v.59 n.3, p.681-699, December 2006
	François Bry , Tim Furche , Benedikt Linse , Andreas Schroeder, Efficient evaluation of n-ary conjunctive queries over trees and graphs, Proceedings of the eighth ACM international workshop on Web information and data management, November 10-10, 2006, Arlington, Virginia, USA
	Sanjay Madria , Yan Chen , Kalpdrum Passi , Sourav Bhowmick, Efficient processing of XPath queries using indexes, Information Systems, v.32 n.1, p.131-159, March, 2007
	Krishna P. Leela , Jayant R. Haritsa, Schema-conscious XML indexing, Information Systems, v.32 n.2, p.344-364, April, 2007
	Yon Dohn Chung , Ji Yeon Lee, An indexing method for wireless broadcast XML data, Information Sciences: an International Journal, v.177 n.9, p.1931-1953, May, 2007
	Guoliang Li , Jianhua Feng , Jianyong Wang , Lizhu Zhou, Effective keyword search for valuable lcas over xml documents, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Sara Cohen , Benny Kimelfeld , Yehoshua Sagiv, Incorporating constraints in probabilistic XML, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada
	Amélie Marian , Jérôme Siméon, Projecting XML documents, Proceedings of the 29th international conference on Very large data bases, p.213-224, September 09-12, 2003, Berlin, Germany
	Alan Halverson , Josef Burger , Leonidas Galanis , Ameet Kini , Rajasekar Krishnamurthy , Ajith Nagaraja Rao , Feng Tian , Stratis D. Viglas , Yuan Wang , Jeffrey F. Naughton , David J. DeWitt, Mixed mode XML query processing, Proceedings of the 29th international conference on Very large data bases, p.225-236, September 09-12, 2003, Berlin, Germany
	Zhimin Chen , H. V. Jagadish , Laks V. S. Lakshmanan , Stelios Paparizos, From tree patterns to generalized tree patterns: on efficient evaluation of XQuery, Proceedings of the 29th international conference on Very large data bases, p.237-248, September 09-12, 2003, Berlin, Germany
	Chang-Xuan Wan , Xi-Ping Liu, Structural join and staircase join algorithms of sibling relationship, Journal of Computer Science and Technology, v.22 n.2, p.171-181, March 2007
	Haifeng Jiang , Wei Wang , Hongjun Lu , Jeffrey Xu Yu, Holistic twig joins on indexed XML documents, Proceedings of the 29th international conference on Very large data bases, p.273-284, September 09-12, 2003, Berlin, Germany
	Chee-Yong Chan , Wenfei Fan , Yiming Zeng, Taming XPath queries by minimizing wildcard steps, Proceedings of the Thirtieth international conference on Very large data bases, p.156-167, August 31-September 03, 2004, Toronto, Canada
	Yunyao Li , Cong Yu , H. V. Jagadish, Schema-free XQuery, Proceedings of the Thirtieth international conference on Very large data bases, p.72-83, August 31-September 03, 2004, Toronto, Canada
	Liang Huai Yang , Mong Li Lee , Wynne Hsu, Efficient mining of XML query patterns for caching, Proceedings of the 29th international conference on Very large data bases, p.69-80, September 09-12, 2003, Berlin, Germany
	Shu-Yao Chien , Zografoula Vagena , Donghui Zhang , Vassilis J. Tsotras , Carlo Zaniolo, Efficient structural joins on indexed XML documents, Proceedings of the 28th international conference on Very Large Data Bases, p.263-274, August 20-23, 2002, Hong Kong, China
	Ryan H. Choi , Raymond K. Wong, Efficient processing of branch queries for high-performance XML filtering, Proceedings of the 2nd international conference on Scalable information systems, June 06-08, 2007, Suzhou, China
	Georg Gottlob , Christoph Koch , Reinhard Pichler, Efficient algorithms for processing XPath queries, Proceedings of the 28th international conference on Very Large Data Bases, p.95-106, August 20-23, 2002, Hong Kong, China
	Michael Haustein , Theo Härder, An efficient infrastructure for native transactional XML processing, Data & Knowledge Engineering, v.61 n.3, p.500-523, June, 2007
	Prakash Ramanan, Holistic Join for Generalized Tree Patterns, Information Systems, v.32 n.7, p.1018-1036, November, 2007
	Torsten Grust , Jan Rittinger , Jens Teubner, Why off-the-shelf RDBMSs are better at XPath than you might expect, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
	Artem Chebotko , Mustafa Atay , Shiyong Lu , Farshad Fotouhi, XML subtree reconstruction from relational storage of XML documents, Data & Knowledge Engineering, v.62 n.2, p.199-218, August, 2007
	Zhifeng Bao , Huayu Wu , Bo Chen , Tok Wang Ling, Using semantics in XML query processing, Proceedings of the 2nd international conference on Ubiquitous information management and communication, January 31-February 01, 2008, Suwon, Korea
	Jae-Gil Lee , Kyu-Young Whang , Wook-Shin Han , Il-Yeol Song, The dynamic predicate: integrating access control with query processing in XML databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.3, p.371-387, July 2007
	Xin Wu , Guiquan Liu, XML twig pattern matching using version tree, Data & Knowledge Engineering, v.64 n.3, p.580-599, March, 2008
	Jan-Marco Bremer , Michael Gertz, Integrating document and data retrieval based on XML, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.1, p.53-83, January 2006
	Bingsheng He , Qiong Luo , Byron Choi, Adaptive Index Utilization in Memory-Resident Structural Joins, IEEE Transactions on Knowledge and Data Engineering, v.19 n.6, p.772-788, June 2007
	Vanja Josifovski , Marcus Fontoura , Attila Barta, Querying XML streams, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.2, p.197-210, April 2005
	Ralf Schenkel , Anja Theobald , Gerhard Weikum, Semantic Similarity Search on Semistructured Data with the XXL Search Engine, Information Retrieval, v.8 n.4, p.521-545, December 2005
	Dunren Che, Holistically processing XML twig queries with AND, OR, and NOT predicates, Proceedings of the 2nd international conference on Scalable information systems, June 06-08, 2007, Suzhou, China
	Radim Bača , Michal Krátký, A cost-based join selection for XML twig content-based queries, Proceedings of the 2008 EDBT workshop on Database technologies for handling XML information on the web, March 25-25, 2008, Nantes, France
	Gang Gou , Rada Chirkova, Efficient algorithms for exact ranked twig-pattern matching over graphs, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	Guoren Wang , Bo Ning , Ge Yu, Holistically Stream-based Processing Xtwig Queries, World Wide Web, v.11 n.4, p.407-425, December 2008
	Guoren Wang , Bo Ning , Ge Yu, Holistically Stream-based Processing Xtwig Queries, World Wide Web, v.11 n.4, p.407-425, December 2008
	Hongzhi Wang , Jianzhong Li , Wei Wang , Xuemin Lin, Coding-based Join Algorithms for Structural Queries on Graph-Structured XML Document, World Wide Web, v.11 n.4, p.485-510, December 2008
	Gang Gou , Rada Chirkova, Efficiently Querying Large XML Data Repositories: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.19 n.10, p.1381-1403, October 2007
	Nils Grimsmo, Faster path indexes for search in XML data, Proceedings of the nineteenth conference on Australasian database, December 03-04, 2007, Gold Coast, Australia
	Benny Kimelfeld , Yuri Kosharovsky , Yehoshua Sagiv, Query efficiency in probabilistic XML models, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	Michael Benedikt , Christoph Koch, XPath leashed, ACM Computing Surveys (CSUR), v.41 n.1, p.1-54, December 2008
	Stefanos Souldatos , Xiaoying Wu , Dimitri Theodoratos , Theodore Dalamagas , Timos Sellis, Evaluation of partial path queries on xml data, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Vahid Garakani , Sayyed Kamyar Izadi , Mostafa Haghjoo , Mohammad Harizi, Ntjfsat¬: a novel method for query with not-predicates on xml data, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Sourav S. Bhowmick , Erwin Leonardi , Hongmei Sun, Efficient evaluation of high-selective xml twig patterns with parent child edges in tree-unaware rdbms, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Loredana Afanasiev , Maarten Marx, An analysis of XQuery benchmarks, Information Systems, v.33 n.2, p.155-181, April, 2008
	Dimitri Theodoratos , Xiaoying Wu, Assigning semantics to partial tree-pattern queries, Data & Knowledge Engineering, v.64 n.1, p.242-265, January, 2008
	Philippe Michiels , Ioana Manolescu , Cédric Miachon, Toward microbenchmarking XQuery, Information Systems, v.33 n.2, p.182-202, April, 2008
	Benny Kimelfeld , Yehoshua Sagiv, Efficiently enumerating results of keyword search over data graphs, Information Systems, v.33 n.4-5, p.335-359, June, 2008
	Radim Bača , Michal Krátký , Václav Snášel, On the efficient search of an XML twig query in large DataGuide trees, Proceedings of the 2008 international symposium on Database engineering & applications, September 10-12, 2008, Coimbra, Portugal
	Jinghua Groppe , Sven Groppe, Filtering unsatisfiable XPath queries, Data & Knowledge Engineering, v.64 n.1, p.134-169, January, 2008
	Jiangming Yang , Haixun Wang , Ning Gu , Yiming Liu , Chunsong Wang , Qiwei Zhang, Lock-free consistency control for web 2.0 applications, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China
	Yunyao Li , Cong Yu , H. V. Jagadish, Enabling Schema-Free XQuery with meaningful query focus, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.3, p.355-377, May 2008
	Peter M. Fischer , Donald Kossmann, Quality of service in stateful information filters, Proceedings of the 3rd workshop on Data management for sensor networks: in conjunction with VLDB 2006, September 11-11, 2006, Seoul, Korea
	Changqing Li , Tok Wang Ling , Min Hu, Efficient updates in dynamic XML data: from binary string to quaternary string, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.3, p.573-601, May 2008
	Yan Qi , K. Selçuk Candan , Maria Luisa Sapino, Sum-max monotonic ranked joins for evaluating top-k twig queries on weighted data graphs, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Zhongming Han , Jiajin Le , Niya Fu, An efficient numbering scheme and query algorithms for XML, International Journal of Computational Science and Engineering, v.3 n.2, p.145-154, November 2007
	Shirish Tatikonda , Srinivasan Parthasarathy , Matthew Goyder, LCS-TRIM: dynamic programming meets XML indexing and querying, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Andreas M. Weiner , Christian Mathis , Theo Härder, Rules for query rewrite in native XML databases, Proceedings of the 2008 EDBT workshop on Database technologies for handling XML information on the web, March 25-25, 2008, Nantes, France
	Hong Su , Elke A. Rundensteiner , Murali Mani, Automaton in or out: run-time plan optimization for XML stream processing, Proceedings of the 2nd international workshop on Scalable stream processing system, March 29-29, 2008, Nantes, France
	O. Boussaid , J. Darmont , F. Bentayeb , S. Loudcher, Warehousing complex data from the web, International Journal of Web Engineering and Technology, v.4 n.4, p.408-433, August 2008
	Sofía Brenes, Structural summaries for efficient XML query processing, Proceedings of the 2008 EDBT Ph.D. workshop, March 25-25, 2008, Nantes, France
	Dongyang Li , Chunping Li, Track: a novel XML join algorithm for efficient processing twig queries, Proceedings of the nineteenth conference on Australasian database, December 03-04, 2007, Gold Coast, Australia
	Zhen Hua Liu , Sivasankaran Chandrasekar , Thomas Baby , Hui J. Chang, Towards a physical XML independent XQuery/SQL/XML engine, Proceedings of the VLDB Endowment, v.1 n.2, August 2008
	Sayyed Kamyar Izadi , Theo Härder , Mostafa S. Haghjoo, S3: Evaluation of tree-pattern XML queries supported by structural summaries, Data & Knowledge Engineering, v.68 n.1, p.126-145, January, 2009
	Wook-Shin Han , Haifeng Jiang , Howard Ho , Quanzhong Li, StreamTX: extracting tuples from streaming XML data, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Hongzhi Wang , Jianzhong Li , Jizhou Luo , Hong Gao, Hash-base subgraph query processing method for graph-structured XML documents, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Joonho Kwon , Praveen Rao , Bongki Moon , Sukho Lee, Value-based predicate filtering of XML documents, Data & Knowledge Engineering, v.67 n.1, p.51-73, October, 2008
	Imam Machdi , Toshiyuki Amagasa , Hiroyuki Kitagawa, XML data partitioning strategies to improve parallelism in parallel holistic twig joins, Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication, January 15-16, 2009, Suwon, Korea
	Imam Machdi , Toshiyuki Amagasa , Hiroyuki Kitagawa, GMX: an XML data partitioning scheme for holistic twig joins, Proceedings of the 10th International Conference on Information Integration and Web-based Applications & Services, November 24-26, 2008, Linz, Austria
	Su-Cheng Haw , Chien-Sing Lee, Extending path summary and region encoding for efficient structural query processing in native XML databases, Journal of Systems and Software, v.82 n.6, p.1025-1035, June, 2009
	Cheng Luo , Zhewei Jiang , Wen-Chi Hou , Feng Yu , Qiang Zhu, A sampling approach for XML query selectivity estimation, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	K. Selçuk Candan , Mehmet E. Dönderler , Yan Qi , Jaikannan Ramamoorthy , Jong W. Kim, FMware: middleware for efficient filtering and matching of XML messages with local data, Proceedings of the ACM/IFIP/USENIX 2006 International Conference on Middleware, November 01-01, 2006, Melbourne, Australia
	Lijun Chang , Jeffrey Xu Yu , Lu Qin, Query ranking in probabilistic XML data, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Huayu Wu , Tok Wang Ling , Liang Xu , Zhifeng Bao, Performing grouping and aggregate functions in XML queries, Proceedings of the 18th international conference on World wide web, April 20-24, 2009, Madrid, Spain
	Benny Kimelfeld , Yehoshua Sagiv, Modeling and querying probabilistic XML data, ACM SIGMOD Record, v.37 n.4, December 2008
	Patrick K. L. Ng , Vincent T. Y. Ng, RRSi: indexing XML data for proximity twig queries, Knowledge and Information Systems, v.17 n.2, p.193-216, November 2008
	Sara Cohen , Benny Kimelfeld , Yehoshua Sagiv, Running tree automata on probabilistic XML, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Riham Abdel Kader , Peter Boncz , Stefan Manegold , Maurice van Keulen, ROX: run-time optimization of XQueries, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
	George H. L. Fletcher , Dirk Van Gucht , Yuqing Wu , Marc Gyssens , Sofía Brenes , Jan Paredaens, A methodology for coupling fragments of XPath with structural indexes for XML documents, Information Systems, v.34 n.7, p.657-670, November, 2009
	Haris Georgiadis , Minas Charalambides , Vasilis Vassalos, Cost based plan selection for xpath, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
	Michaela Götz , Christoph Koch , Wim Martens, Efficient algorithms for descendant-only tree pattern queries, Information Systems, v.34 n.7, p.602-623, November, 2009
	Yangjun Chen , Donovan Cooke, XPath query evaluation based on the stack encoding, Proceedings of the 2009 C3S2E conference, May 19-21, 2009, Montreal, Quebec, Canada
	Yongjian Wang , Yinan Ren , Ting Chen , Yuanqiang Huang , Zhongzhi Luan , Zhongxin Wu , Depei Qian, Cesar-FD: An Effective Stateful Fault Detection Mechanism in Drug Discovery Grid, Proceedings of the 2009 9th IEEE/ACM International Symposium on Cluster Computing and the Grid, p.580-585, May 18-21, 2009