8.3.1 Database manipulation

Representation of the chart in the prolog database.

There is one key key decision that we have to make before starting to implement the recognizer and that is how we are going to represent the chart, and how we are going to work with it.

Now, there are various options here. For example, we could represent the chart using some sort of structured list. But there is another, more attractive, way to go: represent the chart using the Prolog database, and manipulate the chart (that is, add new edges) using the database manipulation operations. As we are going to be making heavy use of Prolog's database manipulations, let's quickly run through them and remember how they worked.

There are five database manipulation commands that we will using:

    assert
    retract
    asserta
    assertz
    retractall

How are these used? Suppose we start with an empty database. So if we give the command:

?- listing.
yes

we get a yes --- and the listing (of course) is empty.

Suppose we now give this command:

?- assert(happy(mia)).
yes

It succeeds (the assert/1 commands always succeed). But what is important is not that it succeeds, but the side effect it has on the database, for if we now give the command:

?- listing.
 
happy(mia).
yes

we get again yes --- but now there is something in the database, namely the fact we asserted.

Suppose we then made four more assert commands:

?- assert(happy(vincent)).
yes
 
?- assert(happy(marsellus)).
yes
 
?- assert(happy(butch)).
yes
 
?- assert(happy(vincent)).
yes

and then ask for a listing. Then we get:

?- listing.
 
happy(mia).
happy(vincent).
happy(marsellus).
happy(butch).
happy(vincent).
yes

There is an inverse predicate to assert/1, namely retract/1. For example, if we go straight on and give the command:

?- retract(happy(marsellus)).
yes

and then list the database we get:

?- listing.
 
happy(mia).
happy(vincent).
happy(butch).
happy(vincent).
yes

Suppose we go on further, and say

?- retract(happy(vincent)).
yes

and then ask for a listing:

?- listing.
 
happy(mia).
happy(butch).
happy(vincent).
yes

Note that the first occurrence of happy(vincent) was removed. Prolog removes the first thing in the database that matches the argument of retract.

?- retract(happy(_)).
yes
?- listing.
 
happy(butch).
happy(vincent).
yes

The predicate retractall/1 removes everything that matches its argument:

?- retractall(happy(_)).
yes
?- listing.
yes

If we want more control over where the asserted material is placed, there are two variants of assert, namely:

Prolog puts some restrictions on what can be asserted and retracted. More precisely, other predicates are only allowed to remove or retract clauses of predicates that have been declared dynamic . So, if you want to write a predicate which asserts or retracts clauses of the form happy(mia), you also have to put the following statement into your file:

:- dynamic happy/1.

Database manipulation is useful when we want to store the results of queries, so that if we need to ask the same question in future, we don't need to redo the work --- we just look up the asserted fact. This technique is called `memoization', or `caching'. And of course, this `memoization' idea is the basic concept underlying chart-parsing: we want to store information about the syntactic structure we find, instead of having to re-compute it all the time.


Kristina Striegnitz, Patrick Blackburn, Katrin Erk, Stephan Walter, Aljoscha Burchardt and Dimitra Tsovaltzi
Version 1.2.5 (20030212)