Structural joins: a primitive for efficient XML query pattern matching

摘要: XML queries typically specify patterns of selection predicates on multiple elements that have some specified tree structured relationships. The primitive relationships are parent-child and ancestor-descendant, finding all occurrences these in an database is a core operation for query processing. We develop two families structural join algorithms this task: tree-merge stack-tree. natural extension traditional merge joins the multi-predicate joins, while stack-tree no counterpart relational present experimental results range data using TIMBER native engine built top SHORE. show while, cases, can performance comparable to algorithms, many cases they considerably worse. This behavior explained by analytical demonstrate that, sorted inputs, worst-case I/O CPU complexities linear sum sizes inputs output, do not same guarantee.