Agents' beliefs can be incomplete and partially inconsistent. The process of agents' belief formation in such contexts has to be supported by suitable tools allowing one to express a variety of inconsistency resolving and nonmonotonic reasoning techniques.

In this paper we discuss 4QL*, a general purpose rule-based query language allowing one to use rules with negation in the premises and in the conclusions of rules. It is based on a simple and intuitive semantics and provides uniform tools for lightweight versions of well-known forms of nonmonotonic reasoning. In addition, it is tractable w.r.t. data complexity and captures PTIME queries, so can be used in real-world applications.

Reasoning in 4QL* is based on well-supported models. We simplify and at the same time generalize previous definitions of well-supported models and develop a new algorithm for computing such models.

In this paper we consider rule-based query languages with negation inbodies and heads of rules, traditionally denoted by DATALOG--. Tractable andat the same time intuitive semantics for DATALOG-- has not been provided evenif the area of deductive databases is over 30 years old. In this paper we identifysources of the problem and propose a query language, which we call 4QL.The 4QL language supports a modular and layered architecture and providesa tractable framework for many forms of rule-based reasoning both monotonicand nonmonotonic. As the underpinning principle we assume openness of theworld, which may lead to the lack of knowledge. Negation in rule heads may leadto inconsistencies. To reduce the unknown/inconsistent zones we introduce simpleconstructs which provide means for application-specific disambiguation ofinconsistent information, the use of Local Closed World Assumption (thus alsoClosed World Assumption, if needed), as well as various forms of default anddefeasible reasoning.

The paper discusses properties of 4QL, a DATALOG¬¬-like query language, originally outlined by Małuszy´nski and Szałas (Małuszy´nski & Szałas, 2011). 4QL allows one to use rules with negation in heads and bodies of rules. It is based on a simple and intuitive semantics and provides uniform tools for “lightweight” versions of known forms of nonmonotonic reasoning. Negated literals in heads of rules may naturally lead to inconsistencies. On the other hand, rules do not have to attach meaning to some literals. Therefore 4QL is founded on a four-valued semantics, employing the logic introduced in (Małuszy´nski et al., 2008; Vitória et al., 2009) with truth values: ‘true’, ‘false’, ‘inconsistent’ and ‘unknown’. In addition, 4QL is tractable w.r.t. data complexity and captures PTIME queries. Even though DATALOG¬¬ is known as a concept for the last 30 years, to our best knowledge no existing approach enjoys these properties. In the current paper we:

• investigate properties of well-supported models of 4QL
• prove the correctness of the algorithm for computing well-supported models
• show that 4QL has PTIME data complexity and captures PTIME.

A general framework is proposed for integration of rules and external first-order theories. It is based on the well-founded semantics of normal logic programs and inspired by ideas of Constraint Logic Programming (CLP) and constructive negation for logic programs. Hybrid rules are normal clauses extended with constraints in the bodies; constraints are certain formulae in the language of the external theory. A hybrid program consists of a set of hybrid rules and an external theory. Instances of the framework are obtained by specifying the class of external theories and the class of constraints. An example instance is integration of (non-disjunctive) Datalog with ontologies formalized in description logics. The paper defines a declarative semantics of hybrid programs and a goal-driven formal operational semantics. The latter can be seen as a generalization of SLS-resolution. It provides a basis for hybrid implementations combining Prolog with constraint solvers (such as ontology reasoners). Soundness of the operational semantics is proven. Sufficient conditions for decidability of the declarative semantics and for completeness of the operational semantics are given.

The purpose of this chapter is to report on work that has been done in the REWERSE project concerning hybrid reasoning with rules and ontologies. Two major streams of work have been pursued within REWERSE. They start from the predominant semantics of non-monotonic rules in logic programming. The one stream was an extension of non-monotonic logic programs under answer set semantics, with query interfaces to external knowledge sources. The other stream, in the spirit of the -log approach of enhanced deductive databases, was an extension of Datalog (with the well-founded semantics, which is predominant in the database area). The former stream led to so-called non-monotonic dl-programs and hex-programs, and the latter stream to hybrid well-founded semantics. Further variants and derivations of the formalisms (like a well-founded semantics for dl-programs, respecting probabilistic knowledge, priorities, etc.) have been conceived.

Rough set approximations of Pawlak [15] are sometimes generalized by using similarities between objects rather than elementary sets. In practical applications, both knowledge about properties of objects and knowledge of similarity between objects can be incomplete and inconsistent. The aim of this paper is to define set approximations when all sets, and their approximations, as well as similarity relations are four-valued. A set is four-valued in the sense that its membership function can have one of the four logical values: unknown (u), false (f), inconsistent (i), or true (t). To this end, a new implication operator and set-theoretical operations on four-valued sets, such as set containment, are introduced. Several properties of lower and upper approximations of four-valued sets are also presented.

This paper presents a language for defining four-valued rough sets and to reason about them. Our framework brings together two major fields: rough sets and paraconsistent logic programming. On the one hand it provides a paraconsistent approach, based on four-valued rough sets, for integrating knowledge from different sources and reasoning in the presence of inconsistencies. On the other hand, it also caters for a specific type of uncertainty that originates from the fact that an agent may perceive different objects of the universe as being indiscernible. This paper extends the ideas presented in [9]. Our language allows the user to define similarity relations and use the approximations induced by them in the definition of other four-valued sets. A positive aspect is that it allows users to tune the level of uncertainty or the source of uncertainty that best suits applications.