Consider the following queries:

Q1: age > 18 & age < 24 & gender = 'male'

Q2: age > 25 & gender = 'male' & major = 'CS'

Q3: age = 20 & major = 'CS'

Clearly, given any database instance $D$, we can decide $Q1(D) \cap Q2(D) = \emptyset$ and $Q2(D) \cap Q3(D) = \emptyset$. However, we cannot decide about the result of $Q1(D) \cap Q3(D)$.

I'm aware of query containment, in where the result of one query always is a subset of the results of another query. Also, I'm aware of query equivalence, in where the results of two queries should be exactly the same given any database instance.

However, I'm looking for an algorithm/terminology for my case, where before evaluating the two queries, I can decide the intersection of their results are always empty. Indeed, due to conflicting selection conditions, they cannot have any common result.

  • 2
    $\begingroup$ This depends on the class of logical expressions you allow. You can look at the decidable theories that are used in SMT (Satisfiability Modulo Theories) for some examples. $\endgroup$ – Derek Elkins left SE Aug 1 '19 at 3:06

Your example queries are not conjunctive queries in the sense I came to know them. On Wikipedia they also are defined differently. What you maybe are looking for is the boolean query evaluation problem. $Q_1(D) \cap Q_2(D)$ can be expressed as $(Q_1 \wedge Q_2)(D)$, thus deciding whether $Q_1(D) \cap Q_2(D)$ is empty is the same as deciding whether $(Q_1 \wedge Q_2)(D)$ has any solution at all. For conjunctive queries (as defined by Wikipedia) there are algorithms, faster than the brute force method, for this problem, if the query has a certain form, for example acyclic conjunctive queries.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.