This is an archive of an inactive wiki and cannot be modified.

Interpretations

Model-theoretic semantics of RIF dialects is defined using the notion of an interpretation. Different dialects are expected to have different notions of interpretations. For instance, some dialects might use standard first-order semantic structures (FOL dialect, stable model semantics based dialects), others might use three valued Herbrand interpretations (the dialects based on the Well-founded Semantics for negation), yet others might use four-valued or multivalued interpretations (dialects that deal with uncertain and inconsistent information). A good survey of these issues can be found in http://citeseer.ist.psu.edu/fitting99fixpoint.html.

However, many of the different semantics can be defined in a uniform way. What unifies all of them is that an interpretation, I, is defined as a collection of mappings of the form

Iv: Set of formulas --> Set of truth values

where v is a variable assignment, i.e., a mapping that maps each variable in the language to the domain of the interpretation. This mapping has an effect only on the free variables of each formula. Thus, if φ is a formula then Iv(φ) is its truth value.

The other element that is common to many popular semantics is that there is a fixed total or partial order on the set of truth values, called the truth order and denoted <t. For instance, in the first-order semantics, f <t t. In the well-founded semantics, f <t u <t t (where u denotes undefined). In Belnap-style four-valued logics, which are suitable for dealing with uncertain or imprecise information, the truth order is f <t u <t t and f <t i <t t, where i is the truth value that denotes inconsistency. Belnap-style logics also have another order, called the knowledge order <k: u <k t <k i; and u <k f <k. Under the knowledge order, true and false are incomparable, and facts that are both true and false receive the truth value i, which is the least upper bound of f and t in the knowledge order.

SEMANTICS OF CONDITIONS

The semantics of the expressions of the RIF Condition Language is determined by the Iv mappings that correspond to the particular dialect of the condition language. Regardless of the dialect, these mappings satisfy the usual condititions such as Iv(φ /\ ψ) = mint(Iv(φ), Iv(ψ)), Iv(φ \/ ψ) = maxt(Iv(φ), Iv(ψ)), and Iv(neg φ) = - Iv(φ), Iv(naf φ) = - Iv(φ), where "-" is an operator on the set of truth values, which typically has these properties: -f=t, -t=f, -u=u, -i=i. Here mint and maxt are minimum and maximum with respect to the truth order.

Note that neg and naf are treated similarly when it comes to interpretation. The main difference is in how these two styles of negation affect the choice of intended models of a rule set (see the section on intended models). In a nutshell, neg dosnt affect the choice of intended models at all, so, for example, p :- neg q is the same as p \/ q and has two kinds of intended models: one in which p is true and another where q is true. In contrast, p :- naf q has only one intended model -- the one where p is true and q is false.

SEMANTICS OF RULES

While interpretations may be multivalued, rules are typically two-valued even in logics that support inconsistency and uncertainty. Consider a rule of the form Q head :- body, where Q is a quantification prefix for all the variables that are shared by head and body (we will later restrict Q to a universal prefix), and let v be a variable assignment. We assume that the variables mentioned in Q are the only ones that are free both in head and body. We first define the notion of rule satisfaction with respect to a variable assignment and without the quantification prefix Q:

I |=v head :- body

iff Iv(head) ≥ Iv(body).

Finally, we define I |= Q head :- body irrespective of the variable assignment v. For the first-order semantics, this can be defined for any quantification prefix Q. For non-monotonic semantics, such as the well-founded or stable semantics, rule heads and bodies are assumed to share only universally quantified variables. Therefore, we assume that Q is a universal prefix. Under this assumption, we write

I |= Q head :- body

iff I |=v head :- body for all variable assignments v. In this case we also say that I is a model of the rule.

Intended Models and Query Answering

A model I of a rule set R is an interpretation such that I |= r for every rule r ∈ R. The semantics of a rule set, however, is based on the notion of intended models. In the first-order semantics, all models are intended. The semantics for rules used in Logic Programming and Databases (the well-founded and the stable semantics), on the other hand, recognize only a subset of all models as intended. For instance, in case of the well-founded semantics (when rules don't have disjunction in the head) there is only one intended model -- the well-founded model. It always exists, but sometimes may not be very useful. For instance, p :- not p has a unique well-founded model, but p has the truth value u there. In case of the stable model semantics, there can be multiple intended models or none at all. For instance, p :- naf p has no stable models, but p :- naf q and q :- naf p has two stable models: {p} and {q}.

The fact that only some models are intended can have serious impact on query answering under the different semantics. For instance, the rule set {p :- naf p} has no intended models under the well-founded and stable semantics, but {p :- neg p} it has intended models under the first-order semantics. On the other hand, for the rule set { p :- naf q }, p has a unique intended model under the well-founded and stable semantics, but it has many more intended models under the first-order semantics (with naf replaced by neg). As a result, the well-founded and the stable model semantics imply that p is true and q is false, while the first-order semantics implies neither.

Given a set of rules R and a query predicate Q, the set of answers to Q is the set of all ground instantiations q of Q such that I |= q for all intended models I of R.

Semantics of "Classical" Negation neg in the Logic Programming Dialects

The semantics of atomic neg in the models of the FO dialect is standard. For LP dialects supporting "classical" negation, neg-negated predicates are interpreted by fresh predicates that are appropriately axiomatized. For instance, neg of p is associated with a fresh predicate, Neg_p, and neg p(...) is said to be true in a model iff Neg_p(...) is. It is also required that for any given tuple of ground arguments, the formulas p(...) and Neg_p(...) cannot be true in the same model.

The following (Phase 2) dialects of RIF will support neg and/or naf:

Queries and integrity constraints can use those forms of negation that are supported by the rulesets that they constrain or query.

Recall that to distinguish the different possible semantics for the same ruleset, RIF will define an attribute that will explicitly specify the semantics under which the corresponding ruleset is to be interpreted.