# Prolog Cookbook

1. Documenting, testing, and moduling
2. Classical Logic
1. Negation
2. Conjunction
3. Disjunction
4. Implication
5. Equivalence
3. Automata
4. Graph Traversal
5. Route Finding
6. Puzzle Solving

# Intersection

By Robert Laing

## Which majors intersect?

Lets return to Venn’s 5 relations. Here we want to check A ∩ B ≠ Ø, which is true for any of the first four relations.

We need a self-join for this query, which is a form of intersection.

``````SELECT DISTINCT a1.major AS A, a2.major AS B
FROM apply as a1, apply as a2
WHERE a1.sid = a2.sid
ORDER BY A, B;
``````
``````       a        |       b
----------------+----------------
bioengineering | bioengineering
bioengineering | CS
bioengineering | EE
biology        | biology
biology        | CS
biology        | marine biology
CS             | bioengineering
CS             | biology
CS             | CS
CS             | EE
CS             | marine biology
EE             | bioengineering
EE             | CS
EE             | EE
history        | history
history        | psychology
marine biology | biology
marine biology | CS
marine biology | marine biology
psychology     | history
psychology     | psychology
(21 rows)
``````

Note everything intersects with itself. To remove all the A ≡ A along with A ∩ B so B ∩ A reciprocal intersections, we could add a `a1.major < a2.major` test:

``````SELECT DISTINCT a1.major AS A, a2.major AS B
FROM apply as a1, apply as a2
WHERE a1.sid = a2.sid
AND a1.major < a2.major
ORDER BY A, B;
``````
``````       a        |       b
----------------+----------------
bioengineering | CS
bioengineering | EE
biology        | CS
biology        | marine biology
CS             | EE
CS             | marine biology
history        | psychology
(7 rows)
``````

Later in implication, we’ll make the above query more specific so as to only find A and B if they fall into diagrams 1 or 3, ie A ⊆ B. Then in equivalence will hone down to finding those sets with identical elements (ie diagram 1), which in the starting state of the college data, there aren’t any.

To get the SQL query closer to A ∩ B ≠ Ø, we could collect the intersecting student IDs into a set like so:

``````SELECT sid FROM apply
INTERSECT
SELECT sid FROM apply
``````

## Which majors are disjoint?

Now lets find all those sets which fall into diagram 5, ie A ∩ B = Ø.

``````SELECT DISTINCT a1.major AS A, a2.major AS B
FROM apply as a1, apply as a2
WHERE a1.major <> a2.major
EXCEPT
SELECT a1.major AS A, a2.major AS B
FROM apply as a1, apply as a2
WHERE a1.sid = a2.sid
ORDER BY A, B;
``````
``````       a        |       b
----------------+----------------
bioengineering | biology
bioengineering | history
bioengineering | marine biology
bioengineering | psychology
biology        | bioengineering
biology        | EE
biology        | history
biology        | psychology
CS             | history
CS             | psychology
EE             | biology
EE             | history
EE             | marine biology
EE             | psychology
history        | bioengineering
history        | biology
history        | CS
history        | EE
history        | marine biology
marine biology | bioengineering
marine biology | EE
marine biology | history
marine biology | psychology
psychology     | bioengineering
psychology     | biology
psychology     | CS
psychology     | EE
psychology     | marine biology
(28 rows)
``````