In this work we consider the inference problem of computing (minimal) rewritings of concept descriptions using defined concepts from a terminology. We introduce a general framework for this problem. For the small description logic FL₀, which provides us with conjunction and value restrictions, we show that the decision problem induced by the minimal rewriting problem is NP-complete.

Unification of concept terms is a new kind of inference problem for Description Logics, which extends the equivalence problem by allowing to replace certain concept names by concept terms before testing for equivalence. We show that this inference problem is of interest for applications, and present first decidability and complexity results for a small concept description language. / This revised version of LTCS-Report 97-02 provides a stronger complexity result in Section 6. An abridged version will appear in Proc. ECAI'98 .

We extend different Description Logics by concrete domains (such as integers and reals) and by aggregation functions over these domains (such as min,max,count,sum), which are usually available in database systems. We present decision procedures for the inference problems satisfiability for these Logics-provided that the concrete domain is not too expressive. An example of such a concrete domain is the set of (nonnegative) integers with comparisons (=,≤, ≤n, ...) and the aggregation functions min, max, count. / This is a new, extended version of a report with the same number. An abridged version has appeared in the Proceedings of the European Conference on Artificial Intelligence, Brighton, UK, 1998.

Unification of concept terms is a new kind of inference problem for Description Logics, which extends the equivalence problem by allowing to replace certain concept names by concept terms before testing for equivalence. We show that this inference problem is of interest for applications, and present first decidability and complexity results for a small concept description language.

In two previous reports we have investigated both standard and non-standard inferences in the presence of terminological cycles for the description logic EL, which allows for conjunctions, existential restrictions, and the top concept. Regarding standard inference problems, it was shown there that the subsumption problem remains polynomial for all three types of semantics usually considered for cyclic definitions in description logics, and that the instance problem remains polynomial for greatest fixpoint semantics. Regarding non-standard inference problems, it was shown that, w.r.t. greatest fixpoint semantics, the least common subsumer and the most specific concept always exist and can be computed in ploynomial time, and that, w.r.t. descriptive semantics, the least common subsumer need not exist. The present report is concerned with two problems left open by this previous work, namely the instance problem and the problem of computing most specific concepts w.r.t. descriptive semantics, which is the usual first-order semantics for description logic. We will show that the instance problem is polynomial also in this context. Similar to the case of the least common subsumer, the most specific concept w.r.t. descriptive semantics need not exist, but we are able to characterize the cases in which it exists and give a decidable sufficient condition for the existence of the most specific concept. Under this condition, it can be computed in polynomial time.

Dans cette thèse nous nous intéressons au contrôle d’accès dans un système issu d’une intégration de données. Dans un système d’intégration de données un médiateur est défini. Ce médiateur a pour objectif d’offrir un point d’entrée unique à un ensemble de sources hétérogènes. Dans ce type d’architecture, l’aspect sécurité, et en particulier le contrôle d’accès, pose un défi majeur. En effet, chaque source, ayant été construite indépendamment, définit sa propre politique de contrôle d’accès. Le problème qui émerge de ce contexte est alors le suivant : "Comment définir une politique représentative au niveau du médiateur et qui permet de préserver les politiques des sources de données impliquées dans la construction du médiateur?" Préserver les politiques des sources de données signifie qu’un accès interdit au niveau d’une source doit également l’être au niveau du médiateur. Aussi, la politique du médiateur doit préserver les données des accès indirects. Un accès indirect consiste à synthétiser une information sensible en combinant des informations non sensibles et les liens sémantiques entre ces informations. Détecter tous les accès indirects dans un système est appelé problème d’inférence. Dans ce manuscrit, nous proposons une méthodologie incrémentale qui permet d’aborder le problème d’inférence dans un contexte d’intégration de données. Cette méthodologie est composée de trois phases. La première, phase de propagation, permet de combiner les politiques sources et ainsi générer une politique préliminaire au niveau médiateur. La deuxième phase, phase de détection, caractérise le rôle que peuvent jouer les relations sémantiques entre données afin d’inférer une information confidentielle. Par la suite, nous introduisant, au sein de cette phase, une approche basée sur les graphes afin d’énumérer tous les accès indirects qui peuvent induire l’accès à une information sensible. Afin de remédier aux accès indirects détectés nous introduisons la phase de reconfiguration qui propose deux solutions. La première solution est mise en œuvre au niveau conceptuel. La seconde solution est mise en œuvre lors de l’exécution. / In this thesis we are interested in controlling the access to a data integration system. In a data integration system, a mediator is defined. This mediator aims at providing a unique entry point to several heterogeneous sources. In this kind of architecture security aspects and access control in particular represent a major challenge. Indeed, every source, designed independently of the others, defines its own access control policy. The problem is then: "How to define a representative policy at the mediator level that preserves sources’ policies?" Preserving the sources’ policies means that a prohibited access at the source level should also be prohibited at the mediator level. Also, the policy of the mediator needs to protect data against indirect accesses. An indirect access occurs when one could synthesize sensitive information from the combination of non sensitive information and semantic constraints. Detecting all indirect accesses in a given system is referred to as the inference problem. In this manuscript, we propose an incremental methodology able to tackle the inference problem in a data integration context. This methodology has three phases. The first phase, the propagation phase, allows combining source policies and therefore generating a preliminary policy at the mediator level. The second phase, the detection phase, characterizes the role of semantic constraints in inducing inference about sensitive information. We also introduce in this phase a graph-based approach able to enumerate all indirect access that could induce accessing sensitive information. In order to deal with previously detected indirect access, we introduce the reconfiguration phase which provides two solutions. The first solution could be implemented at design time. The second solution could be implemented at runtime.