Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

La théorie des fonctions des croyances offre des outils puissants pour modéliser et traiter les informations imparfaites. En effet, cette théorie peut représenter l'incertitude,l'imprécision et l'ignorance. Dans ce contexte, les données sont stockées dans des bases de données spécifiques qu'on appelle les bases de données crédibilistes. Une base de donnée crédibiliste a deux niveaux d'incertitudes: (i) l'incertitude au niveau des attributs qui se manifeste à travers des degrés de véracité sur les hypothèses des attributs; (ii) l'incertitude au niveau des tuples représentée par des intervalles de confiance sur l'existence des tuples au sein de la table en question. D'autre part, la base de donnée crédibiliste peut être modélisée sous deux formes: (i) la forme compacte caractérisée par un ensemble d'attributs et un ensemble de tuples; (ii) la forme des mondes possibles représentée par un ensemble de base de données candidates où chaque base candidate est une représentation possible de la base de donnée compacte. Interroger la représentation des mondes possibles est une étape fondamentale pour valider les méthodes d'interrogation sur la base compacte crédibiliste. En effet, un modèle de base de donnée est dit système fort si le résultat de l'interrogation de sa représentation compacte est équivalent au résultat de l'interrogation de sa représentation des mondes possibles.Cette thèse est une étude sur les fondements des bases de données crédibilistes. Les contributions sont résumées comme suit:(i) La modélisation et l'interrogation de la base crédibiliste (EDB): Nous mettons en pratique le modèle compacte de la base de données (EDB) en proposant une implémentation objet-relationnelle, ce qui permet d'introduire l'interrogation de ce modèle avec les opérateurs relationnels. D'autres part, nous présentons le formalisme, les algorithmes et les expérimentations d'autres types de requêtes :les top-k évidentiel et le skyline évidentiel que nous appliquons sur des données réelles extraites de la plateforme Tripadvisor.(ii) La modélisation de la base de données sous sa forme des mondes possibles: Nous modélisons la forme de mondes possibles de la base de données (EDB) en traitant les deux niveaux d'incertitudes (niveau attributs et niveau tuples).(iii) La modélisation et l'interrogation de la base de données crédibiliste (ECD): Après avoir prouvé que le modèle des bases de données (ED B) n'est pas un système de représentation fort, nous développons le modèle de la base de données crédibiliste conditionnelle nommée (ECD). Nous présentons le formalisme de l’interrogation sur les deux formes (compacte et mondes possibles) de la base de données (ECD). Finalement, nous discutons les résultats de ces méthodes d'interrogation et les spécificités du modèle (ECD). / The theory of belief functions (a.k.a, the Evidence Theory) offers powerful tools to mode! and handle imperfect pieces of information. Thus, it provides an adequate framework able to represent conjointly uncertainty, imprecision and ignorance. In this context, data are stored in a specific database model called evidential databases. An evidential database includes two levels of uncertainty: (i) the attribute level uncertainty expressed via some degrees of truthfulness about the hypotheses in attributes; (ii) the tuple level uncertainty expressed through an interval of confidence about the existenceof the tuple in the table. An evidential database itself can be modeled in two forms:(i) the compact form represented as a set of attributes and a set of tuples; (ii) the possible worlds' form represented as a set of candidate databases where each candidate is a possible representation of the imperfect compact database. Querying the possible worlds' form is a fundamental step in order to check the querying methods over the compact one. In fact, a model is said to be a strong representation system when results of querying its compact form are equivalent to results of querying its non compact form.This thesis focuses on foundations of evidential databases in both modeling and querying. The main contributions are summarized as follows:(i) Modeling and querying the compact evidential database (EDB): We implement the compact evidential database (EDB) using the object-relational design which allows to introduce the querying of the database model under relational operators. We also propose the formalism, the algorithms and the experiments of other typesof queries: the evidential top-k and the evidential skyline that we apply over a real dataset extracted from TripAdvisor.(ii) Modeling the possible worlds' form of (EDB): We model the possible worlds' form of the evidential database (EDB) by treating both levels of uncertainty (the tuple leve! and the attribute level).(iii) Modeling and querying the evidential conditional database (ECD): After provingt hat the evidential database (EDB) is not a strong representation system, we develop a new evidential conditional database model named (ECD). Thus, we present the formalism of querying the compact and the possible worlds' forms of the (ECD) to evaluate the querying methods under relational operators. Finally, we discuss the results of these querying methods and the specificities of the (ECD)model.

Ce travail de thèse porte sur un modèle de requête de préférence, appelée l'opérateur Skyline, pour l'exploitation de données imparfaites. L'imperfection de données peut être modélisée au moyen de la théorie de l'évidence. Ce type de données peut être géré dans des bases de données imparfaites appelées bases de données évidentielles. D'autre part, l'opérateur skyline est un outil puissant pour extraire les objets les plus intéressants dans une base de données.Dans le cadre de cette thèse, nous définissons une nouvelle sémantique de l'opérateur Skyline appropriée aux données imparfaites modélisées par la théorie de l'évidence. Nous introduisons par la suite la notion de points marginaux pour optimiser le calcul distribué du Skyline ainsi que la maintenance des objets Skyline en cas d'insertion ou de suppression d'objets dans la base de données.Nous modélisons aussi une fonction de score pour mesurer le degré de dominance de chaque objet skyline et définir le top-k Skyline. Une dernière contribution porte sur le raffinement de la requête Skyline pour obtenir les meilleurs objets skyline appelés objets Etoile ou Skyline stars. / The main purpose of this thesis is to study an advanced database tool named the skyline operator in the context of imperfect data modeled by the evidence theory. In this thesis, we first address, on the one hand, the fundamental question of how to extend the dominance relationship to evidential data, and on the other hand, it provides some optimization techniques for improving the efficiency of the evidential skyline. We then introduce efficient approach for querying and processing the evidential skyline over multiple and distributed servers. ln addition, we propose efficient methods to maintain the skyline results in the evidential database context wben a set of objects is inserted or deleted. The idea is to incrementally compute the new skyline, without reconducting an initial operation from the scratch. In the second step, we introduce the top-k skyline query over imperfect data and we develop efficient algorithms its computation. Further more, since the evidential skyline size is often too large to be analyzed, we define the set SKY² to refine the evidential skyline and retrieve the best evidential skyline objects (or the stars). In addition, we develop suitable algorithms based on scalable techniques to efficiently compute the evidential SKY². Extensive experiments were conducted to show the efficiency and the effectiveness of our approaches.

L’informatique pervasive et l’intelligence ambiante visent à créer un environnement intelligent avec des dispositifs électroniques et informatiques mis en réseau tels que les capteurs, qui s’intègrent parfaitement dans la vie quotidienne et offrent aux utilisateurs un accès transparent aux services partout et à tout moment.Pour garantir ce fonctionnement, un système doit avoir une connaissance globale sur son environnement, et en particulier sur les personnes et les dispositifs, leurs intérêts et leurs capacités, ainsi que les tâches et les activités associées. Toutes ces informations relèvent de la notion de contexte. Cela passe par la collecte des données contextuelles de l’utilisateur pour déterminer sa situation/son activité courante ; on parle alors d’identification de situations/d’activités. Pour cela, le système doit être sensible aux variations de son environnement et de son contexte, afin de détecter les situations/les activités et de s’adapter ensuite dynamiquement. Reconnaître une situation/une activité nécessite alors la mise en place de tout un processus : perception des données contextuelles, analyse de ces données collectéeset raisonnement sur celles-ci pour l’identification de situations/d’activités.Nous nous intéressons plus particulièrement aux aspects liés à la modélisation distribuée de l’environnement ambiant et à ceux liés au raisonnement distribué en présence de données imparfaites pour l’identification de situations/d’activités. Ainsi, la première contribution de la thèse concerne la partie perception. Nous avons proposé un nouveau modèle de perception permettant la collecte des données brutes issues des capteurs déployés dans l’environnement et la génération des évènements. Ensuite, la deuxième contribution se focalise sur l’observation et l’analyse de ces évènements en les segmentant et extrayant les attributs lesplus significatifs et pertinents. Enfin, les deux dernières contributions présentent deux propositions concernant le raisonnement distribué pour l’identification de situations/d’activités; l’une représente la principale contribution et l’autre représente sa version améliorée palliant certaines limites. D'un point de vue technique, toutes ces propositions ont été développées, validées et évaluées avec plusieurs outils. / Pervasive Computing and Ambient Intelligence aim to create a smart environment withnetworked electronic and computer devices such as sensors seamlessly integrating into everyday life and providing users with transparent access to services anywhere and anytime.To ensure this, a system needs to have a global knowledge of its environment, and inparticular about people and devices, their interests and their capabilities, and associated tasks and activities. All these information are related to the concept of context. This involves gathering the user contextual data to determine his/her current situation/activity; we also talk about situation/activity identification. Thus, the system must be sensitive to environment and context changes, in order to detect situations/activities and then to adapt dynamically.Recognizing a situation/an activity requires the definition of a whole process : perception of contextual data, analysis of these collected data and reasoning on them for the identification of situations/activities.We are particularly interested in aspects related to the distributed modeling of the ambient environment and to those related to distributed reasoning in the presence of imperfect data for the identification of situations/activities. Thus, the first contribution of the thesis concerns the perception part. We have proposed a new perception model that allows the gathering of raw data from sensors deployed in the environment and the generation of events.Next, the second contribution focuses on the observation and analysis of these events by segmenting them and extracting the most significant and relevant features. Finally, the last two contributions present two proposals concerning the distributed reasoning for the identification of situations/activities ; one represents the main contribution and the other represents its improved version overcoming certain limitations. From a technical point of view, all these proposals have been developed, validated and evaluated with several tools.