David Toman

AAAI Conference 2022 Conference Paper

First Order Rewritability in Ontology-Mediated Querying in Horn Description Logics

• David Toman
• Grant Weddell

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 an 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 as an alternative to deriving so-called perfect rewritings of queries in the case of DL-Lite ontologies.

AAAI Conference 2019 Conference Paper

On Limited Conjunctions and Partial Features in Parameter-Tractable Feature Logics

• Stephanie McIntyre
• Alexander Borgida
• David Toman
• Grant Weddell

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.

KR Conference 2018 Short Paper

On Limited Conjunctions in Polynomial Feature Logics, with Applications in OBDA

• Stephanie McIntyre
• Alex Borgida
• David Toman
• Grant Weddell

Standard reasoning problems are complete for EXPTIME in common feature-based description logics—ones in which all roles are restricted to being functional. We show how to control conjunctions on left-hand-sides of subsumptions in such a way so as to ensure polynomial time complexity. In particular, we present a PTIME algorithm for reasoning about knowledge base consistency. We then show how the resulting description logic allows features to be partial, not just total functions. Algorithms for polynomial-time query answering are presented. The above, in combination with referring expressions, provide a richer capability for ontology-based data access to relational data sources.

IJCAI Conference 2017 Conference Paper

Concerning Referring Expressions in Query Answers

• Alexander Borgida
• David Toman
• Grant Weddell

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.

IJCAI Conference 2016 Conference Paper

Object-Relational Queries over CFDI nc Knowledge Bases: OBDA for the SQL-Literate

• Jason St. Jacques
• David Toman
• Grant Weddell

We consider how SQL-like query languages over object-relational schemata canbe preserved in the setting of ontology based data access (OBDA), thus leveraging wide familiarity with relational technology. This is enabled by the adoption of the logic CFDnc-forall, a member of the CFD family of description logics (DLs). Of particular note is that this logic can fully simulate DLlite-F, a member ofthe DL-Lite family commonly used in the OBDA setting. Our main results present efficient algorithms that allow computation ofcertain answers with respect to CFDnc-forall nowledge bases, facilitating direct access to a pre-existing row-basedrelational encoding of the data without any need for mappings to triple-based representations.

KR Conference 2016 Conference Paper

On Referring Expressions in Query Answering over First Order Knowledge Bases

• Alex Borgida
• David Toman
• Grant Weddell

this are identifiers that individual authors or the sysA referring expression in linguistics is any noun phrase identifying an object in a way that will be useful to interlocutors. In the context of a query over a first order knowledge base K, constant symbols occurring in K are the artifacts usually used as referring expressions in certain answers to the query. In this paper, we begin to explore how this can be usefully extended by allowing a class of more general formulas, called singular referring expressions, to replace constants in this role. In particular, we lay a foundation for admitting singular referring expressions in certain answer computation for queries over K. An integral part of this foundation are characterization theorems for identification properties of singular referring expressions for queries annotated with a domain specific language for referring concept types. Finally, we apply this framework in the context of tractable description logic dialects, showing how identification properties can be determined at compiletime for conjunctive queries, and how off-the-shelf conjunctive query evaluation for these dialects can be used in query evaluations, preserving, in all cases, underlying tractability.

AAAI Conference 2014 Conference Paper

Cost-Based Query Optimization via AI Planning

• Nathan Robinson
• Sheila McIlraith
• David Toman

In this paper we revisit the problem of generating query plans using AI automated planning with a view to leveraging significant advances in state-of-the-art planning techniques. Our efforts focus on the specific problem of cost-based joinorder optimization for conjunctive relational queries, a critical component of production-quality query optimizers. We characterize the general query-planning problem as a deletefree planning problem, and query plan optimization as a context-sensitive cost-optimal planning problem. We propose algorithms that generate high-quality query plans, guaranteeing optimality under certain conditions. Our approach is general, supporting the use of a broad suite of domainindependent and domain-specific optimization criteria. Experimental results demonstrate the effectiveness of AI planning techniques for query plan generation and optimization.

KR Conference 2012 Short Paper

Assertion Absorption in Object Queries over Knowledge Bases

• Jiewen Wu
• Alexander Hudek
• David Toman
• Grant Weddell

eral DL reasoner will include far more instances of assertion membership tasks than of knowledge base consistency tasks. Thus, this separation of concerns can enable technology that is far more efficient for such workloads, particularly so in the case of “non-Horn” DLs that preclude the possibility of computing so-called canonical ABoxes (such as DLs that include disjunction). In this paper, we contribute to this development by introducing a novel absorption technique for knowledge bases and demonstrate that the technique is efficacious for workloads that contain many thousands of assertion membership tasks. To date, work on absorption has focused on the concept satisfaction problem, a simple case of the assertion membership problem for knowledge bases with an ABox consisting of a single assertion a: >. Indeed, it has been known for some time in this case that lazy unfolding is an important optimization technique in model building algorithms for satisfiability (Baader et al. 1994). It is also imperative for a large TBox to be manipulated by an absorption generation process to maximize the benefits of lazy unfolding in such algorithms, thereby reducing the combinatorial effects of disjunction in underlying chase procedures (Horrocks 1998). We build on earlier work reported at the description logics workshop (Hudek and Weddell 2006) that proposed a generalization of the absorption theory and algorithms developed in (Horrocks and Tobies 2000a; 2000b) for the problem of concept satisfaction. The generalization makes it possible for lazy unfolding to be used for parts of terminologies not handled by earlier absorption algorithms and theory. Binary absorption combines two key ideas. The first is the possibility of avoiding the need to internalize (at least some of the) terminological axioms of the form (A1 uA2) v C, where the Ai denote primitive concepts and C a general concept. The second is an idea relating to role absorptions developed by Tsarkov and Horrocks (Tsarkov and Horrocks 2004). These ideas, in combination and when coupled with standard equivalences, make it possible for an algorithm to completely absorb, e. g., the TBox definition. GOODCLIENT = CLIENT u (∃Recommend−. BANK) (∃Buy. (COSTLY t PROFITABLE)) We develop a novel absorption technique for large collections of factual assertions about individual objects. These assertions are commonly accompanied by implicit background knowledge and form a knowledge base. Both the assertions and the background knowledge are expressed in a suitable language of Description Logic and queries over such knowledge bases can be expressed as assertion retrieval queries. The proposed absorption technique significantly improves the performance of such queries, in particular in cases where a large number of object features are known for the objects represented in such a knowledge base. In addition to the absorption technique we present the results of a preliminary experimental evaluation that validates the efficacy of the proposed optimization.

IJCAI Conference 2011 Conference Paper

An Assertion Retrieval Algebra for Object Queries over Knowledge Bases

• Jeffrey Pound
• David Toman
• Grant Weddell
• Jiewen Wu

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.

IJCAI Conference 2011 Conference Paper

Fixpoints in Temporal Description Logics

• Enrico Franconi
• David Toman

We study a decidable fixpoint extension of temporal description logics. To this end we employ and extend decidability results obtained for various temporally first-order monodic extensions of (first-order) description logics. Using these techniques we obtain decidability and tight complexity results for various fixpoint extensions of temporal description logics.

IJCAI Conference 2011 Conference Paper

The Combined Approach to Ontology-Based Data Access

• Roman Kontchakov
• Carsten Lutz
• David Toman
• Frank Wolter
• Michael Zakharyaschev

The use of ontologies for accessing data is one of the most exciting new applications of description logic in databases and other information systems. A realistic way of realising sufficiently scalable ontology- based data access in practice is by reduction to querying relational databases. In this paper, we describe the 'combined approach, ' which incorporates the information given by the ontology into the data and employs query rewriting to eliminate spurious answers. We illustrate this approach for ontologies given in the DL-Lite family of description logics and briefly discuss the results obtained for the EL family.

KR Conference 2010 Conference Paper

The Combined Approach to Query Answering in DL-Lite

• Roman Kontchakov
• Carsten Lutz
• David Toman
• Frank Wolter
• Michael Zakharyaschev

Databases and related information systems can benefit from the use of ontologies to enrich the data with general background knowledge. The DL-Lite family of ontology languages was specifically tailored towards such ontology-based data access, enabling an implementation in a relational database management system (RDBMS) based on a query rewriting approach. In this paper, we propose an alternative approach to implementing ontology-based data access in DL-Lite. The distinguishing feature of our approach is to allow rewriting of both the query and the data. We show that, in contrast to the existing approaches, no exponential blowup is produced by the rewritings. Based on experiments with a number of real-world ontologies, we demonstrate that query execution in the proposed approach is often more efficient than in existing approaches, especially for large ontologies. We also show how to seamlessly integrate the data rewriting step of our approach into an RDBMS using views (which solves the update problem) and make an interesting observation regarding the succinctness of queries in the original query rewriting approach.

IJCAI Conference 2009 Conference Paper

• Carsten Lutz
• David Toman
• Frank Wolter

Conjunctive queries (CQ) are fundamental for accessing description logic (DL) knowledge bases. We study CQ answering in (extensions of) the DL EL, which is popular for large-scale ontologies and underlies the designated OWL2-EL profile of OWL2. Our main contribution is a novel approach to CQ answering that enables the use of standard relational database systems as the basis for query execution. We evaluate our approach using the IBM DB2 system, with encouraging results.

IJCAI Conference 2009 Conference Paper

• David Toman
• Grant Weddell

We review and extend earlier work on the logic CFD, a description logic that allows terminological cycles with universal restrictions over functional roles. In particular, we consider the problem of reasoning about concept subsumption and the problem of computing certain answers for a family of attribute-connected conjunctive queries, showing that both problems are in PTIME. We then consider the effect on the complexity of these problems after adding a concept constructor that expresses concept union, or after adding a concept constructor for the bottom class. Finally, we show that adding both constructors makes both problems EXPTIME-complete.

KR Conference 2008 Conference Paper

Identifying Objects Over Time with Description Logics

• David Toman
• Grant Weddell

A fundamental requirement for cooperating agents is to agree on a selection of component values of objects that can be used for reliably communicating references to the objects, that is, to function as their keys. In distributed environments such as the web, it is more likely that a choice of such values may have time limits on the duration of their ability to serve as keys, e. g., values denoting permissions, authorizations, service codes, mobile addresses and so on. In this paper, we consider how a Boolean complete description logic with a concept constructor for expressing "always" can also be embellished with a concept constructor for dynamic or temporal forms of equality generating constraints we call temporal path functional dependencies. In particular, we introduce the temporal description logic DLFDtemp, demonstrate how it can be used, among other things, to capture and reason about temporal keys and functional dependencies for a hypothetical distributed hospital database, and prove that the general membership problem for DLFDtemp is ExpTime-complete. The latter is accomplished by exhibiting a reduction of the general membership problem for DLFDtemp to the simpler dialect DLF. We also show that the addition of very simple kinds of eventualities leads to a significant increase in the complexity of the membership problem.

IJCAI Conference 2007 Conference Paper

• Alessandro Artale
• Carsten Lutz
• David Toman

We combine the modal logic S5 with the description logic (DL) ALCQI. The resulting multi-dimensional DL ALCQI_S5 supports reasoning about change by allowing to express that concepts and roles change over time. It cannot, however, discriminate between changes in the past and in the future. Our main technical result is that satisfiability of ALCQI_S5 concepts with respect to general TBoxes (including GCIs) is decidable and 2-ExpTime-complete. In contrast, reasoning in temporal DLs that are able to discriminate between past and future is inherently undecidable. We argue that our logic is sufficient for reasoning about temporal conceptual models with time-stamping constraints.

TCS Journal 2005 Journal Article

On reasoning about structural equality in XML: a description logic approach

• David Toman
• Grant Weddell

We define a boolean complete dialect of description logic called DLFD reg that can be used to reason about structural equality in semistructured ordered data in the presence of document type definitions. This application depends on the novel ability of DLFD reg to express functional dependencies over possibly infinite sets of feature paths defined by regular languages. We also present a decision procedure for the associated logical implication problem. The procedure underlies a mapping of such problems to satisfiability problems of Datalog nS ¬.

IJCAI Conference 2005 Conference Paper

On the Interaction between Inverse Features and Path-functional Dependencies in Description Logics

• David Toman
• Grant

We investigate how inverse features can be added to a boolean complete description logic with pathfunctional dependencies in ways that avoid undecidability of the associated logical implication problem. In particular, we present two conditions that ensure the problem remains EXPTIMEcomplete. The first is syntactic in nature and limits the form that dependencies may have in argument terminologies. The second is a coherence condition on terminologies that is sufficiently weak to allow the transfer of relational and emerging objectoriented normalization techniques.