DL 2014 PROCEEDINGS: PAPERS WITH ABSTRACTS

ABSTRACT. We consider the setting of graph-structured data that evolve as a result of operations carried out by users or applications. We rely on a simple yet powerful action language in which actions are finite sequences of insertions and deletions of nodes and labels, and on the use of Description Logics for describing integrity constraints and (partial) states of the data. For this setting, we study variants of planning problems, which range from ensuring the satisfaction of a given set of integrity constraints after executing a given sequence of actions, to deciding the existence of a sequence of actions that takes the data to an (un)desirable state, starting either from a specific data instance or from an incomplete description of it. For these problems we establish (un)decidability results and study the computational complexity, also considering various restrictions.

ABSTRACT. Updates in RDF stores have recently been standardised in the SPARQL 1.1 Update specification. However, computing answers entailed by ontologies in triple stores is usually treated orthogonal to updates. Even W3C's SPARQL 1.1 Update language and SPARQL 1.1 Entailment Regimes specifications explicitly exclude a standard behaviour how entailment regimes other than simple entailment in the context of updates. In this paper, we take a first step to close this gap. We define a fragment of SPARQL basic graph patterns corresponding to (the RDFS fragment of) DL-Lite and the corresponding SPARQL update language, dealing with updates both of ABox and of TBox statements. We discuss possible semantics along with potential strategies for implementing them. Particularly, we treat materialised RDF stores, which store all entailed triples explicitly and how materialisation can be preserved upon ABox and TBox updates.

ABSTRACT. We investigate various types of query rewriting over ontologies given in the standard temporal logic LTL as well as combinations of LTL with DL-Lite logics. In particular, we consider FO(<)-rewritings that can use the temporal precedence relation, FO(<,+)-rewritings that can also employ the arithmetic predicate PLUS, and rewritings to finite automata with data given on the automaton tape.

ABSTRACT. Matching concept descriptions against concept patterns was introduced as a new inference task in Description Logics almost 20 years ago, motivated by applications in the Classic system. For the Description Logic EL, it was shown in 2000 that the matching problem is NP-complete. It then took almost 10 years before this NP-completeness result could be extended from matching to unification in EL. The next big challenge was then to further extend these results from matching and unification without a TBox to matching and unification w.r.t. a general TBox, i.e., a finite set of general concept inclusions. For unification, we could show some partial results for general TBox that satisfy a certain restriction on cyclic dependencies between concepts, but the general case ist still open. For matching, we solve the general case in this paper: we show that matching in EL w.r.t. general TBoxes is NP-complete by introducing a goal-oriented matching algorithm that uses nondeterministic rules to transform a given matching problem into a solved form by a polynomial number of rule applications. We also investigate some tractable variants of the matching problem.

ABSTRACT. This paper further investigates the succinctness landscape of query rewriting in OWL 2 QL. We clarify the size of positive existential (PE), non-recursive datalog (NDL), and first order (FO) rewritings for various classes of tree-like conjunctive queries, ranging from linear queries up to bounded treewidth queries. More specifically, we establish a superpolynomial lower bound on the size of PE rewritings that holds already for linear queries and TBoxes of depth 2. For NDL-rewritings, we show that polynomial-size rewritings always exist for tree-shaped queries with a bounded number of leaves (and arbitrary TBoxes), and for bounded treewidth queries and bounded depth TBoxes. Finally, we show that the succinctness problems concerning FO-rewritings are equivalent to well-known problems in Boolean circuit complexity. Along with known results, this yields a complete picture of the succinctness landscape for the considered classes of queries and TBoxes. 

ABSTRACT. The complexity of reasoning in fuzzy description logics over finite lattices usually does not exceed that of the underlying classical DLs. This has recently been shown for the logics between L-IALC and L-ISCHI using a combination of automata- and tableau-based techniques. In this paper, this approach is modified to deal with nominals and constants in L-ISCHOI. Reasoning w.r.t. general TBoxes is ExpTime-complete, and PSpace-completeness is shown under the restriction to acyclic terminologies in two sublogics. The latter implies two previously unknown complexity results for the classical DLs ALCHO and SO.

ABSTRACT. We study the fuzzy extension of \FLz with semantics based on the G\"odel t-norm. We show that gfp-subsumption w.r.t.\ a finite set of primitive definitions can be characterized by a relation on weighted automata, and use this result to provide tight complexity bounds for reasoning in this logic.

ABSTRACT. We investigate conjunctive query inseparability of description logic knowledge bases (KBs) with respect to a given signature, a fundamental problem for KB versioning, module extraction, forgetting and knowledge exchange. We develop a game-theoretic technique for checking query entailment of KBs expressed in fragments of Horn-ALCHI, and show a number of complexity results ranging from P to EXPTIME and 2EXPTIME.

ABSTRACT. Recently several inconsistency-tolerant semantics have been introduced for querying inconsistent description logic knowledge bases. Most of these semantics rely on the notion of a repair, defined as an inclusion-maximal subset of the facts (ABox) which is consistent with the ontology (TBox). In this paper, we study variants of two popular inconsistency-tolerant semantics obtained by replacing classical repairs by various types of preferred repair. We analyze the complexity of query answering under the resulting semantics, focusing on the lightweight logic DL-Lite_R. Unsurprisingly, query answering is intractable in all cases, but we nonetheless identify one notion of preferred repair, based upon priority levels, whose data complexity is "only" coNP-complete. This leads us to propose an approach combining incomplete tractable methods with calls to a SAT solver. An experimental evaluation of the approach shows good scalability on realistic cases.

ABSTRACT. The complete picture of the complexity of conjunctive query answering under guarded disjunctive existential rules has been recently settled. However, in the case of acyclic (unions of) conjunctive queries there are some fundamental questions which are still open. It is the precise aim of the present paper to close those questions. Our main result states that acyclic conjunctive query answering under a fixed set of guarded disjunctive existential rules is EXPTIME-hard. This result together with an EXPTIME upper bound obtained by exploiting classical results on guarded first-order logic, gives us the complete picture of the complexity of our problem. As an immediate consequence, we get that answering acyclic unions of conjunctive queries under DL-Lite_{bool}^{H}, one of the most expressive languages of the DL-Lite family of DLs, is EXPTIME-complete, even in the case of a fixed TBox. In fact, the EXPTIME-hardnees holds even for DL-Lite_{bool}, that is, the DL obtained from DL-Lite_{bool}^{H} after forbidding role hierarchies.

ABSTRACT. Representation of context dependent knowledge in the Semantic Web has been recognized as a relevant issue: as a consequence, a number of logic based formalisms have been proposed in this regard. In response to this need, in previous works, we presented the description logic-based Contextualized Knowledge Repository (CKR) framework. Starting from this point, the first contribution of the paper is an extension of CKR with the possibility to represent defaults in context dependent axioms and a translation of extended CKRs to datalog programs with negation under answer set semantics. The translation generates datalog programs which are sound and complete w.r.t. instance checking in CKRs. Exploiting this result, we have developed as a second contribution a prototype implementation that compiles a CKR based on OWL2RL to a datalog program. Finally, we compare our approach with major non-monotonic formalisms for description logics and contextual knowledge representation.

ABSTRACT. The verification community has studied dynamic data structures primarily in a bottom-up way by analyzing pointers and the shapes induced by them. Recent work in fields such as separation logic has made significant progress in extracting shapes from program source code. Many real world programs however manipulate complex data whose structure and content is most naturally described by formalisms from object oriented programming and databases. In this paper, we attempt to bridge the conceptual gap between these two communities. Our approach is based on description logic, a widely used knowledge representation paradigm which gives a logical underpinning for diverse modeling frameworks such as UML and ER. We show how description logic can be used on top of an existing shape analysis to add content descriptions to the shapes. Technically, we assume that we have separation logic shape invariants obtained from a shape analysis tool, and requirements on the program data in terms of description logic. We show that the two-variable fragment of first order logic with counting and trees (whose decidability was proved at LICS 2013) can be used as a joint framework to embed suitable fragments of description logic and separation logic.

ABSTRACT. We investigate cases where an ontology expressed in a seemingly hard DL can be polynomially reduced to one in a simpler logic, while preserving classification and fact entailment reasoning outcomes. Our transformations target the elimination of inverse roles, universal and existential restrictions, and in the best case allow us to rewrite the given ontology into one of the OWL 2 profiles. Even if an ontology cannot be fully rewritten into a profile, in many cases our transformations allow us to exploit further optimisation techniques. Moreover, the elimination of some out-of-profile axioms can improve the performance of modular reasoners, such as MORe. We have tested our techniques on both classification and data reasoning tasks with encouraging results.

ABSTRACT. We study confidentiality enforcement in ontologies under the Controlled Query Evaluation (CQE) framework. In a CQE system, a policy specifies the sensitive information, and a censor ensures that answers to user queries that could violate the policy are not returned. Our goal is the design of optimal CQE algorithms, which ensure confidentiality while maximising access to information. We study two natural classes of censors that can be realised using existing infrastructure for query answering and propose optimal CQE algorithms for the standardised profiles of the ontology language OWL 2.

ABSTRACT. An increasing number of applications are relying on RDF format for storing data, on OWL ontologies to enhance the data with semantics, and SPARQL for accessing the data. SPARQL, however, is not targeted towards end-users, and suitable query interfaces are needed. Faceted search is a prominent approach for end-user data access, and in this paper we discuss how this approach can be applied to RDF and OWL. We implemented our ideas in a proof of concept prototype, SemFacet, and a preliminary evaluation of the system is encouraging.

ABSTRACT. A major challenge in knowledge representation is to manage the access to knowledge: users should not be presented with knowledge that is irrelevant to their topic of interest, or have no right to access.

Two general strategies exist for providing access restrictions: (1) the ontology engineers describe the conditions that allow access to specific fragments of the ontology, or (2) fragments are automatically identified through their logical properties. The former is prone to miss logical connections between axioms, while the latter can fail to capture relevant knowledge that has no logical connection with the topic of interest.

We define the Context-Oriented Decomposition (COD) of an ontology as a technique that combines the benefits of both approaches: it allows authors to identify relevant fragments, while guaranteeing the strong semantic properties of the logic-based Atomic Decomposition.

ABSTRACT. Nonmonotonic Description Logic (DL-) programs couple nonmonotonic logic programs with DL-ontologies through queries in a loose way which may lead to inconsistency, i.e., lack of an answer set. Recently defined repair answer sets remedy this but a straightforward computation method lacks practicality. We present a novel evaluation algorithm for deletion repair answer sets based on support sets, which reduces evaluation of DL-Lite_A ontology queries to constraint matching. This leads to significant performance gains towards inconsistency management in practice.

ABSTRACT. It is known that no algorithm can extract the minimal depleting Σ-module from ontologies in expressive description logics (DLs). Thus research has focused on algorithms that approximate minimal depleting modules ‘from above’ by computing a depleting module that is not necessarily minimal. The first contribution of this paper is an implementation (AMEX) of such a depleting module extraction algorithm for expressive acyclic DL ontologies that uses a QBF solver for checking conservative extensions relativised to singleton interpretations. To evaluate AMEX and other module extraction algorithms we propose an algorithm approximating minimal depleting modules ‘from below’ (which also uses a QBF solver). We present experiments based on NCI (the National Cancer Institute Thesaurus) that indicate that our lower approximation often coincides with (or is very close to) the upper approximation computed by AMEX, thus proving for the first time that an approximation algorithm for minimal depleting modules can be almost optimal on a large ontology.

ABSTRACT. We present a new procedure for ontology materialization (computing all entailed instances of every atomic concept) in which reasoning over a large ABox is reduced to reasoning over a smaller "abstract" ABox. The abstract ABox is obtained as the result of a fixed-point computation involving two stages: 1) abstraction: partition the individuals into equivalence classes based on told information and use one representative individual per equivalence class, and 2) refinement: iteratively split (refine) the equivalence classes, when new assertions are derived that distinguish individuals within the same class. We prove that the method is complete for Horn ALCHOI ontologies, that is, all entailed instances will be derived once the fixed-point is reached. We implement the procedure in a new database-backed reasoning system and evaluate it empirically on existing ontologies with large ABoxes. We demonstrate that the obtained abstract ABoxes are significantly smaller than the original ones and can be computed with few refinement steps.

ABSTRACT. We propose a new type of algorithm for computing first-order (FO) rewritings of concept queries under EL-TBoxes that is tailored towards efficient implementation. The algorithm outputs a non-recursive datalog rewriting if the input is FO-rewritable and otherwise reports non-FO-rewritability. We carry out experiments with ontologies from practical applications which show that our algorithm performs very well in practice, and that EL-TBoxes originating from real-world applications admit FO-rewritings (of reasonable size) in almost all cases, even when in theory such rewritings are not guaranteed to exist.

ABSTRACT. We study the closely related problems of rewriting disjunctive datalog programs and non-Horn DL ontologies into plain datalog programs that entail the same facts for every dataset. We first propose the class of markable disjunctive datalog programs, which is efficiently recognisable and admits polynomial rewritings into datalog. Markability naturally extends to SHI ontologies, and markable ontologies admit (possibly exponential) datalog rewritings. We then turn our attention to resolution-based rewriting techniques. We devise an enhanced rewriting procedure for disjunctive datalog, and propose a second class of SHI ontologies that admits exponential datalog rewritings via resolution. Finally, we evaluate the feasibility of our techniques over a large corpus of ontologies, with encouraging results.

ABSTRACT. EL is a family of tractable Description Logics (DLs) that is the basis of the OWL~2 EL profile. Unlike for many expressive DLs, reasoning in EL can be performed by computing a deductively-closed set of logical consequences of some specific form. In some ontology-based applications, e.g., for ontology debugging, knowing the logical consequences of the ontology axioms is often not sufficient. The user also needs to know from which axioms and how the consequences were derived. Although it is possible to keep track of all inferences applied during reasoning, this is usually not done in practice to avoid the overheads. In this paper, we present a goal-directed method that can generate inferences for selected consequences in the deductive closure without re-applying all rules from scratch. We provide an empirical evaluation demonstrating that the method is fast and economical for large EL ontologies. Although the main benefits are demonstrated for EL reasoning, the method can be easily extended to other procedures based on deductive closure computation using fixed sets of rules.

ABSTRACT. Temporal query abduction is the problem of hypothesizing a minimal set of temporal data which, given some fixed background knowledge, warrants the entailment of the query. This problem formally underlies a variety of forms of explanatory and diagnostic reasoning in the context of time series data, data streams, or otherwise temporally annotated structured information. In this paper, we consider (temporally ordered) data represented in Description Logics from the popular DL-Lite family and Temporal Query Language, based on the combination of LTL with conjunctive queries. In this defined setting, we study the complexity of temporal query abduction, assuming different restrictions on the problem and minimality criteria for abductive solutions. As a result, we draw several revealing demarcation lines between NP-, DP- and PSpace-complete variants of the problem.

ABSTRACT. We present a method to compute uniform interpolants of ALC ontologies with ABoxes. Uniform interpolants are restricted views of ontologies that only use a specified set of symbols, but share all entailments in that signature with the original ontology. This way, it allows to select or remove information from an ontology based on a signature, which has applications in privacy, ontology analysis and ontology reuse. In turns out, that in general, uniform interpolants of ALC ontologies with ABoxes may require the use of disjunctions in the ABox or nominals. Our evaluation of the method suggests however, that in most practical cases uniform interpolants can be represented as a classical ALC ontology.

ABSTRACT. Applications of description logics (DLs) such as OWL 2 and ontology-based data access (OBDA) require understanding of how to pose database queries over DL knowledge bases. While there have been many studies regarding traditional relational query formalisms such as conjunctive queries and their extensions, little attention has been paid to graph database queries, despite the fact that graph databases share the structure of interpretations with DLs; that is they describe essentially the same objects. In particular, not much is known about the interplay between DLs and XPath. The last is a powerful formalism for querying semistructured data: it is in the core of most practical query languages for XML trees, and it is also gaining popularity in theory and practice of graph databases.

In this paper we make a step towards coupling knowledge bases and graph databases by studying how to answer powerful XPath-style queries over DL-Lite. We start with adapting the definition of XPath to the DL context, and then proceed to study the complexity of evaluating XPath queries over knowledge bases. Results show that, while query answering is undecidable for the full XPath, by carefully tuning the amount of negation allowed in the queries we can arrive to XPath fragments that have a potential to be used in practical applications.

ABSTRACT. Nominal schemas extend description logics (DLs) with a restricted form of variables, thus integrating rule-like expressive power into standard DLs. They are also one of the most recently introduced DL features, and in spite of many works on algorithms and implementations, almost nothing was known about their computational complexity and expressivity until recently. In this extended abstract, we review our recent work "Nominal Schemas in Description Logics: Complexities Clarified" that will be presented at KR 2014. We give a comprehensive overview of the reasoning complexities of a wide range of DLs—from EL to SROIQ—extended with nominal schemas. Both combined and data complexities increase by one exponential in most cases, with the one previously known case of SROIQ being the main exception. To further improve our understanding of nominal schemas, we also investigate their semantics, traditionally based on finite grounding, and show that it can be extended to infinite sets of individuals without affecting reasoning complexities. We argue that this might be a more suitable semantics when considering entailments of axioms with nominal schemas.

ABSTRACT. Developing and maintaining ontologies is an expensive and error-prone task. After an error is detected, users may have to wait for a long time before a corrected version of the ontology is available. In the meantime, one might still want to derive meaningful knowledge from the ontology, while avoiding the known errors. We introduce brave and cautious reasoning and show that it is hard for EL. We then propose methods for improving the reasoning times by precompiling information about the known errors and using proof-theoretic techniques for computing justifications. A prototypical implementation shows that our approach is feasible for large ontologies used in practice.

ABSTRACT. We present a new method for detecting logical differences between EL-terminologies extended with role inclusions, domain and range restrictions of roles using a hypergraph representation of ontologies. In this paper we only consider differences that are given by pairs consisting of a conjunctive query together with an ABox formulated over a signature of interest. We define a simulation notion between such hypergraph representations and we show that its existence coincides with the absence of a logical difference. To demonstrate the practical applicability of our approach, we evaluate the performance of our prototype implementation on large ontologies.

ABSTRACT. In this paper we use directed hypergraphs to represent the locality-based dependencies between the axioms of an OWL ontology. We define a notion of a axiom dependency hypergraph, where axioms are represented as nodes and dependencies between axioms as hyperedges connecting possibly several nodes with one node. We show that a locality-based module of an ontology corresponds to a set of connected nodes in the hypergraph, and atoms of an ontology to strongly connected components. Collapsing the strongly connected components into single nodes yields a condensed axiom dependency hypergraph, which contains the atomic decomposition of the ontology. To condense the axiom dependency hypergraph we exploit linear time graph algorithms on its graph fragment. This approach can significantly reduce the time needed to compute the atomic decomposition of an ontology. We provide an experimental evaluation for computing the atomic decomposition of large biomedical ontologies.

ABSTRACT. We present a novel approach to parallel materialisation (i.e., fixpoint computation) of OWL RL Knowledge Bases in centralised, main-memory, multi-core RDF systems. Our approach comprises a parallel reasoning algorithm that evenly distributes the workload to cores, and an RDF indexing data structure that supports efficient, `mostly' lock-free parallel updates. Our empirical evaluation shows that our approach parallelises computation very well so, with 16 physical cores, materialisation can be up to 13.9 times faster than with just one core.

ABSTRACT. Absorption is a well-known and very important optimisation technique that is widely used to reduce non-determinism for tableau-based reasoning systems. In this paper, we present the partial absorption algorithm which allows for absorbing parts of concepts of very expressive Description Logics and, thus, further reduces non-determinism. In addition, we present several extensions of the basic algorithm, which, for example, can be used to improve the handling of datatypes. The described absorption techniques are used in the reasoning system Konclude and they are essential for Konclude's performance.

ABSTRACT. Query answering over SROIQ TBoxes is an important reasoning task for many modern applications. Unfortunately, due to its high computational complexity, SROIQ reasoners are still not able to cope with datasets containing billions of data. Consequently, application developers often employ provably scalable systems which only support a fragment of SROIQ and which are, hence, most likely incomplete for the given input. However, this notion of completeness is too coarse since it implies that there exists \emph{some} query and \emph{some} dataset for which these systems would miss answers. Nevertheless, there might still be a large number of user queries for which they can compute all the right answers even over SROIQ TBoxes. In the current paper, we investigate whether, given a (ground) query Q over a SROIQ TBox T and a system ans, it is possible to identify in an efficient way if ans is complete for Q,T and every dataset. We give sufficient conditions for (in)completeness and present a hybrid query answering algorithm which uses ans when it is complete, otherwise it falls back to a fully-fledged SROIQ reasoner. However, even in the latter case, our algorithm still exploits ans as much as possible in order to reduce the search space of the SROIQ reasoner. Finally, we have implemented our approach using a concrete system ans and SROIQ reasoner obtaining encouraging results.

ABSTRACT. We consider the consequences on basic reasoning problems of allowing negated primitive concepts on left-hand-sides of inclusion dependencies in the description logic dialect CFDnc. Although earlier work has shown that this makes CQ answering coNP-complete, we show that TBox consistency and concept satisfiability remain in PTIME. We also show that knowledge base consistency and instance retrieval remain in PTIME if a CFDnc knowledge base satisfies a number of additional conditions, and that failing any one of these conditions will alone lead to intractability for these problems.

ABSTRACT. We describe a hybrid approach to conjunctive query answering over OWL 2 ontologies that combines a datalog reasoner with a fully-fledged OWL 2 reasoner in order to provide scalable “pay as you go” performance. Our approach delegates the bulk of the computation to the highly scalable datalog engine and resorts to expensive OWL 2 reasoning only as necessary to fully answer the query. We have implemented a prototype system that uses RDFox as a datalog reasoner, and HermiT as an OWL 2 reasoner. Our evaluation over both benchmark and realistic ontologies and datasets suggests the feasibility of our approach.

ABSTRACT. Several attempts have been made to develop similarity measures for ontologies. Motivated by finding problems in existing measures, we design a new family of measures to address these problems. We carry out two sets of empirical studies. Firstly, to explore how good the new measures are by comparing them to human judgments of similarity. Secondly, we investigate how likely it is to encounter specific task-oriented problems when using a bad similarity measure.

ABSTRACT. Description Logics (DLs) have succeeded as a knowledge representation formalism in many domains of application. Nevertheless, they are not suitable to represent vague or imprecise information. To overcome this limitation, several fuzzy extensions have been proposed in the literature. An important family of reasoning algorithms for fuzzy DLs are based on a combination of tableaux algorithms and optimization problems. However, existing algorithms so far cannot support nominals.

In this paper, we give a step in this direction by studying the more specific case of value restrictions. In particular, we propose a novel reasoning algorithm for a fuzzy DL with value restrictions and functional roles. Interestingly, the tableaux algorithm is deterministic and does not need any guessing when dealing with nominal nodes.

ABSTRACT. In the last few years, the complexity of reasoning in fuzzy description logics has been studied in depth. Surprisingly, despite being arguably the simplest form of fuzzy semantics, not much is known about the complexity of reasoning in fuzzy description logics using the Gödel t-norm. It was recently shown that in the logic G-IALC under witnessed model semantics, all standard reasoning problems can be solved in exponential time, matching the complexity of reasoning in classical ALC. We show that this also holds under general model semantics.

ABSTRACT. Regular path queries (RPQs) define query patterns in terms of regular expressions and are therefore well-suited to query for paths over roles in DL. RPQs can be extended to 2-way RPQs (with converse), CRPQs (with conjunctions), or PRPQs (arbitrary positive Boolean combinations), all of which have been explored in DL research. Another natural extension of any query language is nesting, where query predicates can be defined in terms of subqueries. In this paper, we discuss several ways of introducing nesting to PRPQs, and show that they lead to increasingly expressive query languages: CN2RPQs, which were studied in the context of DLs recently; nested P2RPQs; and positive queries with transitive closure on binary predicates. The latter is one of the most expressive languages for which query answering can still be decided over DL knowledge bases. We present initial complexity results that show query answering to be non-elementary in the worst case, with an exponential increase for each level of nesting.

ABSTRACT. Mapping relational data to RDF is an important task for the development of the Semantic Web. To this end, the W3C has recently released a Recommendation for the so-called direct mapping of relational data to RDF. In this work, we propose an enrichment of the direct mapping to make it more faithful by transferring also semantic information present in the relational schema from the relational world to the RDF world. For this purpose we enrich DL-Lite_{RDFS} with expressive identification constraints to capture functional dependencies and define an RDF Normal Form, which precisely captures the classical Boyce-Codd Normal Form of relational schemas.

ABSTRACT. In recent years many FDLs based on infinite t-norms have been proved to be undecidable. On the other hand, several FDLs based on finite t-norms, not only have been proved to be decidable, but they have been proved to belong to the same complexity classes as the corresponding crisp DLs. On the light of such results, a question that naturally arises is whether the finite-valued fuzzy framework is really more complex than the old crisp-valued formalism. The aim of this work is to analyze some of the complexity sources that are not present in the crisp framework. To this end, we will consider FDL languages with low expressivity that allow us to observe how the need for more complex deciding strategies, not required in the crisp framework, arises in many-valued FDLs.

ABSTRACT. This paper investigates how to restrict the spread of sensitive information. This work is situated in a military context, and provides a tractable method to decide what semantic information to share, with whom, and how. The latter decision is supported by obfuscation, where a related concept or fact may be shared instead of the original. We consider uncertain information, and utilise Subjective Logic as an underlying formalism to further obfuscate concepts, and reason about obfuscated concepts.

ABSTRACT. We present Bayesian Description Logics (BDLs): an extension of Description Logics with contextual probabilities encoded in a Bayesian network (BN). Classical DL reasoning tasks are extended to consider also the contextual and probabilistic information in BDLs. A complexity analysis of these problems shows that, for propositionally closed DLs, this extension comes without cost, while for tractable DLs the complexity is affected by the cost of reasoning in the BN.

ABSTRACT. Revision of knowledge bases expressed in Description Logics (DLs) has gained a lot of attention lately. Existing revision algorithms can be divided into two groups: model-based approaches (MBAs) and formula-based approaches(FBAs). MBAs are independent of the syntactical forms of the knowledge base, and are fine-grained for the changes between knowledge bases; however, they only work for some restricted forms of the DL-Lite family. FBAs can deal with expressive DLs such as $\mathcal{SHOIN}$, but they are syntax-dependent and not fine-grained. In this paper, by combining MBAs and FBAs in some form, we present a new method for revising DL-based knowledge bases in the instance level. In our algorithm, a typical model is firstly constructed for the knowledge base to be revised; then a revision process based on justifications is carried out on this model by treating this model as a set of assertions; finally the resulted model is mapped back to a knowledge base which will be returned by the algorithm. Our algorithm are not only syntax-independent and fine-grained, but also works well for the description logic $\mathcal{EL_{\bot}}$ which extends $\mathcal{EL}$ with bottom concept.

ABSTRACT. In this paper we introduce the notion of an ontology excerpt as being a fixed-size subset of an ontology that preserves as much as possible of the meaning of the terms in a given signature as described in the ontology. We consider different extraction techniques for ontology excerpts based on methods from information retrieval. To evaluate these techniques we measure the degree of incompleteness of the resulting excerpts using the notion of logical difference. As such a measure we use the number of concept names from an input signature that witness the logical concept difference between the ontology and its excerpt. We provide an experimental evaluation of the extraction techniques using the biomedicalal ontology SNOMED CT.

ABSTRACT. In this paper we present Graphol, a novel language for the diagrammatic representation of Description Logic (DL) ontologies. Graphol is designed with the aim of offering a completely visual representation to the users (notably, no formulae need to be used in our diagrams), thus helping the understanding of people not skilled in logic. At the same time, it provides designers with simple mechanisms for ontology editing, which free them from having to write down complex textual syntax. Graphol offers most of the classical constructs used in DLs, and allows for specifying expressive ontologies. It is also suitably extended to capture the same expressivity of OWL 2. In this respect, we developed a basic tool to translate Graphol ontologies realized with the yEd graph editor into OWL 2 encoding. User evaluation tests, conducted with designers skilled in conceptual or ontology modeling and users without specific logic background, demonstrate the effectiveness of our language for both visualization and editing of ontologies.

ABSTRACT. Ontology-based data access (OBDA) is a new paradigm aiming at accessing and managing data by means of an ontology, i.e., a conceptual representation of the domain of interest in the underlying information system. In the last years, this new paradigm has been used for providing users with suitable mechanisms for querying the data residing at the information system sources. Most of the research has been concentrating on making query answering efficient. However, query answering is not the only service that an OBDA system must provide. Another crucial service is consistency checking. Current approaches to this problem involves executing expensive queries at run-time. In this paper we address a fundamental problem for OBDA system: given an OBDA specification, can we avoid the consistency check on the whole OBDA system (global consistency check), and rely instead on the constraint checking carried out by the DBMS on the data source (local consistency checking)? We present algorithms and complexity analysis for this problem, showing that it can be solved efficiently for a class of OBDA systems that is very relevant in practice.

ABSTRACT. We compare the expressiveness of the description logics that extend \ALCreg (a variant of PDL) with any combination of the features: inverse roles, nominals, quantified number restrictions, the universal role, the concept constructor for expressing the local reflexivity of a role. The comparison is done for the expressiveness with respect to concepts, positive concepts and TBoxes. It is based on bisimulations.

ABSTRACT. Dealing with uncertainty is a very important issue in description logics (DLs). Therefore, several approaches proposed probabilistic extensions of DLs but most of them are difficult to use and don't support the belief degree in terminological axioms or use graphical models such as Bayesian Network or are based on classical models. In this paper, we present PrDL lite N bool a new probabilistic extension of DL Lite N bool, known as a very expressive DL Lite, by supporting the belief degree interval in a single axiom or a set of axioms connected with conjunction (by ∧) or disjunction (by ∨) operators. The PrDL lite N bool semantics is based on DL Lite N bool features which are a new alternative semantics for DL lite N bool having a finite structure and its number is always finite unlike classical models. PrDL lite N bool also supports terminological and assertional probabilistic knowledge and the reasoning tasks (satisfiability, deciding the entailment, computing tight interval for entailment) are achieved by solving linear optimization problems. A prototype of the approach is implemented using OWLAPI for knowledge base creation, Pellet for reasoning and LpSolve for solving the linear programs.

ABSTRACT. In Description Logics (DL) knowledge bases (KBs) information is typically captured by crisp concepts. For many applications querying the KB by crisp query concepts is too restrictive. A controlled way of gradually relaxing a query concept can be achieved by the use of concept similarity. We formalize the task of instance query answering for crisp DL KBs using concepts relaxed by concept similarity measures (CSM). For the DL EL we investigate computation algorithms for this task, their complexity and properties for the employed CSM in case unfoldable TBoxes or general TBoxes are used.

ABSTRACT. We present a method for generating understandable explanations in description logic. Such explanations could be of potential use for e.g. engineers, doctors, and users of the semantic web. Users commonly need to understand why a logical statement follows from a set of hypotheses. Then automatically generated explanations that are easily understandable could be of help. A proof system for description logic that can be used for generating understandable explanations is proposed. Similar systems have been proposed for propositional logic and first-order logic.

ABSTRACT. We propose a nonmonotonic extension of SHIQ, which is at the base of the OWL-DL language and does not enjoy the finite model property. We extend to SHIQ the well established notion of rational closure, a nonmonotonic mechanism introduced by Lehmann and Magidor for propositional logic, built on the top of the rational logic R. We start from an extension of SHIQ with a typicality operator T, whose aim is to select the typical (the most normal) instances of a concept C: T(C) stands for typical Cs. As a further contribution, we provide a semantic characterization of the rational closure for SHIQ, namely a minimal model semantics built upon standard Description Logics models enriched with a preference relation among domain elements.

ABSTRACT. The formal definition of abduction asks what needs to be added to a knowledge base to enable an observation to be entailed. TBox abduction in description logics (DLs) asks what TBox axioms need to be added to a DL knowledge base to allow a TBox axiom to be entailed. We describe a sound and complete algorithm, based on the standard DL tableau, that takes a TBox abduction problem in ALC and generates solutions in a restricted language. We then show how this algorithm can be enhanced to deal with a broader range of problems in ALC.

ABSTRACT. Ontology modelling sometimes calls for higher order entities, i.e., classes of classes, and so on. Such constructs are, however, not supported by most widely used ontology languages, such as OWL 2, which is based on the SROIQ DL. This often results in approximate modelling techniques, such as modelling classes as individuals. Some of the logical and ontological information is thus lost, or at least obscured. In this paper we show a typed higher-order variant of SROIQ. We show that it is decidable, and in fact polynomially reducible into regular SROIQ. In the latter part of the paper we then illustrate modelling scenarios in which such a language is useful.

ABSTRACT. We present a non-deterministic consequence-based procedure for the description logic ALCHI. Just like the similar style (deterministic) procedures for EL and Horn-SHIQ, our procedure explicitly derives subsumptions between concepts, but due to non-deterministic rules, not all of these subsumptions are consequences of the ontology. Instead, the consequences are only those subsumptions that can be derived regardless of the choices made in the application of the rules. This is similar to tableau-based procedures, for which an ontology is inconsistent if every expansion of the tableau eventually results in a clash. We report on a preliminary experimental evaluation of the procedure using a version of SNOMED~CT with disjunctions, which demonstrates some promising potential.

ABSTRACT. Program Analysis requires expressive logics enjoying good computational properties and capable of describing graph-structured information. In particular, logical representation of standard dynamic data structures like lists or trees requires some form of reachability assertions. However, reachability is usually not expressible in decidable logics for graphs such as guarded first-order logic (GF), and thus in Description Logics (DLs), which are mainly fragments of GF. In this work, we introduce the DL $ALCQIO_{b,Re}$ that extends the Boolean $ALCQIO$ KBs with reachability assertions and is tailored for reasoning over programs with dynamic data structures. $ALCQIO_{b,Re}$ is powerful enough to express (an unbounded number of) lists and trees, can describe complex data structures with a high degree of sharing, and also allows compositions like trees of lists or lists of trees. We show that finite model reasoning in $ALCQIO_{b,Re}$ is polynomial-time reducible to finite satisfiability of $ALCQIO$-formulae. As a consequence, we get that finite satisfiability and finite implication in $ALCQIO_{b,Re}$ are NEXPTIME-complete. Extensions of DLs with reachability have been studied previously (mainly in terms of fix-points and regular expressions), but $ALCQIO_{b,Re}$ is the first such enriched DL that remains decidable in the simultaneous presence of nominals, inverse roles and counting quantifiers.

ABSTRACT. In this paper we present an in progress prototype for the graphical visualization and management of mappings for Ontology-based data access (OBDA). The tool supports the specification of expressive mappings linking a DL-Lite ontology to a relational source database, and allows the designer to graphically navigate them, according to various possible views, modify their textual representation, and validate their syntactic correctness. Furthermore, it gives preliminary support to the semantic analysis of the mappings, which aims to identify anomalies in the representation, like the specification of mapping queries that cannot return answers without contradicting the ontology. Such functionalities are currently being enhanced in our ongoing development of the tool.

ABSTRACT. The language Hi(DL-LiteR) is obtained from DL-LiteR by adding metamodeling features, and is equipped with a query language that is able to express higher-order queries. We investigate the problem of answering a particular class of such queries, called instance higher-order queries posed over Hi (DL-LiteR ) knowledge bases (KBs). The only existing algorithm for this problem is based on the idea of reducing the evaluation of a higher-order query Q over a Hi(DL-LiteR) KB to the evaluation of a union of first-order queries over a DL-LiteR KB, built from Q by instantiating in all possible ways all metavariables. Even though of polynomial time complexity with respect to the size of the KB, this algorithm turns out to be inefficient in practice. In this paper we present a new algorithm, called Smart Binding Planner (SBP), that compiles Q into a program, that issues a sequence of first-order conjunctive queries, where each query has the goal of providing the bindings for metavariables of the next ones, and the last one completes the process by computing the answers to Q. We also illustrate some experiments showing that, in practice, SBP is significantly more efficient than the previous approach.

ABSTRACT. We design and investigate a new interval based temporal description logic, EL-Lambda, which is based on an Annotated Logic introduced by Kifer, AL, and motivated by life-science applications. We show how a subset of the logic can captured as the EL fragment of AL, EL-AL, and then go on to show how we can extend this representation to capture further temporal entailments. We show that both EL-Lambda and EL-AL maintain the same tractable complexity bounds for reasoning as EL and finally provide an example of how the logic can be utilised for the Drosophila developmental ontology.

ABSTRACT. Ontology repair remains one of the main bottlenecks for the development of ontologies for practical use. Many automated methods have been developed for suggesting potential repairs, but ultimately human intervention is required for selecting the adequate one, and the human expert might be overwhelmed by the amount of information delivered to her. We propose a decomposition of ontologies into smaller components that can be repaired in parallel. We show the utility of our approach for ontology repair, provide algorithms for computing this decomposition through standard reasoning, and study the complexity of several associated problems.

ABSTRACT. Competency Questions (CQs) play an important role in the ontology development life-cycle, as they represent the ontology requirements. Although the main methodologies use them, there is room for improvement in the current practice of ontology engineering. One of the main problems is the lack of tools to check if CQs defined in OWL, are being fulfilled by an ontology, preferably in an automated way. Moreover, requirement (or CQ) traceability is rarely explored. Recently there has been a trend on checking CQs against ontologies using RDF and SPARQL. Naturally, this language, being created for Semantic Networks, is inadequate to check the fulfillment of OWL CQs. In this paper, we introduce a semi-automatic, full-fledged method to develop ontologies iteratively, using CQs as requirements. It presents many novelties: a tracer to monitor the relations among CQs and the OWL code; an NLP component that translates CQs in natural language into OWL queries; a logic checker that confirms whether CQs are satisfied or not; a generator of new CQs, which comes into play when the CQ being dealt is not satisfied yet; and an axiom generator that suggests to the user new axioms to be included in the ontology.

ABSTRACT. Very expressive Description Logics in the $\Logic{SH}$ family have worst case complexity ranging from \complexity{EXPTIME} to double \complexity{NEXPTIME}. In spite of this, they are very popular with modellers and serve as the foundation of the Web Ontology Language (OWL), a W3C standard. Highly optimised reasoners handle a wide range of naturally occurring ontologies with relative ease, albeit with some pathological cases. A recent optimisation trend has been \emph{modular} reasoning, that is, breaking the ontology into hopefully easier subsets with a hopefully smaller overall reasoning time (see MORe and Chainsaw for prominent examples).

However, it has been demonstrated that subsets of an OWL ontology may be harder -- even much harder -- than the whole ontology. This introduces the risk that modular approaches might have even more severe pathological cases than the normal monolithic approaches.

In this paper, we analyse a number of ontologies from the BioPortal repository in order to isolate cases where random subsets are harder than the whole. For such cases, we then examine whether the module nearest to the random subset also exhibits the pathological behaviour.

ABSTRACT. The preferential approach to nonmonotonic reasoning was consolidated in depth by Krause, Lehmann and Magidor (KLM) for propositional logic in the early 90’s. In recent years, there have been efforts to extend their framework to Description Logics (DLs) and a solid theoretical foundation has already been established towards this aim. Despite this foundation, and the fact that many of the desirable aspects of the approach generalise favourably to certain DLs, implementations thereof remain unpublished. We present a defeasible reasoning system for OWL ontologies demonstrating that we need not devise new decision procedures for certain preferential DLs. Our reasoning procedures are composed purely of classical DL decision steps which allows us to immediately hinge upon existing OWL and DL systems for defeasible reasoning tool support.

ABSTRACT. Representing temporal data in conceptual data models and ontologies is required by various application domains, and for it to be useful for modelling precision and useful with automated reasoners, a language that is expressive enough to capture the required operational semantics of the time-varying information is essential. Temporal modelling languages have little support for temporal attributes, if at all, yet attributes are a standard element in the widely used conceptual modelling languages such as EER and UML. This hiatus prevents one to utilise a complete temporal conceptual data model and keep track of evolving values of data and its interaction with temporal classes. A rich axiomatization of fully temporized attributes is possible with a minor extension to the already very expressive description logic language DLRUS . We formalize the notion of transition of attributes, and their interaction with transition of classes. The transition specified for attributes are extension, evolution, and arbitrary quantitative extension.

ABSTRACT. The paper contributes to the recent enterprise of temporalizing and streamifiying ontology based data access (OBDA) by discussing rewritability and unfoldability aspects for DL-Lite instantiations of the new query-language framework STARQL. In particular, it demonstrates how STARQL queries can be rewritten and unfolded into queries expressed in one of the early relational stream query languages, the continuous query language CQL.

ABSTRACT. Rough Description Logics have recently been studied as a means for representing and reasoning with imprecise knowledge. Real-world applications need to exploit reasoning over such knowledge in an efficient way. We describe how the combined approach to query answering can be extended to the rough setting. In particular, we extend both the canonical model and the rewriting procedure such that rough queries over rough EL ontologies can be answered by considering this information alone.

ABSTRACT. We propose a novel approach for performance prediction of OWL reasoners. It selects suitable, small ontology subsets, and then extrapolates reasoner's performance on them to the whole ontology. We investigate intercorrelation of ontology features using PCA. Finally, we discuss various error measures for performance prediction and compare our approach against an existing one using these measures.

ABSTRACT. Many applications nowadays expose data in semantic formats such as RDF and OWL. The standard query language to access such data is SPARQL. Writing SPARQL requires requires training and it is not feasible for unexperienced users. In this paper we present OptiqueVQS, a query formulation interface that addresses this problem and allows to construct conjunctive SPARQL queries in an intuitive way. Our approach relies on a graph based representation paradigm to visualise queries. Users can construct queries step by step and OptiqueVQS provides them with suggestions on how to continue query construction. These suggestions depend on specific parts of the constructed query and automatically computed by reasoning over the ontology underlying the interface. OptiqueVQS has two types of suggestions which are based on data and object properties. Preliminary user studies of the interface with geologists gave us encouraging results.

ABSTRACT. In previous work it has been shown how a SROIQ ontology O can be `repaired' for an RL system ans---that is, how we can compute a set of axioms R that is independent from the data and such that ans that is generally incomplete for O becomes complete for all SPARQL queries when used with O and R. However, the initial implementation and experiments were very preliminary and hence it is currently unclear whether the approach can be applied to large and complex ontologies. Moreover, the approach could not support non-SPARQL CQs. In the current paper we thoroughly investigate repairing as an approach to scalable (and complete) ontology-based data access. First, we present several non-trivial optimisations to the first prototype. Second, we show how (arbitrary) conjunctive queries can be supported by integrating well-known query rewriting techniques with RL systems via repairing. Third, we perform an extensive experimental evaluation obtaining encouraging results. In more detail, our results show that we can compute repairs even for very large real-world ontologies in a reasonable amount of time, that the performance overhead introduced by repairing is negligible in small to medium sized ontologies and noticeable but manageable in large and complex one, and that our approach to handling non-SPARQL CQs can very efficiently compute the correct answers for real-world challenging TBoxes.

ABSTRACT. The development and maintenance of large and complex ontologies are often time-consuming and error-prone. Thus, automated ontology learning and revision have attracted intensive research interest. In data-centric applications where the ontology is designed based on or automated learnt from the data, when new data instances are added that contradict to the ontology, it is often desirable to incrementally revise the ontology according to the added data. In this paper, we address this problem using TBox revision and allow TBox axioms to be revised by ABox assertions. To provide a model-theoretic characterisation of minimal change, we introduce and apply the type semantics for DL-Lite TBoxes. We define a concrete revision operator using the type semantics, and show that it possesses desired properties.

ABSTRACT. An essential task in managing description logic (DL) ontologies is the removal of problematic axioms. Such removal is formalised as the operation of contraction in belief change. In this paper, we investigate contraction over DL-Lite$_\R$ TBoxes so as to provide methods for eliminating problematic axioms in DL-Lite$_\R$ TBoxes. In belief change, a well known approach in defining contraction is via epistemic entrenchments which are essentially preference orderings over formulas. The approach however is not applicable in DLs as classic belief change assumes an underlying logic different from DLs. Thus we reformulate the epistemic entrenchment approach so as to make it applicable to DL-Lite$_\R$. We then provide representation theorem and a tractable algorithm for the reformulated approach.