We consider first-order (FO) rewritability for query answering in ontology mediated querying (OMQ) in which ontologies are formulated in Horn fragments of description logics (DLs). In general, OMQ approaches for such logics rely on non-FO rewriting of the query and/or on non-FO completion of the data, called a ABox. Specifically, we consider the problem of FO rewritability in terms of Beth definability, and show how Craig interpolation can then be used to effectively construct the rewritings, when they exist, from the Clark’s completion of Datalog-like programs encoding a given DL TBox and optionally a query. We show how this approach to FO rewritability can also be used to (a) capture integrity constraints commonly available in backend relational data sources, (b) capture constraints inherent in mapping such sources to an ABox , and (c) can be used an alternative to deriving so-called perfect rewritings of queries in the case of DL-Lite ontologies.

Standard reasoning problems are complete for EXPTIME in common feature-based description logics—ones in which all roles are restricted to being functions. We show how to control conjunctions on left-hand-sides of subsumptions and use this restriction to develop a parameter-tractable algorithm for reasoning about knowledge base consistency. We then show how the resulting logic can simulate partial features, and present algorithms for efficient query answering in that setting.

A referring expression in linguistics is a noun phrase that identifies individuals to listeners. In the context of a query over a first order knowledge base, referring expressions to answers are usually constant symbols. This paper motivates and initiates the exploration of allowing more general formulas, called singular referring expressions, to replace constants in this role. Referring expression types play a novel and significant role in analyzing the properties of candidate expressions.

Many keyword queries issued to Web search engines target information about real world entities, and interpreting these queries over Web knowledge bases can often enable the search system to provide exact answers to queries. Equally important is the problem of detecting when the reference knowledge base is not capable of answering the keyword query, due to lack of domain coverage.

We consider a generalization of instance retrieval over knowledge bases that provides users with assertions in which descriptions of qualifying objects are given in addition to their identifiers. Notably, this involves a transfer of basic database paradigms involving caching and query rewriting in the context of an assertion retrieval algebra. We present an optimization framework for this algebra, with a focus on finding plans that avoid any need for general knowledge base reasoning at query execution time when sufficient cached results of earlier requests exist.

Current optimization techniques for answering queries over Semantic Web data use realization to precalculate the individuals associated with every concept in the given ontology. However, this technique does not take into account the type of queries, written for example in nRQL or SPARQL-DL, that will arrive at the system. In this paper we propose how this additional knowledge can be used to create query-specific indices. We include experimental results that show how our approach can be used to improve the performance of the Pellet query engine for the popular LUBM benchmark.

Automated extraction of structured data from Web sources often leads to large heterogeneous knowledge bases (KB), with data and schema items numbering in the hundreds of thousands or millions. Formulating information needs with conventional structured query languages is difficult due to the sheer size of schema information available to the user. We address this challenge by proposing a new query language that blends keyword search with structured query processing over large information graphs with rich semantics. Our formalism for structured queries based on keywords combines the flexibility of keyword search with the expressiveness of structures queries.

Model checking is an automated technique for the verification of finite-state systems that is widely used in practice. In Bounded Model Checking (BMC) the system is checked only until a given execution depth from the initial state. State of the art model checkers apply Binary Decision Diagrams (BDDs) as well as Satisfiability Solving (SAT) for this task. However, both methods suffer from the state explosion problem, which restricts the application of model checking to only modestly sized systems. The importance of model checking makes it worthwhile to explore alternative technologies, in the hope of enabling the application of the technique to a wider class of systems. Description Logic (DL) is a family of knowledge representation formalisms, mainly used for designing ontologies, for which reasoning is based on tableaux techniques. In this article, we show how model checking problems can be solved using DL reasoning. We present two different encodings of a model checking problem as a consistency check in DL, and show how DL can serve as a natural setting for representing and solving a BMC problem. Experimental results, using the DL reasoner FaCT++, give encouraging results.

Recent work on Web-extracted data sets has produced an interesting new source of structured Web data. These data sets can be viewed as knowledge bases (KB) -- large heterogeneous linked entity collections with millions of unique edge and node labels, often encoding rich semantic information over entities. For example, YAGO [5] and ExDB [2] have fact collections numbering in the tens and hundreds of millions respectfully, and WebTables [1] contains over one hundred million extracted relations. In terms of schema information, the ExDB, YAGO, and WebTables data sets all have schema items numbering in the millions.

Object layout schemes used in C++ and other languages rely on (sometimes numerous) compiler generated fields. We describe a language-independent object layout scheme, which is space optimal, that is, objects are contiguous, and contain no compiler generated fields other than a single type identifier. As in C++ and other multiple inheritance languages such as CECIL and DYLAN, the new scheme sometimes requires extra levels of indirection to access some of the fields. Using a data set of 28 hierarchies, totaling almost 50,000 types, we show that this scheme improves field access efficiency over standard implementations, and competes favorably with (the non-space-optimal) highly optimized C++ specific implementations. The benchmark includes an analytical model for computing the frequency of indirections in a sequence of field access operations. Our layout scheme relies on whole-program analysis, which requires about 10 microseconds per type on a contemporary architecture (Pentium III, 900Mhz, 256MB machine), even in very large hierarchies. We also present a layout scheme for separate compilation using the user-annotation of virtual inheritance edge that is used in C++.

Uniqueness constraints such as keys and functional dependencies in the relational model are a core concept in information systems technology. We consider uniqueness constraints suitable for object relational data models and identify a boundary between tractable and intractable varieties. The subclass that is tractable is still a strict generalization of both keys and relational functional dependencies. We present an efficient decision procedure for the logical implication problem of this subclass. The problem itself is formulated as an implication problem for a simple dialect of description logic (DL). DLs are a family of languages for knowledge representation that have many applications in information systems technology and for which model building procedures have been developed that can decide implication problems for dialects that are very expressive. Our own procedure complements this approach and can be integrated with these earlier procedures. Finally, to motivate our results, we review some applications of our procedure in query optimization.

Virtually all semantic or object-oriented data models assume that objects have an identity separate from any of their parts, and allow users to define complex object types in which part values may be any other objects. This often results in a choice of query language in which a user can express navigating from one object to another by following a property value path. We consider a constraint language in which one may express equations and functional dependencies over complex object types. The language is novel in the sense that component attributes of individual constraints may correspond to property paths. The kind of equations we consider are also important, because they are a natural abstraction of the class of conjunctive queries for query languages that support property value navigation. In our introductory comments, we give an example of such a query and outline two applications of the constraint theory to problems relating to a choice of access plan for the query. We present a sound and complete axiomatization of the constraint language for the case in which interpretations are permitted to be infinite, where interpretations themselves correspond to a form of directed labeled graph. Although the implication problem for our form of equational constraint alone over arbitrary schema is undecidable, we present decision procedures for the implication problem for both kinds of constraints when the problem schema satisfies a stratification condition, and when all input functional dependencies are keys.>

We propose a more general form of functional dependency for semantic data models that derives from their common feature in which the separate notions of domain and relation in the relational model are combined into a single notion of class . This usually results in a richer terminological component for their query languages, whereby terms may navigate through any number of properties, including none. We prove the richer expressiveness of this more general functional dependency, and exhibit a sound and complete set of inference axioms. Although the general problem of decidability of their logical implication remains open at this time, we present decision procedures for cases in which the dependencies included in a schema correspond to keys, or in which the schema itself is acyclic. The theory is then extended to include a form of conjunctive query. Of particular significance is that the query becomes an additional source of functional dependency. Finally, we outline several applications of the theory to various problems in physical design and in query optimization. The applications derive from an ability to predict when a query can have at most one solution.

Much recent work in polymorphic programming languages allows subtyping and multiple inheritance for records. In such systems, we would like to extract a field from a record with the same efficiency as if we were not making use of subtyping and multiple inheritance. Methods currently used make field extraction 3-5 times slower, which can produce a significant overall performance slowdown.

A variation of the index selection problem for an extended relational model when all encoding of information is memory resident is discussed. The data model is the relational model extended in two ways that are common with semantic data models. One consequence of memory residence is that the search space of possible indexes is enlarged to the extent that previous methods requiring some consideration of each possibility are no longer possible. An instance of the index selection problem that includes a set of partial match queries in addition to the input schema is given. It is assumed that the set is determined by an initial phase of query optimization when applied to a fixed set of more general forms of queries that characterize the way in which information is accessed for an application. An initial choice of indexes is made, only considering their suitability for answering the partial match queries.>