QUERYING DATALOG PROGRAMS WITH TEMPORAL LOGIC

Temporal logic queries on Datalog and negated Datalog programs are stu died, and their relationship to Datalog queries on these programs is e xplored. It is shown that, in general, temporal logic queries have mor e expressive power than Datalog queries on Datalog and negated Datalog programs. It is also shown that an existential domain-independent fra gment of temporal logic queries has the same expressive power as Datal og queries on negated Datalog programs with inflationary semantics. Th is means that for finite structures this class of queries has the powe r of the fixpoint logic.