A Monotone Preservation Result for Boolean Queries Expressed as a Containment of Conjunctive Queries
When a relational database is queried, the result is normally a relation. Some queries, however, only require a yes/no answer; such queries are often called boolean queries. It is customary in database theory to express boolean queries by testing nonemptiness of query expressions of the form Q ≠∅. Another interesting way for expressing boolean queries are containment statements of the form Q_1 ⊆ Q_2. Here, Q_1 ⊆ Q_2(I) is true if Q_1(I)⊆ Q_2(I) and false otherwise. In the present paper we will focus on nonemptiness and containment expressions of conjunctive queries. The main goal is to investigate the monotone subfragment of the containments of conjunctive queries. In particular, we show a preservation like result for this monotone fragment. That is, we show that, in expressive power, the monotone containments of conjunctive queries are exactly equal to conjunctive queries under nonemptiness.
READ FULL TEXT