An Indexing Scheme for Structured Documents and its Implementation

摘要

Documents consist of components such as sections, subsections and paragraphs. These components conform to hierarchical structures which can be explicitly encoded according to document representation standards such as SGML. The SCL (Simple Concordance Lists) query language provides a simple and effective way to express traditional boolean queries as well as queries specifying document structure ina database of structured documents such as SGML documents. This paper describes an indexing scheme which can support this query language and its implementation as a prototype. We describe how SCL queries are evaluated and show how query evaluation can be optimised. The performance results obtained show that structured queries at all levels of the document structure can be supported, and that ur optimisation strategy can substantially reduce query processing costs.