Roman Kontchakov

KR Conference 2024 Conference Paper

Non-Rigid Designators in Modal and Temporal Free Description Logics

• Alessandro Artale
• Roman Kontchakov
• Andrea Mazzullo
• Frank Wolter

Definite descriptions, such as ‘the General Chair of KR 2024’, are a semantically transparent device for object identification in knowledge representation. In first-order modal logic, definite descriptions have been widely investigated for their non-rigidity, which allows them to designate different objects (or none at all) at different states. We propose expressive modal description logics with non-rigid definite descriptions and names, and investigate decidability and complexity of the satisfiability problem. We first systematically link satisfiability for the one-variable fragment of first-order modal logic with counting to our modal description logics. Then, we prove a promising NEXPTIME-completeness result for concept satisfiability for the fundamental epistemic multi-agent logic S5n and its neighbours, and show that some expressive logics that are undecidable with constant domain become decidable (but Ackermann-hard) with expanding domains. Finally, we conduct a fine-grained analysis of decidability of temporal logics.

JAIR Journal 2022 Journal Article

First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries

• Alessandro Artale
• Roman Kontchakov
• Alisa Kovtunova
• Vladislav Ryzhikov
• Frank Wolter
• Michael Zakharyaschev

Aiming at ontology-based data access to temporal data, we design two-dimensional temporal ontology and query languages by combining logics from the (extended) DL-Lite family with linear temporal logic LTL over discrete time (Z, 1, and FO(RPR) that admits relational primitive recursion. In terms of circuit complexity, FO( 0 and NC 1, respectively. We proceed in three steps. First, we define a hierarchy of 2D DL-Lite/LTL ontology languages and investigate the FO-rewritability of OMQs with atomic queries by constructing projections onto 1D LTL OMQs and employing recent results on the FO-rewritability of propositional LTL OMQs. As the projections involve deciding consistency of ontologies and data, we also consider the consistency problem for our languages. While the undecidability of consistency for 2D ontology languages with expressive Boolean role inclusions might be expected, we also show that, rather surprisingly, the restriction to Krom and Horn role inclusions leads to decidability (and ExpSpace-completeness), even if one admits full Booleans on concepts. As a final step, we lift some of the rewritability results for atomic OMQs to OMQs with expressive positive temporal instance queries. The lifting results are based on an in-depth study of the canonical models and only concern Horn ontologies.

IJCAI Conference 2022 Conference Paper

On the First-Order Rewritability of Ontology-Mediated Queries in Linear Temporal Logic (Extended Abstract)

• Alessandro Artale
• Roman Kontchakov
• Alisa Kovtunova
• Vladislav Ryzhikov
• Frank Wolter
• Michael Zakharyaschev

We argue that linear temporal logic LTL in tandem with monadic first-order logic can be used as a ba- sic language for ontology-based access to tempo- ral data and obtain a classification of the resulting ontology-mediated queries according to the type of standard first-order queries they can be rewritten to.

AIJ Journal 2021 Journal Article

First-order rewritability of ontology-mediated queries in linear temporal logic

• Alessandro Artale
• Roman Kontchakov
• Alisa Kovtunova
• Vladislav Ryzhikov
• Frank Wolter
• Michael Zakharyaschev

We investigate ontology-based data access to temporal data. We consider temporal ontologies given in linear temporal logic LTL interpreted over discrete time ( Z, < ). Queries are given in LTL or MFO ( < ), monadic first-order logic with a built-in linear order. Our concern is first-order rewritability of ontology-mediated queries (OMQs) consisting of a temporal ontology and a query. By taking account of the temporal operators used in the ontology and distinguishing between ontologies given in full LTL and its core, Krom and Horn fragments, we identify a hierarchy of OMQs with atomic queries by proving rewritability into either FO ( < ), first-order logic with the built-in linear order, or FO ( <, ≡ ), which extends FO ( < ) with the standard arithmetic predicates x ≡ 0 ( mod n ), for any fixed n > 1, or FO ( RPR ), which extends FO ( < ) with relational primitive recursion. In terms of circuit complexity, FO ( <, ≡ ) - and FO ( RPR ) -rewritability guarantee OMQ answering in uniform Image 1 and, respectively, Image 2. We obtain similar hierarchies for more expressive types of queries: positive LTL-formulas, monotone MFO ( < ) - and arbitrary MFO ( < ) -formulas. Our results are directly applicable if the temporal data to be accessed is one-dimensional; moreover, they lay foundations for investigating ontology-based access using combinations of temporal and description logics over two-dimensional temporal data.

KR Conference 2020 Conference Paper

Boolean Role Inclusions in DL-Lite With and Without Time

• Roman Kontchakov
• Vladislav Ryzhikov
• Frank Wolter
• Michael Zakharyaschev

Traditionally, description logic has focused on representing and reasoning about classes rather than relations (roles), which has been justified by the deterioration of the computational properties if expressive role inclusions are added. The situation is even worse in the temporalised setting, where monodicity is viewed as an almost necessary condition for decidability. We take a fresh look at the description logic DL-Lite with expressive role inclusions, both with and without a temporal dimension. While we confirm that full Boolean expressive power on roles leads to FO^2-like behaviour in the atemporal case and undecidability in the temporal case, we show that, rather surprisingly, the restriction to Krom and Horn role inclusions leads to much lower complexity in the atemporal case and to decidability (and ExpSpace-completeness) in the temporal case, even if one admits full Booleans on concepts. The latter result is one of very few instances breaking the monodicity barrier in temporal FO. This is also reflected on the data complexity level, where we obtain new rewritability results into FO with relational primitive recursion and FO with unary divisibility predicates.

TIME Conference 2019 Conference Paper

Two-Dimensional Rule Language for Querying Sensor Log Data: A Framework and Use Cases

• Sebastian Brandt 0001
• Diego Calvanese
• Elem Güzel Kalayci
• Roman Kontchakov
• Benjamin Mörzinger
• Vladislav Ryzhikov
• Guohui Xiao 0001
• Michael Zakharyaschev

Motivated by two industrial use cases that involve detecting events of interest in (asynchronous) time series from sensors in manufacturing rigs and gas turbines, we design an expressive rule language DslD equipped with interval aggregate functions (such as weighted average over a time interval), Allen’s interval relations and various metric constructs. We demonstrate how to model events in the uses cases in terms of DslD programs. We show that answering DslD queries in our use cases can be reduced to evaluating SQL queries. Our experiments with the use cases, carried out on the Apache Spark system, show that such SQL queries scale well on large real-world datasets.

IJCAI Conference 2018 Conference Paper

Ontology-Based Data Access: A Survey

• Guohui Xiao
• Diego Calvanese
• Roman Kontchakov
• Domenico Lembo
• Antonella Poggi
• Riccardo Rosati
• Michael Zakharyaschev

We present the framework of ontology-based data access, a semantic paradigm for providing a convenient and user-friendly access to data repositories, which has been actively developed and studied in the past decade. Focusing on relational data sources, we discuss the main ingredients of ontology-based data access, key theoretical results, techniques, applications and future challenges.

AAAI Conference 2017 Conference Paper

Ontology-Based Data Access with a Horn Fragment of Metric Temporal Logic

• Sebastian Brandt
• Elem GŸzel Kalaycõ
• Roman Kontchakov
• Vladislav Ryzhikov
• Guohui Xiao
• Michael Zakharyaschev

We advocate datalogMTL, a datalog extension of a Horn fragment of the metric temporal logic MTL, as a language for ontology-based access to temporal log data. We show that datalogMTL is EXPSPACE-complete even with punctual intervals, in which case MTL is known to be undecidable. Nonrecursive datalogMTL turns out to be PSPACE-complete for combined complexity and in AC0 for data complexity. We demonstrate by two real-world use cases that nonrecursive datalogMTL programs can express complex temporal concepts from typical user queries and thereby facilitate access to log data. Our experiments with Siemens turbine data and MesoWest weather data show that datalogMTL ontologymediated queries are efficient and scale on large datasets of up to 11GB.

TIME Conference 2017 Conference Paper

Ontology-Mediated Query Answering over Temporal Data: A Survey (Invited Talk)

• Alessandro Artale
• Roman Kontchakov
• Alisa Kovtunova
• Vladislav Ryzhikov
• Frank Wolter
• Michael Zakharyaschev

We discuss the use of various temporal knowledge representation formalisms for ontology-mediated query answering over temporal data. In particular, we analyse ontology and query languages based on the linear temporal logic LTL, the multi-dimensional Halpern-Shoham interval temporal logic HS_n, as well as the metric temporal logic MTL. Our main focus is on the data complexity of answering temporal ontology-mediated queries and their rewritability into standard first-order and datalog queries.

AIJ Journal 2016 Journal Article

Games for query inseparability of description logic knowledge bases

• Elena Botoeva
• Roman Kontchakov
• Vladislav Ryzhikov
• Frank Wolter
• Michael Zakharyaschev

We consider conjunctive query inseparability of description logic knowledge bases with respect to a given signature—a fundamental problem in knowledge base versioning, module extraction, forgetting and knowledge exchange. We give a uniform game-theoretic characterisation of knowledge base conjunctive query inseparability and develop worst-case optimal decision algorithms for fragments of Horn- ALCHI, including the description logics underpinning OWL 2 QL and OWL 2 EL. We also determine the data and combined complexity of deciding query inseparability. While query inseparability for all of these logics is P-complete for data complexity, the combined complexity ranges from P- to ExpTime- to 2ExpTime-completeness. We use these results to resolve two major open problems for OWL 2 QL by showing that TBox query inseparability and the membership problem for universal conjunctive query solutions in knowledge exchange are both ExpTime-complete for combined complexity. Finally, we introduce a more flexible notion of inseparability which compares answers to conjunctive queries in a given signature over a given set of individuals. In this case, checking query inseparability becomes NP-complete for data complexity, but the ExpTime- and 2ExpTime-completeness combined complexity results are preserved.

KR Conference 2016 Conference Paper

On Expressibility of Non-Monotone Operators in SPARQL

• Roman Kontchakov
• Egor V. Kostylev

SPARQL, a query language for RDF graphs, is one of the key technologies for the Semantic Web. The expressivity and complexity of various fragments of SPARQL have been studied extensively. It is usually assumed that the optional matching operator OPTIONAL has only two graph patterns as arguments. The specification of SPARQL, however, defines it as a ternary operator, with an additional filter condition. We address the problem of expressibility of the full ternary OPTIONAL via the simplified binary version and show that it is possible, but only with an exponential blowup in the size of the query (under common complexity-theoretic assumptions). We also study expressibility of other non-monotone SPARQL operators via optional matching and each other.

IJCAI Conference 2016 Conference Paper

Temporal and Spatial OBDA with Many-Dimensional Halpern-Shoham Logic

• Roman Kontchakov
• Laura Pandolfo
• Luca Pulina
• Vladislav Ryzhikov
• Michael Zakharyaschev

We design an extension datalogHS of datalog with hyperrectangle generalisations of Halpern-Shoham's modal operators on intervals and a corresponding query language. We prove that, over n-dimensional spaces comprised of Z and R, finding certain answers to datalogHS queries can be reduced to standard datalog query answering. We present experimental results showing the expressivity and efficiency of datalogHS on historical data.

IJCAI Conference 2015 Conference Paper

First-Order Rewritability of Temporal Ontology-Mediated Queries

• Alessandro Artale
• Roman Kontchakov
• Alisa Kovtunova
• Vladislav Ryzhikov
• Frank Wolter
• Michael Zakharyaschev

Aiming at ontology-based data access over temporal, in particular streaming data, we design a language of ontology-mediated queries by extending OWL 2 QL and SPARQL with temporal operators, and investigate rewritability of these queries into two-sorted first-order logic with < and PLUS over time.

AAAI Conference 2015 Conference Paper

Tractable Interval Temporal Propositional and Description Logics

• Alessandro Artale
• Roman Kontchakov
• Vladislav Ryzhikov
• Michael Zakharyaschev

We design a tractable Horn fragment of the Halpern-Shoham temporal logic and extend it to interval-based temporal description logics, instance checking in which is P-complete for both combined and data complexity.

IJCAI Conference 2015 Conference Paper

When Are Description Logic Knowledge Bases Indistinguishable?

• Elena Botoeva
• Roman Kontchakov
• Vladislav Ryzhikov
• Frank Wolter
• Michael Zakharyaschev

Deciding inseparability of description logic knowledge bases (KBs) with respect to conjunctive queries is fundamental for many KB engineering and maintenance tasks including versioning, module extraction, knowledge exchange and forgetting. We study the combined and data complexity of this inseparability problem for fragments of Horn-ALCHI, including the description logics underpinning OWL 2 QL and OWL 2 EL.

KR Conference 2014 Conference Paper

Query Inseparability for Description Logic Knowledge Bases

• Elena Botoeva
• Roman Kontchakov
• Vladislav Ryzhikov
• Frank Wolter
• Michael Zakharyaschev

a signature consisting of concept and role names. We call KBs K1 and K2 Σ-query inseparable and write K1 ≡Σ K2 if any CQ formulated in Σ has the same answers over K1 and K2. Note that even for Σ containing all concept and role names, Σ-query inseparability does not necessarily imply logical equivalence. The relativisation to (smaller) signatures is crucial to support the tasks mentioned above: We investigate conjunctive query inseparability of description logic (DL) knowledge bases (KBs) with respect to a given signature, a fundamental problem for KB versioning, module extraction, forgetting and knowledge exchange. We study the data and combined complexity of deciding KB query inseparability for fragments of Horn-ALCHI, including the DLs underpinning OWL 2 QL and OWL 2 EL. While all of these DLs are P-complete for data complexity, the combined complexity ranges from P to E XP T IME and 2E XP T IME. We also resolve two major open problems for OWL 2 QL by showing that TBox query inseparability and the membership problem for universal UCQ-solutions in knowledge exchange are both E XP T IME-complete for combined complexity. (versioning) When comparing two versions K1 and K2 of a KB with respect to their answers to CQs in a relevant signature Σ, the basic task is to check whether K1 ≡Σ K2. (modularisation) A Σ-module of a KB K is a KB K0 ⊆ K such that K0 ≡Σ K. If we are only interested in answering CQs in Σ over K, then we can achieve our aim by querying any Σ-module of K instead of K itself. (knowledge exchange) In knowledge exchange, we want to transform a KB K1 in a signature Σ1 to a new KB K2 in a disjoint signature Σ2 connected to Σ1 via a declarative mapping specification given by a TBox T12. Thus, the target KB K2 should satisfy the condition K1 ∪ T12 ≡Σ2 K2, in which case it is called a universal UCQ-solution (CQ and UCQ inseparabilities coincide for Horn DLs). (forgetting) A KB K0 results from forgetting a signature Σ in a KB K if K0 ≡sig(K)\Σ K and sig(K0) ⊆ sig(K) \ Σ. Thus, the result of forgetting Σ does not use Σ and gives the same answers to CQs without symbols in Σ as K.

AIJ Journal 2014 Journal Article

Spatial reasoning with RCC 8 and connectedness constraints in Euclidean spaces

• Roman Kontchakov
• Ian Pratt-Hartmann
• Michael Zakharyaschev

The language RCC 8 is a widely-studied formalism for describing topological arrangements of spatial regions. The variables of this language range over the collection of non-empty, regular closed sets of n-dimensional Euclidean space, here denoted RC + ( R n ), and its non-logical primitives allow us to specify how the interiors, exteriors and boundaries of these sets intersect. The key question is the satisfiability problem: given a finite set of atomic RCC 8 -constraints in m variables, determine whether there exists an m-tuple of elements of RC + ( R n ) satisfying them. These problems are known to coincide for all n ≥ 1, so that RCC 8 -satisfiability is independent of dimension. This common satisfiability problem is NLogSpace-complete. Unfortunately, RCC 8 lacks the means to say that a spatial region comprises a ‘single piece’, and the present article investigates what happens when this facility is added. We consider two extensions of RCC 8: RCC 8 c, in which we can state that a region is connected, and RCC 8 c ∘, in which we can instead state that a region has a connected interior. The satisfiability problems for both these languages are easily seen to depend on the dimension n, for n ≤ 3. Furthermore, in the case of RCC 8 c ∘, we show that there exist finite sets of constraints that are satisfiable over RC + ( R 2 ), but only by ‘wild’ regions having no possible physical meaning. This prompts us to consider interpretations over the more restrictive domain of non-empty, regular closed, polyhedral sets, RCP + ( R n ). We show that (a) the satisfiability problems for RCC 8 c (equivalently, RCC 8 c ∘ ) over RC + ( R ) and RCP + ( R ) are distinct and both NP-complete; (b) the satisfiability problems for RCC 8 c over RC + ( R 2 ) and RCP + ( R 2 ) are identical and NP-complete; (c) the satisfiability problems for RCC 8 c ∘ over RC + ( R 2 ) and RCP + ( R 2 ) are distinct, and the latter is NP-complete. Decidability of the satisfiability problem for RCC 8 c ∘ over RC + ( R 2 ) is open. For n ≥ 3, RCC 8 c and RCC 8 c ∘ are not interestingly different from RCC 8. We finish by answering the following question: given that a set of RCC 8 c - or RCC 8 c ∘ -constraints is satisfiable over RC + ( R n ) or RCP + ( R n ), how complex is the simplest satisfying assignment? In particular, we exhibit, for both languages, a sequence of constraints Φ n, satisfiable over RCP + ( R 2 ), such that the size of Φ n grows polynomially in n, while the smallest configuration of polygons satisfying Φ n cuts the plane into a number of pieces that grows exponentially. We further show that, over RC + ( R 2 ), RCC 8 c again requires exponentially large satisfying diagrams, while RCC 8 c ∘ can force regions in satisfying configurations to have infinitely many components.

AIJ Journal 2014 Journal Article

The price of query rewriting in ontology-based data access

• Georg Gottlob
• Stanislav Kikot
• Roman Kontchakov
• Vladimir Podolskii
• Thomas Schwentick
• Michael Zakharyaschev

We give a solution to the succinctness problem for the size of first-order rewritings of conjunctive queries in ontology-based data access with ontology languages such as OWL 2 QL, linear Datalog ± and sticky Datalog ±. We show that positive existential and nonrecursive datalog rewritings, which do not use extra non-logical symbols (except for intensional predicates in the case of datalog rewritings), suffer an exponential blowup in the worst case, while first-order rewritings can grow superpolynomially unless NP ⊆ P / poly. We also prove that nonrecursive datalog rewritings are in general exponentially more succinct than positive existential rewritings, while first-order rewritings can be superpolynomially more succinct than positive existential rewritings. On the other hand, we construct polynomial-size positive existential and nonrecursive datalog rewritings under the assumption that any data instance contains two fixed constants.

IJCAI Conference 2013 Conference Paper

Temporal Description Logic for Ontology-Based Data Access

• Alessandro Artale
• Roman Kontchakov
• Frank Wolter
• Michael Zakharyaschev

Our aim is to investigate ontology-based data access over temporal data with validity time and ontologies capable of temporal conceptual modelling. To this end, we design a temporal description logic, TQL, that extends the standard ontology language OWL 2 QL, provides basic means for temporal conceptual modelling and ensures firstorder rewritability of conjunctive queries for suitably defined data instances with validity time.

LPAR Conference 2013 Conference Paper

The Complexity of Clausal Fragments of LTL

• Alessandro Artale
• Roman Kontchakov
• Vladislav Ryzhikov
• Michael Zakharyaschev

Abstract We introduce and investigate a number of fragments of propositional temporal logic LTL over the flow of time (ℤ, <). The fragments are defined in terms of the available temporal operators and the structure of the clausal normal form of the temporal formulas. We determine the computational complexity of the satisfiability problem for each of the fragments, which ranges from NLogSpace to PTime, NP and PSpace.

KR Conference 2012 Conference Paper

Conjunctive Query Answering with OWL 2 QL

• Stanislav Kikot
• Roman Kontchakov
• Michael Zakharyaschev

tional constants and predicates. Optimised (but still exponential) pure rewritings to nonrecursive Datalog were suggested by Rosati and Almatelli (2010) and Gottlob, Orsi, and Pieris (2011). The combined approach of Kontchakov et al. (2010) was developed for OWL 2 QL without role inclusions; it uses a simple polynomial rewriting over the data expanded by applying the ontology axioms and introducing a small number of new individuals. The diversity of approaches to query rewriting prompts another question: what is the type/shape/size of rewritings we should aim at to make OBDA with OWL 2 QL efficient? When trying to answer this question, we should bear in mind that (i) the OBDA paradigm relies on the proven efficiency of RDBMSs, but (ii) database query answering is not tractable in the size of queries (PS PACE-complete for FO queries and NP-complete for CQs). High efficiency of RDBMSs in practice appears to indicate only that answering real-world queries over real-world databases turns out to be tractable. As rewritings can turn a standard query to something ‘out of this world, ’ a first rule of thumb could be as follows: the rewritten query should look similar to the original one. In this respect, as Gottlob and Schwentick (2011) remark, their polynomial rewriting is of rather ‘theoretical nature’ (it uses the extra constants, predicates and existentially quantified variables to encode, by making nondeterministic guesses, a relevant part of the chase, aka the canonical model; see the discussion in Conclusions for more details). The aim of this paper is to investigate what causes exponentially long pure rewritings of CQs over OWL 2 QL ontologies and to check experimentally whether those ‘bad guys’ occur in real-world queries and ontologies. As a result of this analysis, we suggest some short (polynomial-size) rewritings that cover most, if not all, practical cases. We think of a CQ as a labelled directed multigraph. For example, the query ‘find x1, x2, x3 for which We present a novel rewriting technique for conjunctive query answering over OWL 2 QL ontologies. In general, the obtained rewritings are not necessarily correct and can be of exponential size in the length of the query. We argue, however, that in most, if not all, practical cases the rewritings are correct and of polynomial size. Moreover, we prove some sufficient conditions, imposed on queries and ontologies, that guarantee correctness and succinctness. We also support our claim by experimental results.

ECAI Conference 2012 Conference Paper

DL-Lite with Attributes and Datatypes

• Alessandro Artale
• Vladislav Ryzhikov
• Roman Kontchakov

We extend the DL-Lite languages by means of attributes and datatypes. Attributes-a notion borrowed from data models- associate concrete values from datatypes to abstract objects and in this way complement roles, which describe relationships between abstract objects. The extended languages remain tractable (with a notable exception) even though they contain both existential and (a limited form of) universal quantification. We present complexity results for two most important reasoning problems in DL-Lite: combined complexity of knowledge base satisfiability and data complexity of positive existential query answering.

AAAI Conference 2011 Conference Paper

Conjunctive Query Inseparability of OWL 2 QL TBoxes

• Boris Konev
• Roman Kontchakov
• Michel Ludwig
• Thomas Schneider
• Frank Wolter
• Michael Zakharyaschev

The OWL 2 profile OWL 2 QL, based on the DL-Lite family of description logics, is emerging as a major language for developing new ontologies and approximating the existing ones. Its main application is ontology-based data access, where ontologies are used to provide background knowledge for answering queries over data. We investigate the corresponding notion of query inseparability (or equivalence) for OWL 2 QL ontologies and show that deciding query inseparability is PSPACE-hard and in EXPTIME. We give polynomial time (incomplete) algorithms and demonstrate by experiments that they can be used for practical module extraction.

IJCAI Conference 2011 Conference Paper

On the Decidability of Connectedness Constraints in 2D and 3D Euclidean Spaces

• Roman Kontchakov
• Yavor Nenov
• Ian Pratt-Hartmann
• Michael Zakharyaschev

We investigate (quantifier-free) spatial constraint languages with equality, contact and connectedness predicates as well as Boolean operations on regions, interpreted over low-dimensional Euclidean spaces. We show that the complexity of reasoning varies dramatically depending on the dimension of the space and on the type of regions considered. For example, the logic with the interior-connectedness predicate (and without contact) is undecidable over polygons or regular closed sets in the Euclidean plane, NP-complete over regular closed sets in three-dimensional Euclidean space, and ExpTime-complete over polyhedra in three-dimensional Euclidean space.

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

Interpreting Topological Logics over Euclidean Spaces

• Roman Kontchakov
• Ian Pratt-Hartmann
• Michael Zakharyaschev

Topological logics are a family of languages for representing and reasoning about topological data. In this paper, we consider propositional topological logics able to express the property of connectedness. The satisfiability problem for such logics is shown to depend not only on the spaces they are interpreted in, but also on the subsets of those spaces over which their variables are allowed to range. We identify the crucial notion of tameness, and chart the surprising patterns of sensitivity to the presence of non-tame regions exhibited by a range of topological logics in low-dimensional Euclidean spaces. We referred to r1, r2 and r3 above as ‘regions, ’ and depicted them as discs in the plane. But a moment’s thought shows that the set of valid formulas of any topological logic depends on the precise collection of regions we have in mind. For instance, there are RCC8-formulas that are valid as long as regions are taken to be discs in the plane, but invalid when regions are allowed to be disconnected (i. e. to consist of more than one ‘piece’). Thus, an important semantic issue for a topological logic like RCC8 is to identify the intended models. In this paper, we consider propositional topological logics with connectedness, i. e. topological logics in which the only logical connectives are the usual Boolean operators, but where there is a non-logical primitive expressing the property of topological connectedness (or a variant thereof). We show that such topological logics are typically sensitive both to the spaces they are interpreted over and—more particularly—to the subsets of those spaces over which their variables are allowed to range. We identify the crucial notion of tameness, and chart the surprising patterns of sensitivity to the presence of non-tame regions exhibited by a range of topological logics in low-dimensional Euclidean spaces.

AIJ Journal 2010 Journal Article

Logic-based ontology comparison and module extraction, with an application to DL-Lite

• Roman Kontchakov
• Frank Wolter
• Michael Zakharyaschev

We develop a formal framework for comparing different versions of ontologies, and apply it to ontologies formulated in terms of DL-Lite, a family of ‘lightweight’ description logics designed for data-intensive applications. The main feature of our approach is that we take into account the vocabulary ( = signature ) with respect to which one wants to compare ontologies. Five variants of difference and inseparability relations between ontologies are introduced and their respective applications for ontology development and maintenance discussed. These variants are obtained by generalising the notion of conservative extension from mathematical logic and by distinguishing between differences that can be observed among concept inclusions, answers to queries over ABoxes, by taking into account additional context ontologies, and by considering a model-theoretic, language-independent notion of difference. We compare these variants, study their meta-properties, determine the computational complexity of the corresponding reasoning tasks, and present decision algorithms. Moreover, we show that checking inseparability can be automated by means of encoding into QBF satisfiability and using off-the-shelf general purpose QBF solvers. Inseparability relations between ontologies are then used to develop a formal framework for (minimal) module extraction. We demonstrate that different types of minimal modules induced by these inseparability relations can be automatically extracted from real-world medium-size DL-Lite ontologies by composing the known tractable syntactic locality-based module extraction algorithm with our non-tractable extraction algorithms and using the multi-engine QBF solver aqme. Finally, we explore the relationship between uniform interpolation (or forgetting) and inseparability.

AAAI Conference 2010 Conference Paper

Past and Future of DL-Lite

• Alessandro Artale
• Roman Kontchakov
• Vladislav Ryzhikov
• Michael Zakharyaschev

We design minimal temporal description logics that are capable of expressing various aspects of temporal conceptual data models and investigate their computational complexity. We show that, depending on the required types of temporal and atemporal constraints, the satisfiability problem for temporal knowledge bases in the resulting logics can be NLOGSPACE-, NP- and PSPACE-complete, as well as undecidable.

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

• Roman Kontchakov
• Luca Pulina
• Ulrike Sattler
• Thomas Schneider
• Petra Selmer
• Frank Wolter
• Michael Zakharyaschev

We present a formal framework for (minimal) module extraction based on an abstract notion of inseparability w. r. t. a signature between ontologies. Two instances of this framework are discussed in detail for DL-Lite ontologies: concept inseparability, when ontologies imply the same complex concept inclusions over the signature, and query inseparability, when they give the same answers to existential queries for any instance data over the signature. We demonstrate that different types of corresponding minimal modules for these inseparability relations can be automatically extracted from large-scale DL-Lite ontologies by composing the tractable syntactic locality-based module extraction algorithm with intractable extraction algorithms using the multi-engine QBF solver AQME. The extracted minimal modules are compared with those obtained using non-logic-based approaches.

LPAR Conference 2008 Conference Paper

On the Computational Complexity of Spatial Logics with Connectedness Constraints

• Roman Kontchakov
• Ian Pratt-Hartmann
• Frank Wolter
• Michael Zakharyaschev

Abstract We investigate the computational complexity of spatial logics extended with the means to represent topological connectedness and restrict the number of connected components. In particular, we show that the connectedness constraints can increase complexity from NP to PSpace, ExpTime and, if component counting is allowed, to NExpTime.

AAAI Conference 2007 Conference Paper

DL-Lite in the Light of First-Order Logic

• Alessandro Artale
• Roman Kontchakov

The use of ontologies in various application domains, such as Data Integration, the Semantic Web, or ontology-based data management, where ontologies provide the access to large amounts of data, is posing challenging requirements w. r. t. a trade-off between expressive power of a DL and efficiency of reasoning. The logics of the DL-Lite family were specifically designed to meet such requirements and optimized w. r. t. the data complexity of answering complex types of queries. In this paper we propose DL-Litebool, an extension of DL- Lite with full Booleans and number restrictions, and study the complexity of reasoning in DL-Litebool and its significant sub-logics. We obtain our results, together with useful insights into the properties of the studied logics, by a novel reduction to the one-variable fragment of first-order logic. We study the computational complexity of satisfiability and subsumption, and the data complexity of answering positive existential queries (which extend unions of conjunctive queries). Notably, we extend the LOGSPACE upper bound for the data complexity of answering unions of conjunctive queries in DL-Lite to positive queries and to the possibility of expressing also number restrictions, and hence local functionality in the TBox.

TIME Conference 2007 Conference Paper

Temporalising Tractable Description Logics

• Alessandro Artale
• Roman Kontchakov
• Carsten Lutz
• Frank Wolter
• Michael Zakharyaschev

It is known that for temporal languages, such as first-order LTL, reasoning about constant (time-independent) relations is almost always undecidable. This applies to temporal description logics as well: constant binary relations together with general concept subsumptions in combinations of LTL and the basic description logic ALC cause undecidability. In this paper, we explore temporal extensions of two recently introduced families of 'weak' description logics known as DL-Lite and EL. Our results are twofold: temporalisations of even rather expressive variants of DL-Lite turn out to be decidable, while the temporalisation of EL with general concept subsumptions and constant relations is undecidable.

TIME Conference 2003 Conference Paper

On the Computational Complexity of Decidable Fragments of First-Order Linear Temporal Logics

• Ian M. Hodkinson
• Roman Kontchakov
• Agi Kurucz
• Frank Wolter
• Michael Zakharyaschev

We study the complexity of some fragments of first-order temporal logic over natural numbers time. The one-variable fragment of linear first-order temporal logic even with sole temporal operator /spl square/ is EXPSPACE-complete (this solves an open problem of J. Halpern and M. Vardi (1989)). So are the one-variable, two-variable and monadic monodic fragments with Until and Since. If we add the operators O/sup n/, with n given in binary, the fragment becomes 2EXPSPACE-complete. The packed monodic fragment has the same complexity as its pure first-order part - 2EXPTIME-complete. Over any class of flows of time containing one with an infinite ascending sequence - e. g. , rationals and real numbers time, and arbitrary strict linear orders - we obtain EXPSPACE lower bounds (which solves an open problem of M. Reynolds (1997)). Our results continue to hold if we restrict to models with finite first-order domains.