Queries are used to obtain information about the structure and content of a data structure. In a recent publication by Henrik Björklund and co-authors, the computational complexity of evaluating such queries over tree-shaped data is investigated. In natural language processing, trees are used to represent, i.e., the syntactic structure – the grammar – of sentences. Queries can be used to investigate how common a certain grammatical pattern is. In the paper, the main question addressed is query containment. Containment is a key problem for query optimization, i.e., the task of making queries usable in practice.
Henrik Björklund, Wim Martens, and Thomas Schwentick: Conjunctive query containment over trees using schema information. Acta Informatica 55(1), pp. 17-56, 2018.