Patent ID: 8595215

Claim:
A query processing apparatus comprising: a query receiving unit that receives query data used for delivering a command to extract structured-document data that satisfies a predetermined condition with respect to a database that stores the structured-document data represented by tree-structured nodes, the query data including an OR/AND condition and a nesting condition; a query analyzing unit that parses the query data, and generates an analysis graph that includes variable nodes and predicate nodes, each variable node corresponding to a variable to which an object on the database is bound, each predicate node being connected to the variable nodes, and the predicate node indicating a condition between the connected variable nodes; a plan storing unit that stores a plurality of subplans, each of the subplans including at least one of the predicate nodes; a plan combining unit that generates a plan including all predicate nodes included in the analysis graph by repeating a combining process, the combining process including: a first process that selects from the plan storing unit the plurality of subplans that satisfy plan combination constraint data and that have a low cost; the plan combination constraint data including a first constraint and a second constraint, the first constraint indicating that the predicate nodes included in the plurality of subplans are connected with each other at the variable node, the second constraint indicating that no common predicate node exists in the plurality of subplans, the first process selecting the plurality of subplans that satisfy the first constraint and selecting the plurality of subplans that satisfy the second constraint; a second process that generates a new subplan by combining the selected subplans; and a third process that stores the generated subplan in the plan storing unit, a plan executing unit that generates the structured-document data satisfying the query data by executing the plan; and a processor for executing at least the plan combining unit.