  With XML becoming an ubiquitous language for data interoperability purposes
in various domains, efficiently querying XML data is a critical issue. This has
lead to the design of algebraic frameworks based on tree-shaped patterns akin
to the tree-structured data model of XML. Tree patterns are graphic
representations of queries over data trees. They are actually matched against
an input data tree to answer a query. Since the turn of the twenty-first
century, an astounding research effort has been focusing on tree pattern models
and matching optimization (a primordial issue). This paper is a comprehensive
survey of these topics, in which we outline and compare the various features of
tree patterns. We also review and discuss the two main families of approaches
for optimizing tree pattern matching, namely pattern tree minimization and
holistic matching. We finally present actual tree pattern-based developments,
to provide a global overview of this significant research topic.
