Search

This is an introduction to integrating logic programs with first order theories. The main motivation are the needs of Semantic Web to combine reasoning based on rule systems with that based on Description Logics (DL). We focus on approaches which are able to re-use existing reasoners (for DL and for rule systems). A central issue of this paper is non-monotonic reasoning, which is possibly the main feature of rule based reasoning absent in DL. We discuss the main approaches to non-monotonic reasoning in logic programming. Then we show and classify various ways of integrating them with first order theories. We argue that for practical purposes none of the approaches seems sufficient, and an approach combining the features of so-called tight and loose coupling is needed.

The problem of integration of rules and ontologies is addressed in a general framework based on the well-founded semantics of normal logic programs and inspired by the ideas of Constraint Logic Programming (CLP). Hybrid rules are defined as normal clauses extended with constraints in the bodies. The constraints are formulae in a language of a first order theory defined by a set T of axioms. Instances of the framework are obtained by specifying a language of constraints and providing T. A hybrid program is a pair (P, T) where P is a finite set of hybrid rules. Thus integration of (non-disjunctive) Datalog with ontologies formalized in a Description Logic is covered as a special case. The paper defines a declarative semantics of hybrid programs and a formal operational semantics. The latter can be seen as an extension of SLS-resolution and provides a basis for hybrid implementations combining Prolog with constraint solvers. In the restricted case of positive rules, hybrid programs are formulae of FOL. In that case the declarative semantics reduces to the standard notion of logical consequence. The operational semantics is sound and it is complete for a restricted class of hybrid programs.

The paper presents an architecture and implementation techniques for hybrid integration of normal clauses under well-founded semantics with ontologies specified in Description Logics. The described prototype uses XSB Prolog both for rule reasoning and for controlling communication with the ontology reasoner RacerPro. The query answering techniques for hybrid rules implemented in this prototype are sound wrt. the declarative semantics, extending the well-founded semantics of normal programs and are faithful wrt. FOL.

In previous papers we presented a type system for a substantial fragment of the Web query language Xcerpt. It is a descriptive type system: the typing of a program is an approximation of its semantics. The type system was expressed by means of rules, which could be seen as a comprehensible abstraction of a typing algorithm. That system treats some query terms in a rather simplistic way. As a result the approximations produced for them are rather imprecise. In this paper we provide an improved type system, producing more precise results.

The paper presents a prototype implementation of a descriptive type system for the XML query language Xcerpt. Its intended application is finding (a certain kind of) errors in programs. The implementation is able to check correctness of an Xcerpt program with respect to a type specification. A type specification describes a set of possible data bases to which the program is to be applied and an expected set of results. Program correctness means that all its results are in the expected set. Failure of a correctness check suggests an error in the program. Under certain conditions such failure indeed means that the program is incorrect. Current implementation works for a restricted, but interesting subset of Xcerpt. The system provides (approximations of) the set of program results and the sets of values of program variables; this information is useful for programmers (and is produced even when the specification of the expected set of results is not given).

We present typing rules for the Web query language Xcerpt. The rules provide a descriptive type system: the typing of a program is an approximation of its semantics. The rules can also be seen as an abstract form of a type inference algorithm (presented in previous work), and as a stage in a formal soundness proof of the algorithm. The paper considers a substantial fragment of Xcerpt; the main restriction is that we deal with data terms corresponding to trees (instead of general graphs), and we do not deal with Xcerpt rule chaining. We provide a formal semantics for the fragment of Xcerpt and a soundness theorem for the presented type system.

Our intention is to provide a type system for rule languages used in web applications. In this work we deal with an XML query language Xcerpt. Our types are sets of documents. We represent XML data as so called data terms and propose a formalism to define sets of data terms. The formalism is a generalization of tree automata; the defined sets roughly correspond to sets of documents definable by means of XML schema languages, like DTD and XML Schema. The main contribution of this paper is an algorithm for computing the type of possible results of an Xcerpt rule, given the type of the database. The algorithm can be used to automatically check correctness of Xcerpt programs with respect to type specifications. For non recursive Xcerpt programs it can also be used to compute the type of program results.

We advocate a declarative approach to proving properties of logic programs. Total correctness can be separated into correctness, completeness and clean termination; the latter includes non-floundering. Only clean termination depends on the operational semantics, in particular on the selection rule. We show how to deal with correctness and completeness in a declarative way, treating programs only from the logical point of view. Specifications used in this approach are interpretations (or theories). We point out that specifications for correctness may differ from those for completeness, as usually there are answers which are neither considered erroneous nor required to be computed.We present proof methods for correctness and completeness for definite programs and generalize them to normal programs. The considered semantics of normal programs is the standard one, given by the program completion in 3-valued logic.The method of proving correctness of definite programs is not new and can be traced back to the work of Clark in 1979. However a more complicated approach using operational semantics was proposed by some authors. We show that it is not stronger than the declarative one, as far as properties of program answers are concerned.

Given a logic program P and a goal G, we introduce a notion which states when an SLD-tree for P∪{G} instantiates a, set of variables V with respect to another one, W. We call this notion weak instantiation, as it is a generalization of the instantiation property introduced in [3]. A negation rule based on instantiation, the so-called Negation As Instantiation rule (NAI), allows for inferring existentially closed negative queries, that is formulas of the form ∃¬Q, from logic programs. We show that, by using the new notion, we can infer a larger class of negative queries, namely the class of the queries of the form ∨W∃V¬Q and of the form ∨W∃V∨Z¬Q, where Z is the set of the remaining variables of Q.