A monotone preservation result for Boolean queries expressed as a containment of conjunctive queries

DOI10.1016/J.IPL.2019.06.001MaRDI QIDQ2274499zbMATH OpenOpenAlexWikidataFDO

Authors Dimitri Surinx, Jan Van den Bussche

Publication date 20 September 2019

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.08822

zbMATH Keywords

databasesexpressive powerquery languages

Mathematics Subject Classification ID

Database theory (68P15)

Abstract: 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. Another interesting way for expressing boolean queries are containment statements of the form $Q_{1}subseteq{Q}_2$ where $Q_1$ and $Q_2$ are query expressions. Here, for any input instance $I$, the boolean query result is $mathittrue$ if $Q_1(I)$ is a subset of $Q_2(I)$ and $mathitfalse$ otherwise. In the present paper we will focus on nonemptiness and containment statements about conjunctive queries. The main goal is to investigate the monotone fragment 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.

Recommendations

• A framework for comparing query languages in their ability to express Boolean queries
• scientific article; zbMATH DE number 1951561
• A framework for comparing query languages in their ability to express Boolean queries
• Some results on the containment and minimization of (in)equality queries
• On the containment problem for queries in conjunctive form with negation

Cites work

• Datalog queries distributing over components
• Generating plans from proofs. The interpolation-based approach to query reformulation
• Homomorphism preservation theorems
• scientific article; zbMATH DE number 4008383 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• Model theory.
• Monotone versus positive

Cited in

(2)

• A framework for comparing query languages in their ability to express Boolean queries
• A framework for comparing query languages in their ability to express Boolean queries

This page was built for publication: A monotone preservation result for Boolean queries expressed as a containment of conjunctive queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274499)