Arrow Research search

Author name cluster

Ulrike Sattler

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.

26 papers
2 author rows

Possible papers

26

JELIA Conference 2021 Conference Paper

ReAD: AD-Based Modular Ontology Classification

  • Haoruo Zhao
  • Bijan Parsia
  • Ulrike Sattler

Abstract For OWL ontologies, classification is the central reasoning task, and several highly-optimised reasoners have been designed for different fragments of OWL. Some of these exploit different notions of modularity, including the atomic decomposition (AD), to further optimise their performance, but this is a complex task due to ontology modules overlapping, thereby possibly causing duplication of subsumption tests. In this paper, we use the AD to avoid both this duplication as well as other subsumption tests that can be avoided by inspecting the AD. We have designed and implemented a new AD-informed and \(\mathsf {MORe}\) -inspired algorithm that uses \(\mathsf {Hermit}\) and \(\mathsf {ELK}\) as delegate reasoners, but avoids any duplicate subsumption tests between these two reasoners and further minimises these tests. We have thoroughly evaluated the effects of these two kinds of avoidance on the overall classification time on a corpus of complex ontologies.

Details

KR Conference 2012 Short Paper

Justification Masking in Ontologies

  • Matthew Horridge
  • Bijan Parsia
  • Ulrike Sattler

are parts of these axioms that are superfluous as far as the entailment is concerned: In the first axiom the filler of the existential restriction is superfluous, in the third axiom the conjunct E is superfluous for the entailment. Given that justifications are not minimal with respect to their “parts” and thus with respect to their logical content, it is possible for the cardinality of the set of justifications to be different from the set of reasons for an entailment, that is, justifications can mask the set of reasons. For example, consider J = {A v ∃R. C u ∀R. C, D ≡ ∃R. C} which entails A v D. Clearly, J is a justification for A v D. It is also noticeable that there are superfluous parts in this justification. Moreover, there are two distinct reasons why J |= A v D, the first being {A v ∃R. C, ∃R. C v D} and the second being {A v ∃R. > u ∀R. C, ∃R. C v D}. The work presented in the paper describes how masking can occur within a justification, over a set of justifications, and over a set of justifications plus axioms outside the set of justifications. The main problems identified with masking are (i) it can hamper understanding—not all reasons for an entailment may be salient to a person trying to understand the entailment, and (ii) it can hamper the design or choice of a repair plan—not all reasons for an entailment may be obvious, and if the plan consists of weakening and removing parts of axioms it may not actually result in a successful repair of the ontology in question. This paper presents a characterisation of and definitions for the phenomenon of masking in the context of justifications for entailments in ontologies. In essence masking is present within a justification, over a set of justifications, or over a complete ontology when the number of justifications for an entailment does not reflect the number of reasons for that entailment. Four types of masking are defined in this paper: Internal Masking, Cross Masking, External Masking and Shared Core Masking. The results of an empirical study are presented which shows that the phenomenon of masking is prevalent throughout ontologies with non-trivial entailments in the NCBO BioPortal corpus. Out of 72 ontologies, 53 exhibited some form of masking, with 9 ontologies exhibiting internal masking, 23 ontologies exhibiting external masking, and 53 ontologies exhibiting shared core masking.

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.

PDF Details

KR Conference 2008 Conference Paper

Representing Structured Objects using Description Graphs

  • Boris Motik
  • Bernardo Cuenca Grau
  • Ian Horrocks
  • Ulrike Sattler

State-of-the-art ontology languages are often not sufficiently expressive to accurately represent domains consisting of objects connected in a complex way. As a possible remedy, in our previous work we have proposed an extension of ontology languages with description graphs. In this paper, we extend this formalism by allowing for multiple graphs that can be combined in complex ways, thus obtaining a powerful language for modeling structured objects. By imposing a particular acyclicity restriction on the relationships between the graphs, we ensure that checking satisfiability of knowledge bases expressed in our language is decidable. We also present a practical reasoning algorithm.

KR Conference 2008 Conference Paper

Unions of Conjunctive Queries in SHOQ

  • Birte Glimm
  • Ian Horrocks
  • Ulrike Sattler

Conjunctive queries play an important role as an expressive query language in Description Logics (DLs). Decision procedures for expressive Description Logics are, however, only recently emerging and it is still an open question whether answering conjunctive queries is decidable for the DL SHOIQ that underlies the OWL DL standard. In fact, no decision procedure was known for expressive DLs that contain nominals. In this paper, we close this gap by providing a decision procedure for entailment of unions of conjunctive queries in SHOQ. Our algorithm runs in deterministic time single exponential in the size of the knowledge base and double exponential in the size of the query, which is the same as for SHIQ. Our procedure also shows that SHOQ knowledge base consistency is indeed ExpTime-complete, which was, to the best of our knowledge, always conjectured but never proved.

IJCAI Conference 2007 Conference Paper

  • Birte Glimm
  • Ian Horrocks
  • Carsten Lutz
  • Ulrike Sattler

Conjunctive queries play an important role as an expressive query language for Description Logics (DLs). Although modern DLs usually provide for transitive roles, it was an open problem whether conjunctive query answering over DL knowledge bases is decidable if transitive roles are admitted in the query. In this paper, we consider conjunctive queries over knowledge bases formulated in the popular DL SHIQ and allow transitive roles in both the query and the knowledge base. We show that query answering is decidable and establish the following complexity bounds: regarding combined complexity, we devise a deterministic algorithm for query answering that needs time single exponential in the size of the KB and double exponential in the size of the query. Regarding data complexity, we prove co-NP-completeness.

PDF Details

IJCAI Conference 2007 Conference Paper

  • Franz Baader
  • Bernhard Ganter
  • Ulrike Sattler
  • Baris Sertkaya

We propose an approach for extending both the terminological and the assertional part of a Description Logic knowledge base by using information provided by the knowledge base and by a domain expert. The use of techniques from Formal Concept Analysis ensures that, on the one hand, the interaction with the expert is kept to a minimum, and, on the other hand, we can show that the extended knowledge base is complete in a certain, well-defined sense.

PDF Details

IJCAI Conference 2007 Conference Paper

  • Bernardo Cuenca Grau
  • Ian Horrocks
  • Yevgeny Kazakov
  • Ulrike Sattler

Modularity is a key requirement for collaborative ontology engineering and for distributed ontology reuse on the Web. Modern ontology languages, such as OWL, are logic-based, and thus a useful notion of modularity needs to take the semantics of ontologies and their implications into account. We propose a logic-based notion of modularity that allows the modeler to specify the external signature of their ontology, whose symbols are assumed to be defined in some other ontology. We define two restrictions on the usage of the external signature, a syntactic and a slightly less restrictive, semantic one, each of which is decidable and guarantees a certain kind of "black-box" behavior, which enables the controlled merging of ontologies. Analysis of real-world ontologies suggests that these restrictions are not too onerous.

PDF Details

LPAR Conference 2007 Conference Paper

How Many Legs Do I Have? Non-Simple Roles in Number Restrictions Revisited

  • Yevgeny Kazakov
  • Ulrike Sattler
  • Evgeny Zolin

Abstract The Description Logics underpinning OWL impose a well-known syntactic restriction in order to preserve decidability: they do not allow to use non-simple roles—that is, transitive roles or their super-roles—in number restrictions. When modeling composite objects, for example in bio-medical ontologies, this restriction can pose problems. X Therefore, we take a closer look at the problem of counting over non-simple roles. On the one hand, we sharpen the known undecidability results and demonstrate that: (i) for DLs with inverse roles, counting over non-simple roles leads to undecidability even when there is only one role in the language; (ii) for DLs without inverses, two transitive and an arbitrary role are sufficient for undecidability. On the other hand, we demonstrate that counting over non-simple roles does not compromise decidability in the absence of inverse roles provided that certain restrictions on role inclusion axioms are satisfied.

Details

LPAR Conference 2006 Conference Paper

A Comparison of Reasoning Techniques for Querying Large Description Logic ABoxes

  • Boris Motik
  • Ulrike Sattler

Abstract Many modern applications of description logics (DLs) require answering queries over large data quantities, structured according to relatively simple ontologies. For such applications, we conjectured that reusing ideas of deductive databases might improve scalability of DL systems. Hence, in our previous work, we developed an algorithm for reducing a DL knowledge base to a disjunctive datalog program. To test our conjecture, we implemented our algorithm in a new DL reasoner KAON2, which we describe in this paper. Furthermore, we created a comprehensive test suite and used it to conduct a performance evaluation. Our results show that, on knowledge bases with large ABoxes but with simple TBoxes, our technique indeed shows good performance; in contrast, on knowledge bases with large and complex TBoxes, existing techniques still perform better. This allowed us to gain important insights into strengths and weaknesses of both approaches.

Details

AAAI Conference 2006 Conference Paper

Deciding Semantic Matching of Stateless Services

  • Duncan Hull
  • Andrey Bovykin
  • Ulrike Sattler

We present a novel approach to describe and reason about stateless information processing services. It can be seen as an extension of standard descriptions which makes explicit the relationship between inputs and outputs and takes into account OWL ontologies to fix the meaning of the terms used in a service description. This allows us to define a notion of matching between services which yields high precision and recall for service location. We explain why matching is decidable, and provide biomedical example services to illustrate the utility of our approach.

PDF Details

KR Conference 2006 Conference Paper

The Even More Irresistible SROIQ

  • Oliver Kutz
  • Ian Horrocks
  • Ulrike Sattler

We describe an extension of the description logic underlying OWL-DL, SHOIN, with a number of expressive means that we believe will make it more useful in practise. Roughly speaking, we extend SHOIN with all expressive means that were suggested to us by ontology developers as useful additions to OWL-DL, and which, additionally, do not affect its decidability and practicability. We consider complex role inclusion axioms to express propagation of one property along another one, which have proven useful in medical terminologies. Furthermore, we extend SHOIN with reflexive, antisymmetric, and irreflexive roles, disjoint roles, a universal role, and constructs exists R. Self, allowing, for instance, the definition of concepts such as a "narcist". Finally, we consider negated role assertions in Aboxes and qualified number restrictions. The resulting logic is called SROIQ. We present a rather elegant tableau-based reasoning algorithm: it combines the use of automata to keep track of universal value restrictions with the techniques developed for SHOIQ. The logic SROIQ has been adopted as the logical basis for the next iteration of OWL, OWL 1. 1.

LPAR Conference 2004 Conference Paper

A Decomposition Rule for Decision Procedures by Resolution-Based Calculi

  • Ullrich Hustadt
  • Boris Motik
  • Ulrike Sattler

Abstract Resolution-based calculi are among the most widely used calculi for theorem proving in first-order logic. Numerous refinements of resolution are nowadays available, such as e. g. basic superposition, a calculus highly optimized for theorem proving with equality. However, even such an advanced calculus does not restrict inferences enough to obtain decision procedures for complex logics, such as \(\mathcal{SHIQ}\). In this paper, we present a new decomposition inference rule, which can be combined with any resolution-based calculus compatible with the standard notion of redundancy. We combine decomposition with basic superposition to obtain three new decision procedures: ( i ) for the description logic \(\mathcal{SHIQ}\), ( ii ) for the description logic \(\mathcal{ALCHIQ}b\), and ( iii ) for answering conjunctive queries over \(\mathcal{SHIQ}\) knowledge bases. The first two procedures are worst-case optimal and, based on the vast experience in building efficient theorem provers, we expect them to be suitable for practical usage.

Details

IJCAI Conference 2003 Conference Paper

Keys, Nominals, and Concrete Domains

  • Carsten Lutz
  • Carlos Areces
  • Ian Horrocks
  • Ulrike Sattler

Many description logics (DLs) combine knowledge representation on an abstract, logical level with an interface to "concrete" domains such as numbers and strings. We propose to extend such DLs with key constraints that allow the expression of statements like "US citizens are uniquely identified by their social security number". Based on this idea, we introduce a number of natural description logics and present (un)decidability results and tight NEx- PTlME complexity bounds.

PDF

CSL Conference 2001 Conference Paper

Modal Logic and the Two-Variable Fragment

  • Carsten Lutz
  • Ulrike Sattler
  • Frank Wolter

Abstract We introduce a modal language L which is obtained from standard modal logic by adding the difference operator and modal operators interpreted by boolean combinations and the converse of accessibility relations. It is proved that L has the same expressive power as the two-variable fragment FO 2 of first-order logic but speaks less succinctly about relational structures: if the number of relations is bounded, then L- satisfiability is E xp T ime -complete but FO 2 satisfiability is NE xp Time -complete. We indicate that the relation between L and FO 2 provides a general framework for comparing modal and temporal languages with first-order languages.

Details

LPAR Conference 2000 Conference Paper

How to Decide Query Containment Under Constraints Using a Description Logic

  • Ian Horrocks 0001
  • Ulrike Sattler
  • Sergio Tessaris
  • Stephan Tobies

Abstract We present a procedure for deciding (database) query containment under constraints. The technique is to extend the logic DLR with an ABox, and to transform query subsumption problems into DLR ABox satisfiability problems. Such problems can then be decided, via a reification transformation, using a highly optimised reasoner for the SHIQdescription logic. We use a simple example to support our hypothesis that this procedure will work well with realistic problems.

Details

LPAR Conference 1999 Conference Paper

Practical Reasoning for Expressive Description Logics

  • Ian Horrocks 0001
  • Ulrike Sattler
  • Stephan Tobies

Abstract Description Logics (DLs) are a family of knowledge representation formalisms mainly characterised by constructors to build complex concepts and roles from atomic ones. Expressive role constructors are important in many applications, but can be computationally problematical. We present an algorithm that decides satisfiability of the DL ALC extended with transitive and inverse roles, role hierarchies, and qualifying number restrictions. Early experiments indicate that this algorithm is well-suited for implementation. Additionally, we show that ALC extended with just transitive and inverse roles is still in PSpace. Finally, we investigate the limits of decidability for this family of DLs.

Details