12. The computer readable medium of claim 2 , wherein the original query is expressed as an original query tree, the relaxed query is expressed as a relaxed query tree, the relaxing includes removing from the original query, a requirement that a leaf node must be found in the input document, and the relaxing includes preserving a shape of the original query tree while forming the relaxed query tree to have no more nodes than the original query tree.
2. The apparatus of claim 1 , wherein, the document is expressed in a nested-structure, document-specific markup language and the query further comprises: links that are associated with join conditions that define relationships among the query nodes as being children, parents, ancestors or descendants of each other; and a query root node that represents answers to be returned.