ABSTRACT
Tree pattern queries are a natural language for querying graph- and tree-structured data. A central question for understanding their optimization problem was whether they can be minimized by cutting away redundant parts. This question has been studied since the early 2000's and was recently resolved.
- W. Czerwiński, W. Martens, M. Niewerth, and P. Parys. Minimization of Tree Pattern Queries. In PODS, pages 43–54, 2016. Google ScholarDigital Library
- W. Czerwiński, W. Martens, M. Niewerth, and P. Parys. Optimizing Tree Patterns for Querying Graph- and Tree-Structured Data. Sigmod RECORD, 2017. Google ScholarDigital Library
- S. Flesca, F. Furfaro, and E. Masciari. On the minimization of XPath queries. J. ACM, 55(1), 2008. Google ScholarDigital Library
- B. Kimelfeld and Y. Sagiv. Revisiting redundancy and minimization in an XPath fragment. In EDBT, pages 61–72, 2008. Google ScholarDigital Library
- G. Miklau and D. Suciu. Containment and equivalence for a fragment of XPath. J. ACM, 51(1), 2004. Google ScholarDigital Library
- Abstract 1 The Counterexample in a Nutshell ReferencesGoogle Scholar
Index Terms
- Optimizing tree pattern queries: why cutting is not enough (invited talk)
Recommendations
Minimization of tree pattern queries with constraints
SIGMOD '08: Proceedings of the 2008 ACM SIGMOD international conference on Management of dataTree pattern queries (TPQs) provide a natural and easy formalism to query tree-structured XML data, and the efficient processing of such queries has attracted a lot of attention. Since the size of a TPQ is a key determinant of its evaluation cost, ...
Efficient algorithms for descendant-only tree pattern queries
Tree pattern matching is a fundamental problem that has a wide range of applications in Web data management, XML processing, and selective data dissemination. In this paper we develop efficient algorithms for the tree homeomorphism problem, i.e., the ...
Optimizing large star-schema queries with snowflakes via heuristic-based query rewriting
CASCON '03: Proceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative researchUser queries have been becoming increasingly complex (e.g., involving a large number of joins) as database technology is applied to some application domains such as data warehouses and life sciences. Query optimizers in existing database management ...
Comments