Facing today's information flood needs efficient means for personalization. Therefore XML query processing over large volumes of data needs to make the most out of already spent processing time by caching common (sub)expressions for reuse. This is especially promising for the new paradigm of personalized preference queries. Here a sequence of possible query relaxations is a-priori determined by the users' preferences. Structural and value-based preferences thus define a query process where predicates are progressively relaxed until a suitable set of best possible results has been retrieved. To improve evaluation times for such query processes we argue that caching intermediate join results of structural preference queries is especially effective, because subsequent queries will always be subsumed by some previously cached queries to a certain extent. In this paper we propose a structural join-based caching scheme that allows preference queries to reuse the most beneficial structural join results of all previous queries. We first design a twig cache along with effective strategies for cache management. Moreover, we present a selection algorithm for join orders using cached data and the preference-induced sequence of future queries to select optimal query evaluation plans. Our benchmark experiments show that by using our twig caches preference query processing can be essentially sped up.

Efficient query processing using XPath or XQuery has inspired a lot of research. In contrast to classical exact match retrieval, in today's systems, specifying preferences rather than simple hard constraints is essential. As the structure of XML documents plays a major part in retrieval, recently approximate query matching on structure has received attention. However, query processing of structural user preferences has not yet been considered. In this paper we enable users to express structural preferences and consider the problem of optimizing XML twig queries while preserving the ordering induced on the result set by such user preferences. Evaluating such queries generally needs a rewriting into a set of queries, where each leaf node can be expanded by combinations of structural elements derived from the preference information. Since such structure expansions typically contain redundancies and the efficiency of query evaluation strongly depends on the size of the set of rewritten queries, it is important to identify and simplify necessary expansions. We give a detailed analysis of this process and present an optimization algorithm that determines a minimal set of queries, which in turn are minimal in their expanded nodes, while maintaining the ordering induced by the preference structure. Finally, we provide a comprehensive practical evaluation of our optimization against the XMark benchmark dataset.

XML is the de facto standard for data representation and exchange over the Web. Given the diversity of the information available in XML, it is very useful to annotate XML data with a wide variety of meta-data, such as quality and sensitivity. When querying such XML data, say using XPath, it is important to efficiently identify the data that meet specified constraints on the meta-data. For example, different users may be satisfied with different levels of quality guarantees, or may only have access to different parts of the XML data based on specified security policies. In this paper, we address the problem of efficiently identifying the XML elements along a location step in an XPath query, that satisfy meta-data range constraints, when the meta-data levels are specifically drawn from an ordered domain (e.g., accuracy in [0,1], recency using timestamps, multi-level security, etc.). More specifically, we develop a family of index structures, which we refer to as meta-data indexes, to address this problem. A meta-data index is easily instantiated using a multi-dimensional index structure, such as an R-tree, incorporating novel query and update algorithms. We show that the full meta-data index (FMI), based on associating each XML element with its meta-data level, has a very high update cost for modifying an element's meta-data level. We resolve this problem by designing the inheritance meta-data index (IMI), in which (i) actual meta-data levels are associated only with elements for which this value is explicitly specified, and (ii) inherited meta-data levels and inheritance source nodes are associated with non-leaf nodes of the index structure. We design efficient query (for all XPath axes) and update (of meta-data levels) algorithms for the IMI, and experimentally demonstrate the superiority of the IMI over the FMI using benchmark data sets.

No abstract available.

Tree patterns forms a natural basis to query tree-structured data such as XML and LDAP. Since the efficiency of tree pattern matching against a tree-structured database depends on the size of the pattern, it is essential to identify and eliminate redundant nodes in the pattern and do so as quickly as possible. In this paper, we study tree pattern minimization both in the absence and in the presence of integrity constraints (ICs) on the underlying tree-structured database.