Prolog Cookbook

  1. Documenting, testing, and moduling
  2. Classical Logic
    1. Negation
      1. Not
      2. Difference
      3. Fill Values
      4. De Morgan's Law
    2. Conjunction
      1. And
      2. Intersection
      3. Inner Join
      4. Product
      5. Series
    3. Disjunction
      1. Or
      2. Union
      3. Outer Join
      4. Sum
      5. Parallel
    4. Implication
      1. Proofs
    5. Equivalence
  3. Automata
  4. Graph Traversal
    1. Depth First
    2. Breadth First
    3. Transitive Closures
  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)