Patent ID: 7502802
Filing Date: 2009-03-10
Classification: G06F,Y10S

Abstract:
1. A computer implemented method for optimizing cursor movement in holistic twig joins, comprising: selecting a minimum cursor having a smallest begin value in an inverted index representing XML data and corresponding to a path node q in a query tree Q; virtually moving all cursors corresponding to one or more nodes in a subtree of Q rooted at q as far forward as possible without missing a solution; physically moving a cursor forward in the subtree rooted at q when no further virtual moves are possible without missing a solution; repeating the steps of selecting a minimum cursor and moving cursors forward until a partial solution rooted at q is found; outputting one or more stacked full solutions that includes q; pushing a cursor corresponding to q onto a stack; physically advancing the cursor corresponding to q; repeating the steps of selecting a minimum cursor, virtually moving, physically moving, outputting, pushing a cursor, and physically advancing the minimum cursor until no more solutions are found, wherein the partial solution rooted at q is found if no cursors in a set path of cursors in a subtree rooted at q are virtual, a cursor at q is contained by its parent's stack and the set path of cursors in a subtree rooted at q satisfy containment constraints of a query tree being evaluated.