Dynamic Knowledge Bases

Introduction

So far we have been dealing with static knowledge bases in which facts and rules never changed. Most real life applications, however, involve dynamic knowledge bases -- those whose data and rules do change as the time passes. This section discusses the issues involved and the subsequent sections on this page elaborate on each of these issues.

Static vs. dynamic facts:

• Loaded facts (introduced via the load{file} or [file] primitives) that have
  • no rule Ids (or other descriptors),
  • no UDFs,
  • no inline expressions (that use \is)

are always dynamic, i.e., they can be deleted from the knowledge base.

• Loaded facts that do involve one of the above features are static: they cannot be deleted.
  • However, they can be disabled temporarily (see later).
• Added facts (introduced via the add{file} or [+file] primitives) are always dynamic.
• Explicitly inserted facts (at runtime, via insert{...}) are also dynamic.

Static vs. dynamic rules:

• Loaded rules (introduced via load{file} or [file]) are always static: they cannot be deleted, but can be disabled temporarily.
• Added rules (introduced via the add{file} or [+file] primitives) are dynamic.
• Explicitly inserted rules (at runtime, via insertrule{...}) are also dynamic.
• Note: Inference with dynamic rules is about 20-30% slower than with static rules and they take more space.

Deletion vs. disabling:

• Deletion is irreversible. A deleted rule or fact can be reinstated only via another insert operation.
  • The advantage of deletion is that this releases the space occupied by the deleted items.
  • Deletion can affect multiple rules and facts that match a supplied pattern.
  • Deletion affects only dynamic rules/facts; static rules/facts cannot be deleted.
• Disablement is like deletion in that a disabled fact or rule can logically be thought of as having been deleted. But:
  • Disablement is reversible: a disabled rule or fact can be re-enabled later, which is logically equivalent to re-inserting the fact.
    • But disablement does not delete anything, so to re-enable one must know only the rule Id.
    • Dynamic facts cannot be disabled/re-enabled (only static facts can be). Dynamic facts are stored in some super-efficient data structures and can be only deleted or inserted.
  • Disabling/enabling can be performed only on facts/rules for which rule Ids are known. These operations need to know the rule Id but not how the actual rule/fact looks like.
  • Any rule can be disabled (static or dynamic), if one knows the rule Id.
    • Only static facts can be disabled.

Transactional vs. non-transactional update primitives:

• The update operations (inserts/deletes/enable/disable) can be transactional (a.k.a. atomic) or non-transactional (non-atomic).
• Transactional operations are atomic in the sense that if they succeed then all changes to the knowledge base made by the operation will stay. If some changes cannot be performed or if some intermediate tests fail, the partially done changes are rolled back.
  • Transactional operations are completely logical and declarative.
• Non-transactional operations, if they fail, may leave partial changes committed to the knowledge base. These operations are non-logical and may be dangerous to use. However,
  • Non-transactional operations are faster.
  • In some cases, a particular operation may be known to never fail. In this case, it is advantageous to implement such an operation as non-transactional because it will be faster while the effect will be the same.
    • Expert users often take advantage of the non-transactional nature of some operations.

Queries vs. actions:

• Once we introduce knowledge base changing operations, we have two kinds of predicates and frames: those whose definitions involve update operations and those that do not. The former are called actions (or transactions, if they are atomic) because they may change the underlying knowledge base. The latter are our familiar queries. Ergo uses special syntax for actions, as discussed below.

Inserting and Deleting Facts

Several facts can be inserted at once using a single insert operation. This can be done via the following query:

• insert{p(a), p(b), q[foo->1,bar->2], r[p->1,q->2]@mod1}.

The first three facts will be inserted into the current module and the last into the module mod1. The meaning of the "current module" depends on the context. If the above query was executed in the Ergo shell (on command line or in the Studio Listener) then this would be the module main. If the above was a query in a file (i.e., ?- insert{...}) then the current module would be the module into which that file is loaded or added. Note that the arguments to insert can contain variables. However this is rare and should be used only by advanced users.

The delete operation can likewise remove several facts from the knowledge base. The arguments here are Ergo literals and they can contain variables. For each argument, the following operation will delete some fact in the knowledge base that matches that argument. (It cannot be predicted which fact among the matching candidates will be picked up for removal.) For instance,

• delete{?X(?Y), ?(?), ?[?P->1], ?A[?B->1]@mod1}.

If the previous insert was executed followed by the above delete, Ergo will return the following:

?X = p

?Y = b

?P = foo

?A = r

?B = p

The module mod1 must exist or else an error will be issued; mod1 can be created via a previous load command or with the newmodule{mod1} query.

What will be left in the knowledge base? The following facts along with whatever might have been there before the above updates:

p(a) in the current module

q[bar->2] in the current module

r[q->2] in mod1

Notice that the two deletes of ?X(?Y) and of ?(?) have removed only one p-fact, p(b) because it happened to match both of these patterns. The fact p(a) has survived even though it also matches both patterns. If all matching facts are to be removed, the following should be used:

• deleteall{?X(?Y), ?[?P->?], ?A[?B->1]@mod1}.

This command will not bind any variables (unlike delete{...}) -- it will simply remove anything that matches the patterns in it. As a result, only the fact r[q->2] in mod1 will remain.

Important: the delete/deleteall operations will remove only the base facts, i.e., the facts that were loaded/added from a file and the previously inserted facts. They will not remove derived facts. To remove a derived fact, some of the underlying base facts must be removed. For instance, consider this example:

p(?X,?Y) :- q(?X,?Z), r(?Z,?Y).

q(1,2), q(1,4).

r(2,a), r(2,b), r(4,b), r(4,c).

Here the predicate p(...) will have these derived facts: p(1,a), p(1,b), p(1,c). We cannot remove p(1,b) directly because it is a derived fact. However, we could delete{q(1,2), q(1,4)} or delete{q(1,2), r(4,b)} or delete some other facts.

Observe that, in general, there is no way to delete precisely some set of derived facts: in our case, deleting q(1,2) will also remove p(1,a) -- perhaps an unintended consequence, but there is no general way to avoid such side effects.

Transactional Insert and Delete

Consider the following query:

• delete{p(b)}, p(?X), insert{q(?X)}.

After deleting p(b), there may or may not be something left in p(...) -- it all depends on what the knowledge base had before. If p(...) still has something, say, p(c), ?X might be bound to c and q(c) would be added to the knowledge base. (If p(d) is in the knowledge base then q(d) will be added also because Ergo will try to satisfy p(?X) in all possible ways.) But what if p(b) was the last fact left? Then p(...) will become empty and the query p(?X) will fail. As a result, the insert operation will never be executed. This is called non-atomic behavior of queries: the query may or may not execute in full. If it does not, partial results will be left in the knowledge base. Usually partial execution leaves garbage behind, and such queries and rules are very hard to debug. This happens because the result of the execution may depend on the transient contents of the knowledge base and what worked one day might not work the next one.

Transactional insert/delete to the rescue! The transactional versions of the above operations are

• tinsert
• tdelete
• tdeleteall

To illustrate, consider the following, transactional variant of the above query:

• tdelete{p(b)}, p(?X), tinsert{q(?X)}.

Looks very similar, but the result might be quite different. If p(?X) succeeds then this query will work exactly as the earlier non-transactional query. However, if p(?X) fails then the partial change made by the tdelete operation will be rolled back and no changes will be made to the knowledge base (and no garbage will be left behind).

Inserting and Deleting Rules

To insert and delete rules, one uses these commands:

• insertrule{rule1, rule2, ...}
• deleterule{rule-pattern1, rule-pattern2, ...}

If multiple patterns are used in the above commands, each must be enclosed in parentheses, e.g.,

insertrule{(a(?X):-b(?X)), (foo(?X,?Y):-moo(?X,?Z),bar(?X,?Y))}

if only one pattern appears then the surrounding parentheses are not needed.

The reason we talk about rule patterns in the above commands and not about rules is because these commands allow more general things that are not necessarily rules:

• In insertrule, what is important is that by the time this command is executed, all arguments must be bound to rules. For instance, neither ?X nor ?Y :- ?Z are valid rules. However, the following query will execute just fine because these variables get bound so that these expressions turn into rules:

?X=${p(?A):-?B}, ?Y=${h(?C)}, ?Z=${p(?A),q(?A,?C)}, insertrule{(?X), (?Y:-?Z)}.

The ${...} idiom is called reification and is explained below.

• In deleterule, the patterns don't even have to become bound to rules. For instance, in

deleterule{?H:-?B}.

?H:-?B is not a rule because bare variables cannot appear in rule heads in place of literals. Nevertheless, the above will work fine and will delete all previously dynamically inserted rules.

The commands insertrule and deleterule are non-transactional and there are no transactional versions for these commands.

However, an effect similar to deletion and re-insertion can be achieved via disabling and enabling of rules, which do have transactional versions. This is discussed in the next section.

About reification: The expressions wrapped in ${...} in the above example are called reified statements; they are described in section "Reification" in the ErgoAI Reasoner User's Manual. Briefly, Ergo distinguishes between object identifiers, which are denoted by terms, and truth-valued statements, like rules, facts, and queries. Object identifiers are global things that have the same meaning in all modules, but truth-valued statements may have different truth values in different modules. In the above insertrule example, ?X must be bound to a rule and ?Y, ?Z to the head and body of a rule, respectively. We need to tell, for example, that h(?C) is meant to be a truth-valued literal in the current module and not just an object identifier. Similarly, for p(?A):-?B we need to tell that this is a rule and not just a term written in infix form.

Enabling and Disabling Static Rules

If one knows the Id of a rule, it can be disabled and then re-enabled. A disabled rule is logically like a rule that never existed in the knowledge base. The difference with deleted rules is that all the information about disabled rules is preserved and the rules can be brought back to life using the enable primitive.

All rules (but not facts) have unique rule Ids consisting of three parts:

• Local Id
• File name
• Module

Local Id is what the user specifies explicitly in the @!{...} descriptor. If the user didn't give an explicit rule Id, it may be difficult to find the system-assigned rule Id and so enabling/disabling such rules might be problematic. Fortunately Ergo provides enough primitives to determine the local Ids even for such rules (for example clause{...}, see "Querying Rule Descriptors" in ErgoAI Reasoner User's Manual). The file name and module, on the other hand, are easy to determine. They are either known in advance or can be determined via the quasi-constants \@F and \@, respectively (see "Quasi-constants and Quasi-variables" in the aforesaid manual).

Given a rule Id, the corresponding rule can be enabled or disabled via these commands:

• enable{LocalId,File,Module}
• disable{LocalId,File,Module}

The transactional versions of these primitives are

• tenable{LocalId,File,Module}
• tdisable{LocalId,File,Module}

The following primitives also let one examine the current status of any rule:

• isenabled{LocalId,File,Module}
• isdisabled{LocalId,File,Module}

Transactional Predicates and Methods

Try to compile the following rule:

p(?X) :- insert{q(?X)}.

and you will see a warning like this:

++Warning[Ergo]> [somefile.ergo] <Dependency check>

                  non-transactional predicate or method in a rule that starts with `p(?A)' near line(...)/char(1)  depends on db operation `insert{ q(?A) }' near line(...)/char(9) in [somefile.ergo]

If one then tries to call, say p(abc), an error will result. It is possible to work around this warning and the error (read about ignore_depchk and stealth updates in the ErgoAI Reasoner User's Manual), but this is for experts only. What is going on here?

The problem is that normal predicates and frames are intended for querying only. A query is a request to gather information

about the current state of the knowledge base and it assumes that the state will remain the same after the query finishes.

This assumption is obviously violated in case of the query p(abc) because it implies that q(abc) must be inserted as part of the query evaluation. If the user indeed wanted to perform a state-changing operation as part of the evaluation, a transactional predicate (or frame) must be used in the above:

%p(?X) :- insert{q(?X)}.

Transactional predicates are distinguished by the %-sign, as above. Transactional frames also exist, but they have more limited syntax than the query frames. For instance:

op[%p(?X)] :- insert{q(?X)}.

Now, executing either %p(abc) or op[%p(abc)] will insert q(abc) into the knowledge base.

In sum:

• Query predicates/frames cannot depend on update operations (insert/delete/enable/etc.).
• If a rule body contains an update, the rule head must be a transactional predicate/frame.
• Transactional predicates are prefixed with the %-sign.
• Transactional frames have the form object[%method]. Neither object[%method->value] nor object[%method=>value] (nor the [|...|] variants) are supported by the syntax.

Dynamic Modules

We have already seen that files can be loaded into modules or added to them. If the respective modules don't exist, they are created. In addition, Ergo modules can be created out of thin air using the primitive

• newmodule{MyMod}.

The result is a new "empty" module named MyMod that has no rules or facts. (If module MyMod already exists, an error will result.)

Following that, rules and facts can be placed into that module via the insert/insertrule commands or added using the add{...} primitive.

Any module can be deleted via a query of the form

• erasemodule{MyMod}.

As a result of this operation, the module is deregistered and all the rules and facts that lived in the module will be destroyed. (If the module didn't exist, an error will be issued.) The module MyMod didn't have to be previously created using newmodule: it could have been created using the load or add commands and then destroyed by erasemodule.