And

By Robert Laing

Once again, lets use Stanford University dean Jennifer Widom’s basic SQL examples from her college applications data as an illustration.

Which students applied for ‘CS’ and ‘EE’?

In what I’ve called copula notation, conjunction is written p ∧ q, which is a handy mnemonic that its set equivalent is P ∩ Q. That logic has a spiky version of set theory’s rounded symbol we’ll also encounter in disjunction and implication.

SQL

In the next section intersection we’ll do this the easy way with SQL’s INTERSECT operator:

SELECT sid FROM apply WHERE major = 'CS'
INTERSECT
SELECT sid FROM apply WHERE major = 'EE'
ORDER BY sid;

Which produces the set {123, 345}. Since ‘EE’ is a subset of ‘CS’, ‘CS’ ∩ ‘EE’ = ‘EE’. That also means ‘EE’ ⇒ ‘CS’ as I’ll get to in implication.

For now, lets just use AND.

SELECT DISTINCT a1.sid
FROM apply AS a1, apply AS a2
WHERE a1.sid = a2.sid AND a1.major = 'CS' AND a2.major = 'EE'
ORDER BY a1.sid;

Subquery in WHERE clause

Another way of writing anded propositions is using IN in a WHERE subquery.

SELECT DISTINCT sid 
FROM apply
WHERE major = 'CS' 
AND sid IN (SELECT sid FROM apply WHERE major = 'EE')
ORDER BY sid;

For fans of Victorian syllogism, SQL allows = ANY(subquery) as a synonym for IN (subquery).

Subquery in FROM clause

One of the rules of relational algebra listed by Al Aho and Jeff Ullman is called selection splitting:

σ_{A AND B}(R) = σ_A(σ_B(R)) = σ_B(σ_A(R)).

In SQL that translates into Subqueries in the FROM clause.

SELECT DISTINCT Apply.sid
FROM (SELECT sid FROM Apply WHERE major = 'CS') AS a1, Apply
WHERE a1.sid = Apply.sid AND major = 'EE';

Prolog

In Prolog, this query can be written:

order_by([asc(SID)], distinct(SID, (apply(SID, _, 'CS', _), apply(SID, _, 'EE', _)))).

Which students applied for ‘CS’ and ‘history’?

?- apply(SID, _, 'CS', _), apply(SID, _, history, _).
false.

Short answer, none, ie we get the empty set {}, which in Prolog equates to false and in SQL to NOT EXISTS.

This is a hint how to find all disjointed sets.

Which students applied for ‘CS’ and ’logic’?

?- apply(SID, _, 'CS', _), apply(SID, _, logic, _).
false.

In this case B is the empty set since logic isn’t among the majors in the example database. Given the importance of logic in software coding, digital circuitry, modern life in general… it’s a bit alarming that the subject appears to have fallen out of modern schooling.

Anyways, this example is intended to show that attempting an intersection with an empty set is the set equivalent of multiplying by zero, ie A ∩ Ø = Ø, a reminder conjunction equates to product.

In the next section, I’ll show how AND is related to intersection.