FrançaisGet started

The deductive database: facts and rules

A database made of stored facts and rules that deduce others, in Datalog: reading a rule, asking a query, deducing by hand what a non-recursive rule produces, and relating it to relational algebra.

  • 26 cards
  • 5 topics
  • Free
Study this deck

The outline, topic by topic

Each topic is weighted the way the exam weighs it.

  1. Concepts
  2. Questions
  3. Sort and link
  4. Scenarios
  5. Understand

A few cards from the deck

  • Deductive database: what is it?

    Show the answer

    A database holding stored facts and rules, which deduces on demand further facts that were never written into it.

    A relation such as grandparent need not be stored: the rule rebuilds it from the parents, and it follows the facts when they change.

  • With these facts and this rule, which frere_ou_soeur facts are deduced?

    ```prolog
    parent(ana, bob).
    parent(ana, cleo).
    parent(bob, dan).

    frere_ou_soeur(X, Y) :- parent(P, X), parent(P, Y), X != Y.
    `

    • frere_ou_soeur(bob, cleo) and frere_ou_soeur(cleo, bob)
    • Only frere_ou_soeur(bob, cleo)
    • frere_ou_soeur(bob, cleo), frere_ou_soeur(cleo, bob) and frere_ou_soeur(dan, dan)
    • None, since no parent is shared by two distinct parent facts
    Show the answer

    frere_ou_soeur(bob, cleo) and frere_ou_soeur(cleo, bob)

    With P = ana, X and Y each take bob and cleo: four pairs, two of them removed by X != Y. The two left are symmetric, since the rule sets no order between X and Y. With P = bob, the only pair is (dan, dan), removed as well: dan has no sibling.

  • In a rule, what comes before :- is called the … and what follows it the ….

    Show the answer

    In a rule, what comes before :- is called the head and what follows it the body.

    The head is the conclusion, a single atom; the body is the list of conditions, separated by commas read as "and".

  • Datalog: what is it?

    Show the answer

    A rule language for deductive databases, where you write facts and rules without function symbols, and query with a goal.

    With no function symbols, a rule makes no new value: it combines the constants already there, so every question has a finite set of answers and deduction always ends.

  • A table chef_du_chef(employe, grand_chef) is filled in by hand every week from chef(employe, chef). It often lags behind org chart changes. Which fix keeps it always correct?

    • Run the filling every day instead of every week
    • Deduce it from a rule: chef_du_chef(E, G) :- chef(E, C), chef(G, C).
    • Also store the grand-boss in every chef fact
    • Deduce it from a rule: chef_du_chef(E, G) :- chef(E, C), chef(C, G).
    Show the answer

    Deduce it from a rule: chef_du_chef(E, G) :- chef(E, C), chef(C, G).

    A table copied by hand is stored derived data: it can drift from the facts. A rule recomputes at each question and so always follows chef, provided it chains the two facts through the middle boss C: chef(E, C), chef(G, C) links two employees with the same boss. More frequent filling shortens the lag without removing it.

Study this deck