BlossomTree: Evaluating XPaths in FLWOR Expressions Ning Zhang, Shishir Agrawal, and M. Tamer Özsu   View Paper (PDF)   Return to Research Session 11: XML Indexing and Dissemination Abstract Efficient evaluation of path expressions has been studied extensively. However, evaluating more complex FLWOR expressions that contain multiple path expressions has not been well studied. In this paper, we propose a novel pattern matching approach, called BlossomTree, to evaluate a FLWOR expression that contains correlated path expressions. BlossomTree is a formalism to capture the semantics of the path expressions and their correlations. We propose a general algebraic framework (abstract data types and logical operators) to evaluate BlossomTreepattern matching that facilitates efficient evaluation and experimentation. We design efficient data structures and algorithms to implement the abstract data types and logical operators. Our experimental studies demonstrate that the BlossomTreeapproach can generate highly efficient query plans in different environments. ©2006 Association for Computing Machinery