Structural joins: a primitive for efficient XML query pattern matching

By Shurug A. Al-Khalifa, Hosagrahar Visvesvaraya Jagadish, Nick Koudas, Jignesh M. Patel, Divesh Srivastava, Yuqing Wu. Proceedings / International Conference on Data Engineering, 2002

886 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/a2967aec77ad5e2bc791903932b61a1c7e187b3b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Signal Processing

Citations in the corpus

Skew handling techniques in sort-merge join (2002, positive): “A similar approach was used in the tree-merge structure join algorithm [1], in which the nodes in a current sweep (analogous to our value packet) are stored in a temporary SHORE file, whose pages are written to and from disk by the SHORE buffer manager.”
Holistic Twig Joins on Indexed XML Documents (2003, methodology): “As a result, we may need to block some path solutions during output, similarly as done in Stack-Tree-Anc [ 14 ] and showSolutionsWithBlocking [3].”
Efficient keyword search for smallest LCAs in XML databases (2005, background): “Tree query patterns for querying XML trees have received gre at attention and efficient approaches are known [3, 7, 22].”
Holistic twig joins: optimal XML pattern matching (2002, methodology): “In this experiment we compare our holistic PathStack algorithm against strategies that use a combination of binary structural joins [1].”
From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching (2005, methodology): “Al-Khalifa et al.[1] started the stack-based algorithms for XML structural joins.”
eXist: An Open Source Native XML Database (2002, methodology): “Backend implementation details are completely hidden from eXist’s core (see figure 1).”
Efficient Structural Joins on Indexed XML Documents (2002, methodology): “One approach is to assign to each tree node three numbers, namely: the node’s preorder and postorder ranks as well as its level in the XML tree [13, 40, 24, 1, 19].”
Schema-Free XQuery (2004, methodology): “Our algorithm is inspired by the stack-based family of algorithms for structural join [6, 7, 8, 10], and is limited to XQuery implementations that can support”
TIMBER: A native XML database (2002, background): “It has been observed [2, 13, 39] that it is possible to associate a numeric start and end label with each data node in the database, defining a corresponding interval between these labels such that every descendant node has an interval that is strictly included in its ancestors’ interval.”
MonetDB/XQuery: a fast XQuery processor powered by a relational engine (2006, background): “Structural Joins: A Primitive for Efficient XML Query Pattern Matching.”
Graphs-at-a-time: query language and access methods for graph databases (2008, background): “Tree pattern matching thus plays an important role in XML query processing [1, 6].”
Efficient algorithms for processing XPath queries (2002, background): “The importance of XPath is due to its potential application as an XML query language per se and its role at the core of several other XML-related technologies, such as XSLT, XPointer, and XQuery.”