Abstract:
The use of markup languages like SGML, HTML, or XML for encoding the structure of documents or linguistic data has lead to many databases where entries are adequately described as trees. In this context querying formalisms are interesting that offer the possibility to refer both to textual content and logical structure. We consider models where the structure specified in a query is not only used as a filter, but also for selecting and presenting different parts of the data. If answers are formalized as mappings from query nodes to the database, a simple enumeration of all mappings in the answer set will often suffer from the effect that many answers have common subparts. From a theoretical point of view this may lead to an exponential time complexity of the computation and presentation of all answers. Concentrating on the language of so-called tree queries—a variant and extension of Kilpeläi-nen's Tree Matching formalism—we introduce the notion of a " complete answer aggregate " for a given query. This new data structure offers a compact view of the set of all answers and supports active exploration of the answer space. Since complete answer aggregates use a powerful structure-sharing mechanism their maximal size is of order Od h q where d and q respectively denote the size of the database and the query, and h is the maximal depth of a path of the database. An algorithm is given that computes a complete answer aggregate for a given tree query in time Od logd h q. For the sublanguage of so-called rigid tree queries, as well as for so-called " nonrecursive " databases, an improved bound of Od logd q is obtained. The algorithm is based on a specific index structure that supports practical efficiency.
