Datalog extensions for database queries and updates

摘要

Deterministic and non-deterministic extensions of Datalog with fixpoint semantics are proposed, and their expressive power characterized. It is argued that fixpoint semantics provides an elegant way to overcome the limited expressive power available with purely declarative semantics. The Datalog extensions range from complete languages to languages capturing interesting complexity classes of queries and updates: PTIME and PSPACE in the non-deterministic case, and the fixpoint queries and while queries in the deterministic case. The connection between the Datalog extensions and explicitly procedural languages, as well as fixpoint extensions of first-order logic, is also investigated. In particular, a new family of non-deterministic fixpoint extensions of first-order logic is considered.