Weighted monadic datalog

Based on monadic datalog, we introduce the concept of weighted monadic datalog over unranked trees. This provides a query language that can be used to extract quantitative information from semi-structured databases where the quantities are taken from some semiring S. We show that weighted monadic datalog is as expressive as weighted tree automata on unranked trees. Moreover, we prove that a query can be evaluated efficiently on an unranked tree provided that (i) S is commutative and the underlying datalog program is non-circular or (ii) S is a finite and commutative ω-cpo semiring.