NDLI: Structural joins: a primitive for efficient XML query pattern matching

Content Provider	IEEE Xplore Digital Library
Author	Al-Khalifa, S. Jagadish, H.V. Koudas, N. Patel, J.M. Srivastava, D. Yuqing Wu
Copyright Year	2002
Abstract	XML queries typically specify patterns of selection predicates on multiple elements that have some specified tree structured relationships. The primitive tree structured relationships are parent-child and ancestor-descendant, and finding all occurrences of these relationships in an XML database is a core operation for XML query processing. We develop two families of structural join algorithms for this task: tree-merge and stack-tree. The tree-merge algorithms are a natural extension of traditional merge joins and the multi-predicate merge joins, while the stack-tree algorithms have no counterpart in traditional relational join processing. We present experimental results on a range of data and queries using the TIMBER native XML query engine built on top of SHORE. We show that while, in some cases, tree-merge algorithms can have performance comparable to stack-tree algorithms, in many cases they are considerably worse. This behavior is explained by analytical results that demonstrate that, on sorted inputs, the stack-tree algorithms have worst-case I/O and CPU complexities linear in the sum of the sizes of inputs and output, while the tree-merge algorithms do not have the same guarantee.
Sponsorship	IEEE Comput. Soc. Tech. Committee on Data Eng.
Starting Page	141
Ending Page	152
File Size	406807
Page Count	12
File Format	PDF
ISBN	0769515312
ISSN	10636382
DOI	10.1109/ICDE.2002.994704
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2002-02-26
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	XML Pattern matching Relational databases Engines Books Query processing Algorithm design and analysis Database languages Database systems Data engineering
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Structural Joins: A Primitive for Efficient XML Query Pattern Matching (2002)

Structural Joins: A Primitive for Efficient XML Query Pattern Matching (2002)

A Fast Tree Pattern Matching Algorithm for XML Query

Index Structures for Matching XML Twigs Using Relational Query Processors

An efficient query matching algorithm for relational data semantic cache

XLight, An Efficient Relational Schema to Store and Query XML Data

Structural Joins: A Primitive for Efficient XML Query Pattern Matching (2002)

Approximate Structural Matching over Ordered XML Documents

Structural Semi-Join: A light-weight structural join operator for efficient XML path query pattern matching

Structural joins: a primitive for efficient XML query pattern matching

Similar Documents

Structural Joins: A Primitive for Efficient XML Query Pattern Matching (2002)

Structural Joins: A Primitive for Efficient XML Query Pattern Matching (2002)

A Fast Tree Pattern Matching Algorithm for XML Query

Index Structures for Matching XML Twigs Using Relational Query Processors

An efficient query matching algorithm for relational data semantic cache

XLight, An Efficient Relational Schema to Store and Query XML Data

Structural Joins: A Primitive for Efficient XML Query Pattern Matching (2002)

Approximate Structural Matching over Ordered XML Documents

Structural Semi-Join: A light-weight structural join operator for efficient XML path query pattern matching

Structural joins: a primitive for efficient XML query pattern matching