Patent ID: 7159171

Claim:
A search device for determining an ancestor-descendant relationship between a first element and a second element of a structured document, comprising: an information retaining part that retains: first structural information showing a hierarchical relationship between partial structures, the partial structures obtained by decomposing the structured document in accordance with a setting; and second structural information showing, for each of the partial structures, a hierarchical relationship between elements in that partial structure, each ancestor partial structure containing at least one element that is also a root of a child partial structure; and a structure search part that determines an ancestor-descendant relationship between the first elements and the second element of the structured document by: determining whether the two elements are in a same partial structure; if the two elements are in the same partial structure, determining the ancestor-descendant relationship between the two elements based on the second structural information; if the two elements are not in the same partial structure, determining the ancestor-descendant relationship between a first partial structure containing the first element and a second partial structure containing the second element based on the first structural information; determining if the first partial structure is an ancestor of the second partial structure based on the first structural information; and if the first partial structure is an ancestor of the second partial structure, determining an ancestor-descendant relationship between the first element and a mount point based on the second structural information, the mount point contained within the first partial structure, the mount point located on a path from the first partial structure to the second partial structure, and the mount point a root of a child partial structure of the ancestor partial structure.