Expressive Power of a New Model for Structured Text Databases

Gonzalo Navarro and Ricardo Baeza-Yates

This paper studies the expressivity of a new model for structuring and querying textual databases by both the structure and contents of the text. The key idea of the model is a set-oriented query language based on operations on proximal nodes. This model has been shown to be efficiently implementable, and the aim of this paper is to show that it is competitive in expressivity with models whose implementation is not so efficient. The expressivity is studied by directly comparing it against related models, and by defining a framework on expressivity where these models are situated. This work leads to the conclusion that the presented model is a good compromise between expressivity and efficiency.