ABSTRACT An Algebraic Query Model for Effective and Efficient Retrieval of XML Fragments

Finding a suitable fragment of interest in a non-schematic XML document with a simple keyword search is a complex task. To deal with this problem, this paper proposes a theoretical framework with a focus on an algebraic query model having a novel query semantics. Based on this semantics, XML fragments that look meaningful to a keyword-based query are effectively retrieved by the operations defined in the model. In contrast to earlier work, our model supports filters for restricting the size of a query result, which otherwise may contain a large number of potentially irrelevant fragments. We introduce a class of filters having a special property that enables significant reduction in query processing cost. Many practically useful filters fall in this class and hence, the proposed model can be efficiently applied to realworld XML documents. Several other issues regarding algebraic manipulation of the operations defined in our query model are also formally discussed