In this lecture, we will look at some useful features of relational databases, such as views and triggers, how they can and cannot be used for knowledge representation. We will also look at rules (a special type of logical implications) and a deductive database, Lore. Lore introduces rule-based reasoning over relational databases.

Slides

Relevant Wiki-pages

• PostgreSQL
• Lore

Exercises

You are currently employed by The Ministry of Thruth (from George Orwell’s novel 1984) as their database administrator for their database on truth.

Their database is created using the following SQL-script:

DROP SCHEMA IF EXISTS truth CASCADE;

CREATE SCHEMA truth;

CREATE TABLE truth.statement (
    sid text PRIMARY KEY,
    stmt_text text NOT NULL
);

CREATE TABLE truth.true_at (
    sid text REFERENCES truth.statement(sid) NOT NULL,
    true_from timestamp NOT NULL,
    true_until timestamp 
);

CREATE TABLE truth.contradiction (
    sid1 text REFERENCES truth.statement(sid),
    sid2 text REFERENCES truth.statement(sid),
    PRIMARY KEY (sid1, sid2)
);

where stmt_text is the statement in plain text; sid is simply the md5 hash of the statement (i.e. sid = md5(stmt_text)); true_from is a timestamp stating when the corresponding statement is true; and true_until is a timestamp for when the statement no longer holds true. Note that sid is not unique in truth.true_at, so each statement can hold true in many intervals. However, you can assume that the intervals never overlap. If true_until is NULL, then the statement still holds true.

So statements are never really deleted, only set to (for now) no longer hold true.

The Ministry of Truth is perfectly fine with asserting statements that contradict our intuition or reality as a whole (e.g. 2+2=5), however, there are certain contradictions that you still do not want. Such unwanted contradictions are kept in the table truth.contradictions where sid1 contradicts sid2.

The SQL-script for creating the database schema can be downloaded here and some example data can be downloaded here. Execute both of these scripts over your database before you start doing the exercises. If you want to reset your database, simply execute the two scripts again, and the data will be reset.

Here is a script for testing your triggers, views, rules and Lore-rules. Execute this script after your have added the triggers/views/rules to see that they work correctly.

1 The World View

The Ministry of Truth often revises what should be true at the moment. It can then often be dificult to keep track of which statements are true now, and which are no longer (or not yet) true.

So, create a VIEW named truth.true_now(sid, stmt_text) that lists all statements that are true at the moment.

2 Trigger Happy

2.1 Automated Truth Maintenance

When a statement is first inserted, it should also be set to true from that point, and on. So make a trigger that in adition to INSERT-statements towards truth.statement, also inserts the statement (sid, now(), NULL) into truth.true_at.

Note that sid is the primary key, so a statement can only occur once in truth.statement. However, every INSERT-statement to this table has ON CONFLICT DO NOTHING appended. This means that your trigger needs to fire before the insert, otherwise your trigger would only fire on the first insert of a statement.

As noted above, a statement is never really deleted, is is simply not true anymore. So make a trigger that changes DELETE statements towards truth.statement to UPDATE statements that sets truth.true_at’s true_until to now() for the rows that have sid equal to the deleted statement.

2.2 Automated Contradiction Maintenance

This exercise concerns the truth.contradiction-table.

You realize that whenever a statement x contradicts a statement y, then it is also the case that y contradicts x. After making sure that the heads of The Ministry of Truth agrees with this fact, you want to rather have that whenever (x, y) is inserted into truth.contradiction, then also (y, x) should also be a contradiction. We assume that we only insert a statement once and that we never try to insert both (x, y) and (y, x) manually for any pair of statements x and y. You can introduce new tables if necessary. Hint: It is not possible/very difficult to have INSERT-triggers inserting into the same table (you are welcome to try ;), so you either need to make a VIEW or a different table that contains all “inferred” contradictions.

Whenever a statement is stated to be true now (i.e. we have an INSERT to truth.true_now, we also want to update true_until = now() for all the contradicting statements (as stated in truth.contradiction) in truth.true_at. Hint: One can have multiple INSTEAD OF INSERT-triggers on the same view, and they all fire on each INSERT.

3 PostgreSQL Rules

You realize that some of the triggers above can actually be rewritten to PostgreSQL rules. So rewrite the triggers defined in 2.1 and 2.2 into functionally equivalent PostgreSQL rules instead.

4 World Lore

4.1 The World View Revisited

After seeing the helpful simplicity of the syntax of PostgreSQL rules, you investigate other formalisms. You come accross Lore, and see that it is even simpler (almost like Newspeak!).

So, try to make the view from the exercise 1 as a backward chaining rule. You should then make truth.true_now as a RELATION rather than a view.

4.2 Implied Contradiction

You want to rewrite even more of the triggers/rules above, and see the greatest potential in truth.contradiction. So make truth.contradiction a RELATION and write the symmetry-trigger (i.e. INSERT of (x, y) should also add (y, x)) as a forward-chaning rule.

Note: If you want to “upgrade” an already existing TABLE t to a RELATION, you can write CREATE RELATION FROM TABLE t(<columns>), where <columns> are the same column definitions as the original table.

4.3 Implied Contradiction

After using your triggers, rules and Lore-rules for a while, you realize that they are not sufficient to capture the intended semantics that The Ministry of Truth had in mind. In particular, if a statement x implies another statement y, and x is true now, then so is y. Also, if x implies y and y contradicts z, then we should also have that x contradicts z.

Therefore, the ministry have now given you a relation of such implications, and a Lore-script making this relation (that also adds some concrete implications). The Lore-script is available from this URL:

http://leifhka.org/in5800/data/ministry_of_truth_implication.lore

Add an IMPORT statement importing this script to your Lore-script, and add a backward implication to truth.true_now and a forwad-implication to truth.contradiction capturing the new semantics described above.

Solution

The solution to the exercises can be found here.