Rule languages


Revision as of 22:20, 27 November 2010 by Markus Krötzsch (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Many formalisms in knowledge representation and reasoning are rule languages, vaguely defined by the usage of logical «rules» as a basic expressive feature. Some rule formalisms are declarative, others are not.

Rule-based modelling is sometimes considered to be more intuitive, in particular for people who have been trained in computer science, and who like to interpret rules as «if-then» statements even in formalisms that behave quite different to a imperative programming language. Even if formally incorrect, such intuitions can sometimes ease adoption in practical applications. (As a side remark, it should be noted that scientific communities outside of computer science, e.g. in the life sciences, often choose variable-free syntaxes instead of rules for knowledge representation; I am not aware of any overwhelming practical evidence that one or the other approach is cognitively more adequate in general).

From a more technical perspective, rule languages tend to be highly expressive since unrestricted rule premisses can capture arbitrary relational structures – without a mechanism for ensuring finiteness of the conceptual domain (as in Datalog where rules are only applied to a limited number of constants) or finiteness of computation (such as in non-recursive logic programs), this modelling power quickly leads to undecidability/non-termination.

On the other hand, formalisms which are more restricted by design may lack rule-like modelling power even in cases where it would not be problematic. Description Logics with their variable-free syntax are a typical example of this, and some of my works described feasible rule language extensions for this case (see description logic rules and ELP; the most comprehensive introduction is given in my dissertation).

Besides the introduction of rule-like expressivity into KR formalisms, it is also interesting to try and extend rule languages with expressive features that they tend to exclude. This involves, for example, the extension of the basic database query language Datalog with features such as existential quantification (tuple generation/value invention), disjunction, or equality.

Publications related to this topic

Updates to the following list are also available as RSS feed. A list of all publications is also available.

enRule languages
Personal tools