Operational Semantics for Fixed-Point Logics on Constraint Databases

Abstract In this paper we compare the expressive power of various fixed-point logics on linear or dense order constraint databases. This comparison is not done on absolute terms, i. e. by comparing their expressive power for arbitrary queries, rather for definability of partially recursive queries. The motivation for choosing this benchmark comes from fixed-point logics as query languages for constraint databases. Here, non-recursive queries are of no practical interest. It is shown that for linear constraint databases already transitive closure logic is expressive enough to define all partially recursive queries, i. e. , transitive-closure logic is expressively complete for this class of databases. It follows that transitive-closure, least, and stratified fixed-point logic are equivalent with respect to this benchmark.

Authors

• Stephan Kreutzer

Keywords

No keywords are indexed for this paper.