Pinto, Floriana Di (Sapienza University of Rome) | Giacomo, Giuseppe De (Sapienza University of Rome) | Lenzerini, Maurizio (Sapienza University of Rome) | Rosati, Riccardo (Sapienza University of Rome)

In this paper we introduce the notion of mapping-based knowledge base (MKB) to formalize the situation where both the extensional and the intensional level of the ontology are determined by suitable mappings to a set of (relational) data sources. This allows for making the intensional level of the ontology as dynamic as traditionally the extensional level is. To do so, we resort to the meta-modeling capabilities of higher-order Description Logics, which allow us to see concepts and roles as individuals, and vice versa. The challenge in this setting is to design tractable query answering algorithms. Besides the definition of MKBs, our main result is that answering instance queries posed to MKBs expressed in Hi(DL-LiteR) can be done efficiently. In particular, we define a query rewriting technique that produces first-order (SQL) queries to be posed to the data sources.

Bartholomew, Michael (Arizona State University) | Lee, Joohyung (Arizona State University)

In classical logic, nonBoolean fluents, such as the location of an object and the color of a ball, can be naturally described by functions, but this is not the case with the traditional stable model semantics, where the values of functions are pre-defined, and nonmonotonicity of the semantics is related to minimizing the extents of predicates but has nothing to do with functions. We extend the first-order stable model semantics by Ferraris, Lee and Lifschitz to allow intensional functions. The new formalism is closely related to multi-valued nonmonotonic causal logic, logic programs with intensional functions, and other extensions of logic programs with functions, while keeping similar properties as those of the first-order stable model semantics. We show how to eliminate intensional functions in favor of intensional predicates and vice versa, and use these results to encode fragments of the language in the input language of ASP solvers and CSP solvers.

Resolution refutation is a powerful reasoning technique employed in many automated theorem provers. Various enhancements to resolution have enabled it to be used as a general question answering mechanism. Question answering systems employing resolution as the basic reasoning technique have been used to provide both "intensional" and "extensional" answers to questions by considering a theorem to be proven as a question. An intensional answer is a rule, such as "for all x and for all y if x is a cat and y is a dog then x detests y', and an extensional answer is a fact, such as "Rachel detests Fido". The notion of what constitutes an answer can be expanded so that, as resolution proceeds, the intermediate results generated on the way to finding an intensional or extensional answer may be regarded as answers. This view of resolution as answer generation, and resolvants as answers, requires an expanded notion of what constitutes an answer. A class of "hypothetical" answers is proposed, having the general form X Y, where X can not be proven based on the information in the knowledge base.

One of the most important lines of research in Description Logics (DLs) is concerned with the tradeoff between expressive power and computational complexity of sound and complete reasoning. Research carried out in the past on this topic has shown that many DLs with efficient, i.e., worstcase polynomial time, reasoning algorithms lack the modeling power required for capturing conceptual models and basic ontology languages, while most DLs with sufficient modeling power suffer from inherently worst-case exponential time behavior of reasoning [1, 2]. Although the requirement of polynomially tractable reasoning might be less stringent when dealing with relatively small ontologies, we believe that the need of efficient reasoning algorithms is of paramount importance when the ontology system is to manage large amount of objects (e.g., from thousands to millions of instances). This is the case of several important applications where the use of ontologies is advocated nowadays. For example, in the Semantic Web, ontologies are often used to describe the relevant concepts of Web repositories, and such repositories may incorporate very large data sets, which constitute the instances of the concepts in the ontology. In such cases, two requirements emerge that are typically overlooked in DLs. First, the number of objects in the knowledge bases requires managing instances of concepts (i.e., ABoxes) in secondary storage. Second, significant queries to be posed to the knowledge base are more complex than the simple queries (i.e., concepts and roles) usually considered in DL research.