Paper Info
Title
Monadic Datalog and Regular Tree Pattern Queries.
Abstract
Containment of monadic datalog programs over trees is decidable. The situation is more complex when tree nodes carry labels from an infinite alphabet that can be tested for equality. It then matters whether the descendant relation is allowed or not: the descendant relation can be eliminated easily from monadic programs only when label equalities are not used. With descendant, even containment of linear monadic programs in unions of conjunctive queries is undecidable, and positive results are known only for bounded-depth trees. We show that without descendant, containment of connected monadic programs is decidable over ranked trees, but over unranked trees it is so only for linear programs. With descendant, it becomes decidable over unranked trees under restriction to downward programs: each rule only moves down from the node in the head. This restriction is motivated by regular tree pattern queries, a recent formalism in the area of ActiveXML, which we show to be equivalent to linear downward programs.
Year
DOI
Venue
2014
10.1145/2925986
ACM Trans. Database Syst.
Keywords
Field
DocType
Theory,Recursive queries,trees,semistructured data,containment problem
Discrete mathematics,Conjunctive query,Combinatorics,Descendant,Computer science,Decidability,Datalog,Monad (functional programming),Tree pattern,Alphabet,Undecidable problem
Conference
Volume
Issue
ISSN
41
3
0362-5915
Citations 
PageRank 
References 
0
0.34
13
Authors
3
Name
Order
Citations
PageRank
Filip Mazowiecki1209.26
Filip Murlak218419.14
Adam Witkowski331.41