Author name cluster

Vladislav Ryzhikov

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

29 papers

2 author rows

IJCAI Conference 2024 Conference Paper

Extremal Separation Problems for Temporal Instance Queries

Jean Christoph Jung
Vladislav Ryzhikov
Frank Wolter
Michael Zakharyaschev

The separation problem for a class Q of database queries is to find a query in Q that distinguishes between a given set of ‘positive’ and ‘negative’ data examples. Separation provides explanations of examples and underpins the query-by-example paradigm to support database users in constructing and refining queries. As the space of all separating queries can be large, it is helpful to succinctly represent this space by means of its most specific (logically strongest) and general (weakest) members. We investigate this extremal separation problem for classes of instance queries formulated in linear temporal logic LTL with the operators conjunction, ‘next’, and ‘eventually’. Our results range from tight complexity bounds for verifying and counting extremal separators to algorithms computing them.

PDF Details DOI

KR Conference 2024 Conference Paper

Unique Characterisability and Learnability of Temporal Queries Mediated by an Ontology

Jean Christoph Jung
Vladislav Ryzhikov
Frank Wolter
Michael Zakharyaschev

Algorithms for learning database queries from examples and unique characterisations of queries by examples are prominent starting points for developing automated support for query explanation and construction. We investigate how far recent results and techniques on learning and unique characterisations of atemporal queries mediated by an ontology can be extended to temporal data and queries. Based on a systematic review of the relevant approaches in the atemporal case, we obtain general transfer results identifying conditions under which temporal queries composed of atemporal ones are (polynomially) learnable and uniquely characterisable.

PDF Details DOI

JAIR Journal 2023 Journal Article

Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic

Agi Kurucz
Vladislav Ryzhikov
Yury Savateev
Michael Zakharyaschev

Our concern is the problem of determining the data complexity of answering an ontology-mediated query (OMQ) formulated in linear temporal logic LTL over (Z,<) and deciding whether it is rewritable to an FO(<)-query, possibly with some extra predicates. First, we observe that, in line with the circuit complexity and FO-definability of regular languages, OMQ answering in AC0, ACC0 and NC1 coincides with FO(<,≡)-rewritability using unary predicates x ≡ 0 (mod n), FO(<,MOD)-rewritability, and FO(RPR)-rewritability using relational primitive recursion, respectively. We prove that, similarly to known PSᴘᴀᴄᴇ-completeness of recognising FO(<)-definability of regular languages, deciding FO(<,≡)- and FO(<,MOD)-definability is also PSᴘᴀᴄᴇ-complete (unless ACC0 = NC1). We then use this result to show that deciding FO(<)-, FO(<,≡)- and FO(<,MOD)-rewritability of LTL OMQs is ExᴘSᴘᴀᴄᴇ-complete, and that these problems become PSᴘᴀᴄᴇ-complete for OMQs with a linear Horn ontology and an atomic query, and also a positive query in the cases of FO(<)- and FO(<,≡)-rewritability. Further, we consider FO(<)-rewritability of OMQs with a binary-clause ontology and identify OMQ classes, for which deciding it is PSᴘᴀᴄᴇ-, Π2p- and coNP-complete.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Reverse Engineering of Temporal Queries Mediated by LTL Ontologies

Marie Fortin
Boris Konev
Vladislav Ryzhikov
Yury Savateev
Frank Wolter
Michael Zakharyaschev

In reverse engineering of database queries, we aim to construct a query from a given set of answers and non-answers; it can then be used to explore the data further or as an explanation of the answers and non-answers. We investigate this query-by-example problem for queries formulated in positive fragments of linear temporal logic LTL over timestamped data, focusing on the design of suitable query languages and the combined and data complexity of deciding whether there exists a query in the given language that separates the given answers from non-answers. We consider both plain LTL queries and those mediated by LTL ontologies.

PDF Details DOI

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.

PDF Details DOI

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.

PDF Details DOI

KR Conference 2022 Conference Paper

Unique Characterisability and Learnability of Temporal Instance Queries

Marie Fortin
Boris Konev
Vladislav Ryzhikov
Yury Savateev
Frank Wolter
Michael Zakharyaschev

We aim to determine which temporal instance queries can be uniquely characterised by a (polynomial-size) set of positive and negative temporal data examples. We start by considering queries formulated in fragments of propositional linear temporal logic LTL that correspond to conjunctive queries (CQs) or extensions thereof induced by the until operator. Not all of these queries admit polynomial characterisations, but by imposing a further restriction to path-shaped queries we identify natural classes that do. We then investigate how far the obtained characterisations can be lifted to temporal knowledge graphs queried by 2D languages combining LTL with concepts in description logics EL or ELI (i. e. , tree-shaped CQs). While temporal operators in the scope of description logic constructors can destroy polynomial characterisability, we obtain general transfer results for the case when description logic constructors are within the scope of temporal operators. Finally, we apply our characterisations to establish (polynomial) learnability of temporal instance queries using membership queries in the active learning framework.

PDF Details DOI

TIME Conference 2021 Conference Paper

Deciding FO-Rewritability of Ontology-Mediated Queries in Linear Temporal Logic

Vladislav Ryzhikov
Yury Savateev
Michael Zakharyaschev

Our concern is the problem of determining the data complexity of answering an ontology-mediated query (OMQ) given in linear temporal logic LTL over (ℤ, <) and deciding whether it is rewritable to an FO(<)-query, possibly with extra predicates. First, we observe that, in line with the circuit complexity and FO-definability of regular languages, OMQ answering in AC⁰, ACC⁰ and NC¹ coincides with FO(<, ≡)-rewritability using unary predicates x ≡ 0 (mod n), FO(<, MOD)-rewritability, and FO(RPR)-rewritability using relational primitive recursion, respectively. We then show that deciding FO(<)-, FO(<, ≡)- and FO(<, MOD)-rewritability of LTL OMQs is ExpSpace-complete, and that these problems become PSpace-complete for OMQs with a linear Horn ontology and an atomic query, and also a positive query in the cases of FO(<)- and FO(<, ≡)-rewritability. Further, we consider FO(<)-rewritability of OMQs with a binary-clause ontology and identify OMQ classes, for which deciding it is PSpace-, Π₂^p- and coNP-complete.

Details

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.

Details DOI

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.

PDF Details DOI

IJCAI Conference 2019 Conference Paper

Data Complexity and Rewritability of Ontology-Mediated Queries in Metric Temporal Logic under the Event-Based Semantics

Vladislav Ryzhikov
Przemyslaw Andrzej Walega
Michael Zakharyaschev

We investigate the data complexity of answering queries mediated by metric temporal logic ontologies under the event-based semantics assuming that data instances are finite timed words timestamped with binary fractions. We identify classes of ontology-mediated queries answering which can be done in AC0, NC1, L, NL, P, and coNP for data complexity, provide their rewritings to first-order logic and its extensions with primitive recursion, transitive closure or datalog, and establish lower complexity bounds.

PDF Details

AIJ Journal 2019 Journal Article

Query inseparability for ALC ontologies

Elena Botoeva
Carsten Lutz
Vladislav Ryzhikov
Frank Wolter
Michael Zakharyaschev

We investigate the problem whether two ALC ontologies are indistinguishable (or inseparable) by means of queries in a given signature, which is fundamental for ontology engineering tasks such as ontology versioning, modularisation, update, and forgetting. We consider both knowledge base (KB) and TBox inseparability. For KBs, we give model-theoretic criteria in terms of (finite partial) homomorphisms and products and prove that this problem is undecidable for conjunctive queries (CQs), but 2ExpTime-complete for unions of CQs (UCQs). The same results hold if (U)CQs are replaced by rooted (U)CQs, where every variable is connected to an answer variable. We also show that inseparability by CQs is still undecidable if one KB is given in the lightweight DL EL and if no restrictions are imposed on the signature of the CQs. We also consider the problem whether two ALC TBoxes give the same answers to any query over any ABox in a given signature and show that, for CQs, this problem is undecidable, too. We then develop model-theoretic criteria for Horn ALC TBoxes and show using tree automata that, in contrast, inseparability becomes decidable and 2ExpTime-complete, even ExpTime-complete when restricted to (unions of) rooted CQs.

Details DOI

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.

Details

JAIR Journal 2018 Journal Article

Querying Log Data with Metric Temporal Logic

Sebastian Brandt
Elem Güzel Kalaycı
Vladislav Ryzhikov
Guohui Xiao
Michael Zakharyaschev

We propose a novel framework for ontology-based access to temporal log data using a datalog extension datalogMTL of the Horn fragment of the metric temporal logic MTL. We show that datalogMTL is EXPSPACE-complete even with punctual intervals, in which case full MTL is known to be undecidable. We also prove that nonrecursive datalogMTL is 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 temporal log data. Our experiments with Siemens turbine data and MesoWest weather data show that datalogMTL ontology-mediated queries are efficient and scale on large datasets.

PDF Details DOI

AAAI Conference 2017 Conference Paper

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

Sebastian Brandt
Elem Gzel 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 efﬁcient and scale on large datasets of up to 11GB.

PDF Details

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.

Details

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.

Details DOI

AIJ Journal 2016 Journal Article

Knowledge base exchange: The case of OWL 2 QL

Marcelo Arenas
Elena Botoeva
Diego Calvanese
Vladislav Ryzhikov

In this article, we define and study the problem of exchanging knowledge between a source and a target knowledge base (KB), connected through mappings. Differently from the traditional database exchange setting, which considers only the exchange of data, we are interested in exchanging implicit knowledge. As representation formalism we use Description Logics (DLs), thus assuming that the source and target KBs are given as a DL TBox+ABox, while the mappings have the form of DL TBox assertions. We define a general framework of KB exchange, and study the problem of translating the knowledge in the source KB according to the mappings expressed in OWL 2 QL, the profile of the standard Web Ontology Language OWL 2 based on the description logic DL-Lite R. We develop novel game- and automata-theoretic techniques, and we provide complexity results that range from NLogSpace to ExpTime.

Details DOI

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.

PDF Details

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.

PDF Details

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.

PDF Details

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.

PDF Details

ECAI Conference 2014 Conference Paper

DL-Lite and Interval Temporal Logics: a Marriage Proposal

Alessandro Artale
Davide Bresolin
Angelo Montanari
Guido Sciavicco
Vladislav Ryzhikov

Description logics of the DL-Lite family are widely used in knowledge representation because of their low computational complexity and rather good expressivity sufficient to capture important conceptual modelling constructs and the OWL2 QL profile of the Ontology Web Language (OWL). Recently, various point-based temporal extensions of DL-Lite have been investigated. Here, we propose to extend DL-Lite with fragments of Halpern and Shoham's interval logic of Allen's relations (&Hscr; &Sscr;). We formally define such extensions and show how they can be successfully used in knowledge representation. In the quest for a decidable logic, we discuss the challanges in combining decidable fragments of &Hscr; &Sscr; with DL-Lite.

Details

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.

IJCAI Conference 2013 Conference Paper

Exchanging OWL 2 QL Knowledge Bases

Marcelo Arenas
Elena Botoeva
Diego Calvanese
Vladislav Ryzhikov

Knowledge base exchange is an important problem in the area of data exchange and knowledge representation, where one is interested in exchanging information between a source and a target knowledge base connected through a mapping. In this paper, we study this fundamental problem for knowledge bases and mappings expressed in OWL 2 QL, the profile of OWL 2 based on the description logic DL-LiteR. More specifically, we consider the problem of computing universal solutions, identified as one of the most desirable translations to be materialized, and the problem of computing UCQrepresentations, which optimally capture in a target TBox the information that can be extracted from a source TBox and a mapping by means of unions of conjunctive queries. For the former we provide a novel automata-theoretic technique, and complexity results that range from NP to EXPTIME, while for the latter we show NLOGSPACE-completeness.

PDF Details DOI

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.

Details

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.

Details

KR Conference 2012 Short Paper

Exchanging Description Logic Knowledge Bases

Marcelo Arenas
Elena Botoeva
Diego Calvanese
Vladislav Ryzhikov
Evgeny Sherkhonov

mappings are sets of DL inclusions. In such a setting, in order to minimize the exchange (and hence transfer and materialization) of explicit (i. e., ABox) information, we are interested in computing translations, from now on referred to as solutions, that contain as much implicit knowledge as possible. This leads us to define the novel notion of representability, which helps us in understanding the capacity of solutions to transfer implicit knowledge. Checking representability and computing a representation of a source TBox under a mapping turn out to be crucial problems in the context of knowledge base exchange. Furthermore, we argue that the right notion of solution, on which to base our investigations, should not be the standard one based on the correspondence between models of source and target KBs. Indeed, we show that such solutions present severe limitations since, on the one hand, they do not allow for the use of implicit target information to represent implicit source information, and on the other hand, they may lead to exponentially large target ABoxes. To overcome these drawbacks, we introduce the weaker notion of Q-solution, for a query language Q, which is based on the correspondence between answers to queries in Q over source and target KBs. Notice that such a notion, though weaker, is in line with the objective of (data and) knowledge base exchange of providing in the target sufficient information to answer queries in Q that could also be posed over the source. We then develop results and techniques for KB exchange and for the Q-representability problem in the case where Q are unions of conjunctive queries (UCQs), and where KBs are expressed in DL-LiteRDFS, a member of the DL-Lite family (Calvanese et al. 2007) that corresponds to the FOL fragment of RDFS (Brickley and Guha 2004), the widely adopted standard Semantic Web language. In this paper, we study the problem of exchanging knowledge between a source and a target knowledge base (KB), connected through mappings. Differently from the traditional database exchange setting, which considers only the exchange of data, we are interested in exchanging implicit knowledge. As representation formalism we use Description Logics (DLs), thus assuming that the source and target KBs are given as a DL TBox+ABox, while the mappings have the form of DL TBox assertions. We study the problem of translating the knowledge in the source KB according to these mappings. We define a general framework of KB exchange, and address the problems of representing implicit source information in the target, and of computing different kinds of solutions, i. e., target KBs with specified properties, given a source KB and a mapping. We develop first results and study the complexity of KB exchange for DL-LiteRDFS, a DL corresponding to the FOL fragment of RDFS, and for DL-LiteR.

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.

PDF Details