Processing queries on tree-structured data efficiently

摘要

This is a survey of algorithms, complexity results, and general solution techniques for efficiently processing queries on tree-structured data. I focus on query languages that compute nodes or tuples of nodes-conjunctive queries, first-order queries, datalog, and XPath. I also point out a number of connections among previous results that have not been observed before.