Stanislav Kikot

On monotone determinacy of recursive queries by views

A problem of (monotone) determinacy of a relational query by views arises in database theory. Algebraically put, it is about deciding if for any RA with constants a₁, ..., a_k, the value of a relational term q(a₁, ..., a_k) is (monotonically) determined by the values of given relational terms v₁(a₁, ..., a_k), ...,v_n(a₁, ..., a_k). A related problem of rewritability over views is to decide if a given relational term t(a₁,..., a_k) can be expressed as a term t'(v₁, ..., v_n) for given terms
v₁(a₁, ..., a_k), ..., v_n(a₁, ..., a_k) in a certain RA-signature. For example, given t = a⁶, it can be expressed as (v₁)³ in terms of v₁=a², but it can't be expressed in terms of v₂=a⁵. There is a plethora of results about (monotone) determinacy of relational queries. In my talk I'm going to review them, and also present a few new results on monotone determinacy for recursive queries and views, of which you can think of as terms that, in addition to RA-connectives, may also use the Kleene star.