Weighted monadic datalog

Abstract: 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 . 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) is commutative and the underlying datalog program is non-circular or (ii) is a finite and commutative -cpo semiring. [Copyright &y& Elsevier]