Ergo as a Database Query Language

Ergo is an elegant language for database queries. Due to its explicit use of quantifiers, Ergo is more powerful than other deductive databases, such as, Prolog. Compared to SQL, Ergo is not only restricted to atoms, integers and reals, but it can also use more complex terms, such as, lists, F-molecules (i.e., object-oriented classes and instances), allow complex recursive definitions, allow programming in Ergo, negation, defeasible reasoning, and Ergotext.

Files Used in This Section

Use case: Flights, passengers and tickets

Example Query 1: find all the passengers that took all the flights from New York to Seattle

Example Query 2: find all passengers that never took a flight from New York to Seattle

Example Query 3: find travel agents that issued at least a ticket for every passenger

Example Query 4: find the travel agents that sold at least 10 tickets to at least one passenger

Example Query 5: find the travel agents that sold the highest number of tickets

Use case: University database: Students, Faculties and Courses

Example Query 1: find the students that are enrolled in two classes with the same faculty

Example Query 2: find the faculty that teach in every room on campus

Example Query 3: find the faculty for whom the combined enrollment is greater than 300

Example Query 4: find the average age for each student level

Example Query 5: find the students enrolled in the maximum number of classes

Use case: Parts and Suppliers

Example Query 1: find the suppliers of red parts

Example Query 2: find the suppliers of red or green parts

Example Query 3: find the suppliers of red parts or located at 1 Main St

Example Query 4: find the suppliers of red and green parts

Example Query 5: find the suppliers of all parts

Example Query 6: find the suppliers of all red parts

Example Query 7: find the suppliers of all red or green parts

Example Query 8: find the suppliers of every red part or every green part

Example Query 9: find the suppliers that sell a cheaper product than another supplier

Example Query 10: find the minimum cost for a product

Example Query 11: find the parts supplied by at least two different suppliers

Example Query 12: find the parts not supplied by any supplier

Example Query 13: find the parts that are supplied by exactly one supplier

Example Query 14: find the most expensive part sold by ACME

Example Query 15: find the parts supplied by everyone

Files Used in This Section

Use case: Flights, passengers and tickets

A relation in relational databases is a set of tuples. For example a Flight relation could contain for each flight a tuple in the relation. Each tuple contains fields for: flight number, starting location, destination, departure date and time, and arrival date and time. We can represent these tuples in Ergo in two different ways:

predicate form:

// Flight(flightNum, start, destination, departureDateTime, arrivalDateTime).

Flight(United1, NYC, Seattle, "2016-12-30T12:32:00"^^\dateTime, "2016-12-30T16:15:00"^^\dateTime).

Flight(United2, NYC, Seattle, "2016-12-31T12:32:00"^^\dateTime, "2016-12-30T16:15:00"^^\dateTime).

Flight(United3, Seattle, 'San Francisco', "2016-12-30T6:45:00"^^\dateTime, "2016-12-30T11:17:00"^^\dateTime).

Flight(United4, Seattle, 'San Francisco', "2016-12-30T6:45:00"^^\dateTime, "2016-12-30T11:16:00"^^\dateTime).

object-oriented form (i.e., F-logic syntax):

Flight[|start => \string, destination => \string, departureDateTime => \datetime, arrivalDateTime => \datetime|].

United1:Flight[start -> NYC, destination -> Seattle, departureDateTime -> "2016-12-30T12:32:00"^^\dateTime, arrivalDateTime  -> "2016-12-30T16:15:00"^^\dateTime].

United2:Flight[start -> NYC, destination -> Seattle, departureDateTime -> "2016-12-31T12:32:00"^^\dateTime, arrivalDateTime  -> "2016-12-30T16:15:00"^^\dateTime].

United3:Flight[start -> Seattle, destination -> 'San Francisco', departureDateTime -> "2016-12-30T6:45:00"^^\dateTime, arrivalDateTime  -> "2016-12-30T11:17:00"^^\dateTime].

United4:Flight[start -> Seattle, destination -> 'San Francisco', departureDateTime -> "2016-12-30T6:45:00"^^\dateTime, arrivalDateTime  -> "2016-12-30T11:16:00"^^\dateTime].

Using either syntax, one can define as many relations as they want. For example, we can have relations for passengers and itineraries:

// Ticket(ticketNum, passengerName, travelAgent).

// Itinerary(ticketNum, flightNum).

Ticket(t1, 'Abe Smith', 'Mary Smith').

Itinerary(t1, United1).

Ticket(t3, 'Ben Jones', 'John Smith').

Itinerary(t3, United1).

Ticket(t2, 'Abe Smith', 'Mary Smith').

Itinerary(t2, United2).

Ticket(t4, 'Ben Jones', 'Mary Smith').

Itinerary(t4, United2).

Ticket(t5, 'Calvin Curtis', 'Mary Smith').

Itinerary(t5, United3).

Given these extensional relations, one can define predicates to give us passengers from tickets:

passenger(?passengerName) :-

    Ticket(?_ticketNum, ?passengerName, ?_travelAgent).

Example Query 1: find all the passengers that took all the flights from New York to Seattle

One can query the Ergo reasoning system to answer complex queries. Unlike other rule engines, Ergo supports a much larger variety of formulas in the rule body, including

logical quantifiers forall (∀) and exists (∃),
negation as failure \naf,
logical implications ~~>, <~~, <~~>, ==>, <==, and <==>, and
aggregates: min, max, count, countdistinct, sum, sumdistinct, avg, avgdistinct, setof, bagof, and others.

We implement below a query that uses quantification and logical implication:

Find passengers that took all the flights from New York (NYC) to Seattle.

?- passenger(?passengerName),

    forall(?flightNum, ?departureDateTime, ?arrivalDateTime)^(

        Flight(?flightNum, NYC, Seattle, ?departureDateTime, ?arrivalDateTime)

~~>

        exists(?ticketNum,?travelAgent)^(

            Ticket(?ticketNum, ?passengerName, ?travelAgent),

            Itinerary(?ticketNum, ?flightNum)

).

Another way to write this query is to use an equivalent logical formula: find the passengers, such that "It is not the case that there exists a flight from New York to Seattle and this passenger does not have a ticket on." using the logical equivalence: ∀x,p(x)->∃y,q(x,y) ≡ ~∃x,p(x)/\~∃y,q(x,y)

?- passenger(?passengerName),

    \naf exists(?flightNum, ?departureDateTime, ?arrivalDateTime)^(

        Flight(?flightNum, NYC, Seattle, ?departureDateTime, ?arrivalDateTime),

        \naf exists(?ticketNum, ?travelAgent)^(

            Ticket(?ticketNum, ?passengerName, ?travelAgent),

            Itinerary(?ticketNum, ?flightNum)

).

Yet another way to write this query is to compare the the total number of flight from New York to Seattle with the number of distinct flights from New York to Seattle that the passenger had a ticket for:

?- passenger(?passengerName),

    count{?flightNum | Flight(?flightNum, NYC, Seattle, ?_departureDateTime, ?_arrivalDateTime)}

        = countdistinct{?flightNum |

            Flight(?flightNum, NYC, Seattle, ?_departureDateTime, ?_arrivalDateTime),

            Ticket(?ticketNum, ?passengerName, ?_travelAgent),

            Itinerary(?ticketNum, ?flightNum)

}.

Example Query 2: find all passengers that never took a flight from New York to Seattle

Find all passengers that never took a flight from New York to Seattle.

?- passenger(?passengerName),

    forall(?flightNum, ?departureDateTime, ?arrivalDateTime)^(

        Flight(?flightNum, NYC, Seattle, ?departureDateTime, ?arrivalDateTime)

~~>

        \naf exists(?ticketNum,?travelAgent)^(

            Ticket(?ticketNum, ?passengerName, ?travelAgent),

            Itinerary(?ticketNum, ?flightNum)

).

An alternative way to write this using the logical equivalences:

        ∀x,p(x)->~∃y,q(x,y) ≡

            ≡ ~~∀x,p(x)->~∃y,q(x,y), by double negation

            ≡ ~∃x,p(x)/\∃y,q(x,y), by DeMorgan (i.e., negation of forall is exists negation formula) and double negation

?- passenger(?passengerName),

    \naf exists(?flightNum, ?departureDateTime, ?arrivalDateTime)^(

        Flight(?flightNum, NYC, Seattle, ?departureDateTime, ?arrivalDateTime),

        exists(?ticketNum,?travelAgent)^(

            Ticket(?ticketNum, ?passengerName, ?travelAgent),

            Itinerary(?ticketNum, ?flightNum)

).

Yet another way to write this query uses the logical equivalence: ~∃x,p(x)/\∃y,q(x,y) ≡ ~∃x,y,(p(x)/\q(x,y))

?- passenger(?passengerName),

    \naf exists(?flightNum, ?departureDateTime, ?arrivalDateTime, ?ticketNum, ?travelAgent)^(

        Flight(?flightNum, NYC, Seattle, ?departureDateTime, ?arrivalDateTime),

        Ticket(?ticketNum, ?passengerName, ?travelAgent),

        Itinerary(?ticketNum, ?flightNum)

).

Another way to write this query could find the passengers that have the number of flights from NY to Seattle 0 (zero).

?- passenger(?passengerName),

    count{?flightNum |

        Flight(?flightNum, NYC, Seattle, ?_departureDateTime, ?_arrivalDateTime),

        Ticket(?ticketNum, ?passengerName, ?_travelAgent),

Itinerary(?ticketNum, ?flightNum)} = 0.

Example Query 3: find travel agents that issued at least a ticket for every passenger

Find the travel agents who issued at least a ticket for every existing passenger.

?- travelAgent(?travelAgent),

    forall(?passengerName)^(

        passenger(?passengerName)

~~>

        exists(?ticketNum)^(

            Ticket(?ticketNum, ?passengerName, ?travelAgent)

).

An alternative way to write this query using aggregates counts all the distinct customers for every travel agent and checks which agent sold tickets to the same number of passengers as the total number of passengers:

?- travelAgent(?travelAgent),

    countdistinct{?passengerName | passenger(?passengerName)}

        = countdistinct{?passengerName |

        Flight(?flightNum, ?_start, ?_destination, ?_departureDateTime, ?_arrivalDateTime),

        Ticket(?ticketNum, ?passengerName, ?travelAgent),

        Itinerary(?ticketNum, ?flightNum)

}.

An alternative way to write this query using logical equivalences:

?- travelAgent(?travelAgent),

    \naf exists(?passengerName)^(

        passenger(?passengerName),

        \naf exists(?ticketNum)^(

            Ticket(?ticketNum, ?passengerName, ?travelAgent)

).

Example Query 4: find the travel agents that sold at least 10 tickets to at least one passenger

Find the travel agents who sold at least 10 tickets to at least one passenger.

?- travelAgent(?travelAgent),

    ?N = count{?ticketNum[?passengerName] | Ticket(?ticketNum, ?passengerName, ?travelAgent)},

    ?N >= 10.

Example Query 5: find the travel agents that sold the highest number of tickets

Find the travel agents who sold the most number of tickets.

?- ?Max = max{?TicketsPerAgent |

            ?TicketsPerAgent = count{?ticketNum[?travelAgent2] | Ticket(?ticketNum, ?_passengerName, ?travelAgent2)}

},

      travelAgent(?travelAgent),

      ?Max = count{?ticketNum | Ticket(?ticketNum, ?_passengerName, ?travelAgent)}.

Use case: University database: Students, Faculties and Courses

Consider the following relations:

Student(sID: integer, sname: string, major: string, level: string, age: integer)
Faculty(fID: integer, fname: string, deptid: string)
Class(cname: string, room: string, fID: integer)
Enrolled(sID: integer, cname: string)

Example Query 1: find the students that are enrolled in two classes with the same faculty

Find the names of all students who are enrolled in two classes with the same faculty.

?- Student(?sID, ?sname, ?_major, ?_level, ?_age),

    Enrolled(?sID, ?cname1),

    Class(?cname1, ?_room, ?fID),

    Enrolled(?sID, ?cname2),

    ?cname1 != ?cname2,

    Class(?cname2, ?_room2, ?fID).

Example Query 2: find the faculty that teach in every room on campus

Find the names of faculty members who teach in every room on campus.

room(?room) :-

    Class(?_cname, ?room, ?_fID).

?- Faculty(?fID, ?fname, ?_deptid),

    forall(?room)^(

        room(?room)

~~>

        exists(?cname)^(

            Class(?cname, ?room, ?fID)

).

Another way to write this query uses logical equivalences:

?- Faculty(?fID, ?fname, ?_deptid),

    \naf exists(?room)^(

        room(?room),

        \naf exists(?cname)^(

            Class(?cname, ?room, ?fID)

).

Example Query 3: find the faculty for whom the combined enrollment is greater than 300

Find the names of faculty members for whom the combined enrollment of the courses that they teach is greater than 300.

?- Faculty(?fID, ?fname, ?_deptid),

    3 < count{?sID |

        Class(?cname, ?_room, ?fID),

        Enrolled(?sID, ?cname)

}.

Example Query 4: find the average age for each student level

For each level, print the level and the average age of students for that level.

? -Student(?_, ?_, ?_, ?level, ?_),

    ?avgAge = avg{?age |

        Student(?_sID, ?_sname, ?_major, ?level, ?age)

}.

Example Query 5: find the students enrolled in the maximum number of classes

Find the names of students enrolled in the maximum number of classes that students are enrolled in.

classesPerStudent(?sID, ?numberOfClasses) :-

    Student(?sID, ?_, ?_, ?_, ?_),

    ?numberOfClasses = count{?cname |

        Enrolled(?sID, ?cname)

}.

maxNumberOfClassesTakenByAStudent(?Max):-

    ?Max = max{?numberOfClasses |

        classesPerStudent(?_sID, ?numberOfClasses)

}.

?- Student(?sID, ?sname, ?_major, ?_level, ?_age),

    maxNumberOfClassesTakenByAStudent(?Max),

    ?Max = count{?cname |

        Enrolled(?sID, ?cname)

}.

Use case: Parts and Suppliers

Consider the following relations:

Suppliers(sid: integer, sname: string, address: string)
Parts(pid: integer, pname: string, color: string)
Catalog(sid: integer, pid: integer, cost: real)

Example Query 1: find the suppliers of red parts

Find the names of suppliers who supply some red part.

?- Suppliers(?sid, ?sname, ?_address),

    Catalog(?sid, ?pid, ?_cost),

    Parts(?pid, ?_pname, red).

Example Query 2: find the suppliers of red or green parts

Find the sids of suppliers who supply some red or green part.

?- Suppliers(?sid, ?_sname, ?_address),

    Catalog(?sid, ?pid, ?_cost),

        Parts(?pid, ?_pname, red);

        Parts(?pid, ?_pname, green)

).

Example Query 3: find the suppliers of red parts or located at 1 Main St

Find the sids of suppliers who supply some red part or are at 1 Main St.

?- (

        Suppliers(?sid, ?_sname, ?_address),

        Catalog(?sid, ?pid, ?_cost),

        Parts(?pid, ?_pname, red)

);

    Suppliers(?sid, ?_sname, '1 Main St').

Example Query 4: find the suppliers of red and green parts

Find the sids of suppliers who supply some red part AND some green part

?- Suppliers(?sid, ?_sname, ?_address),

    Catalog(?sid, ?pid, ?_cost),

    Parts(?pid, ?_pname, red),

    Catalog(?sid, ?pid2, ?_cost2),

    Parts(?pid2, ?_pname2, green).

Example Query 5: find the suppliers of all parts

Find the sids of suppliers who supply every part.

part(?pid):-

    Parts(?pid, ?_pname, ?_color).

?- Suppliers(?sid, ?_sname, ?_address),

    forall(?pid)^(

        part(?pid)

~~>

        exists(?cost)^(

            Catalog(?sid, ?pid, ?cost)

).

Another way to write this query uses aggregates:

?- ?TotalNumberOfParts = count{?pid | part(?pid)},

    Suppliers(?sid, ?_sname, ?_address),

    ?TotalNumberOfParts = count{?pid2 | Catalog(?sid, ?pid2, ?_cost)}.

Example Query 6: find the suppliers of all red parts

Find the sids of suppliers who supply every red part.

redPart(?pid):-

    Parts(?pid, ?_pname, red).

?- Suppliers(?sid, ?_sname, ?_address),

    forall(?pid)^(

        redPart(?pid)

~~>

        exists(?cost)^(

            Catalog(?sid, ?pid, ?cost)

).

Another way to write this query uses aggregates:

?- ?TotalNumberOfRedParts = count{?pid | redPart(?pid)},

    Suppliers(?sid, ?_sname, ?_address),

    ?TotalNumberOfRedParts = count{?pid2 | redPart(?pid2), Catalog(?sid, ?pid2, ?_cost)}.

Example Query 7: find the suppliers of all red or green parts

Find the sids of suppliers who supply every red or green part.

redOrGreenPart(?pid):-

    Parts(?pid, ?_pname, red).

redOrGreenPart(?pid):-

    Parts(?pid, ?_pname, green).

?- Suppliers(?sid, ?_sname, ?_address),

    forall(?pid)^(

        redOrGreenPart(?pid)

~~>

        exists(?cost)^(

            Catalog(?sid, ?pid, ?cost)

).

Another way to write this query uses aggregates:

?- ?TotalNumberOfRedOrGreenParts = count{?pid | redOrGreenPart(?pid)},

    Suppliers(?sid, ?_sname, ?_address),

    ?TotalNumberOfRedOrGreenParts = count{?pid2 | redOrGreenPart(?pid2), Catalog(?sid, ?pid2, ?_cost)}.

Example Query 8: find the suppliers of every red part or every green part

Find the sids of suppliers who supply every red part or supply every green part.

greenPart(?pid):-

    Parts(?pid, ?_pname, green).

query8(?sid) :-

        Suppliers(?sid, ?_sname, ?_address),

    forall(?pid)^(

        redPart(?pid)

~~>

        exists(?cost)^(

            Catalog(?sid, ?pid, ?cost)

).

query8(?sid) :-

    Suppliers(?sid, ?_sname, ?_address),

    forall(?pid)^(

        greenPart(?pid)

~~>

        exists(?cost)^(

            Catalog(?sid, ?pid, ?cost)

).

?- query8(?sid).

Another way to write this query uses aggregates:

query8_2(?sid) :-

    ?TotalNumberOfRedParts = count{?pid | redPart(?pid)},

    Suppliers(?sid, ?_sname, ?_address),

    ?TotalNumberOfRedParts = count{?pid2 | redPart(?pid2), Catalog(?sid, ?pid2, ?_cost)}.

query8_2(?sid) :-

    ?TotalNumberOfGreenParts = count{?pid | greenPart(?pid)},

    Suppliers(?sid, ?_sname, ?_address),

    ?TotalNumberOfGreenParts = count{?pid2 | greenPart(?pid2), Catalog(?sid, ?pid2, ?_cost)}.

?- query8_2(?sid).

Example Query 9: find the suppliers that sell a cheaper product than another supplier

Find pairs of sids such that the supplier with the first sid charges more for some part than the supplier with the second sid.

?- Catalog(?sid1, ?pid, ?cost1),

    Catalog(?sid2, ?pid, ?cost2),

    ?cost1 > ?cost2.

Example Query 10: find the minimum cost for a product

Find the minimum cost and supplier for each part.

minPrice(?pid, ?minCost) :-

    part(?pid),

    ?minCost = min{?cost | Catalog(?_sid, ?pid, ?cost)}.

?- minPrice(?pid, ?minCost),

    Catalog(?sid, ?pid, ?minCost).

Example Query 11: find the parts supplied by at least two different suppliers

Find the pids of parts supplied by at least two different suppliers.

?- Catalog(?sid1, ?pid, ?_minCost1),

    Catalog(?sid2, ?pid, ?_minCost2),

    ?sid1 != ?sid2.

Example Query 12: find the parts not supplied by any supplier

Find the pids of parts not supplied by any supplier

?- part(?pid),

\naf exists(?sid,?cost)^Catalog(?sid, ?pid, ?cost).

Example Query 13: find the parts that are supplied by exactly one supplier

Find the pids of parts supplied by exactly one supplier

?- part(?pid),

    Catalog(?sid1, ?pid, ?_cost),

    \naf exists(?sid2,?cost2)^(

        Catalog(?sid2, ?pid, ?cost2),

        ?sid1 != ?sid2

).

Example Query 14: find the most expensive part sold by ACME

Find the pids of the most expensive parts supplied by suppliers named ‘ACME’

maxPriceItemsSoldByAcme(?maxCost) :-

    Suppliers(?sid, 'ACME', ?_address),

    ?maxCost = max{?cost | Catalog(?sid, ?_pid, ?cost)}.

?- maxPriceItemsSoldByAcme(?maxCost),

    Suppliers(?sid, 'ACME', ?_address),

    Catalog(?sid, ?pid, ?maxCost).

Example Query 15: find the parts supplied by everyone

Find the pids of parts supplied by every supplier

supplier(?sid) :-

    Suppliers(?sid, ?_sname, ?_address).

query15(?pid) :-

    part(?pid),

    forall(?sid)^(

        supplier(?sid)

~~>

        exists(?cost)^(

            Catalog(?sid, ?pid, ?cost)

).

?- query15(?pid).

Another way to write this query is by using aggregates:

query15_2(?pid) :-

    ?countSuppliers = countdistinct{ ?sid | supplier(?sid)},

    part(?pid),

    ?countSuppliers = countdistinct{ ?sid |

        Catalog(?sid, ?pid, ?_cost)

}.

?- query15_2(?pid).

Page updated

Report abuse