New publication on conjunctive queries over trees

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 informationActa Informatica 55(1), pp. 17-56, 2018.