2016/08/22 by André Frochaux, Frochaux, André, Nicole Schweikardt +1
Computer Science · #Advanced Database Systems and Queries #Complexity and Algorithms in Graphs #Graph Theory and Algorithms #cs.LO
paper · pdf · doi:10.48550/arxiv.1608.06130
arxiv created 2016/08/22 · arxiv updated 2016/08/23
In their AMW14-paper, Frochaux, Grohe, and Schweikardt showed that the query containment problem for monadic datalog on finite unranked labeled trees is Exptime-complete when (a) considering unordered trees using the child-axis, and when (b) considering ordered trees using the axes firstchild, nextsibling, and child. Furthermore, when allowing to use also the descendant-axis, the query containment problem was shown to be solvable in 2-fold exponential time, but it remained open to determine the problems exact complexity in presence of the descendant-axis. The present paper closes this gap by showing that, in the presence of the descendant-axis, the problem is 2Exptime-hard.