Dans le cadre d’une solution de modification de la requête, nous nous intéressons aux différentes façons d’utiliser la sémantique pour mieux exprimer le besoin d’information de l’utilisateur dans un contexte Web. Nous distinguons deux types de concepts : ceux identifiables dans une ressource sémantique comme une ontologie, et ceux que l’on extrait à partir d’un ensemble de documents de pseudo retour de pertinence. Nous proposons une Approche Sémantique Mixte d’Expansion et de Reformulation (ASMER) qui permet de modéliser l’utilisation de ces deux types de concepts dans une requête modifiée. Cette approche considère plusieurs défis liés à la modification automatique des requêtes, notamment le choix sélectif des termes d’expansion, le traitement des entités nommées et la reformulation de la requête finale.Bien que dans un contexte Web la précision soit le critère d’évaluation le plus adapté, nous avons aussi pris en compte le rappel pour étudier le comportement de notre approche sous plusieurs aspects. Ce choix a suscité une autre problématique liée à l’évaluation du rappel en recherche d’information. En constatant que les mesures précédentes ne répondent pas à nos contraintes, nous avons proposé la mesure MOR (Mesure Orientée Rappel), qui permet d’évaluer le rappel en tenant compte de la précision comme importante mais pas prioritaire dans un contexte dirigé rappel.En incluant MOR dans notre stratégie de test, nous avons évalué ASMER sur quatre collections Web issues des campagnes INEX et TREC. Nos expériences montrent qu’ASMER améliore la performance en précision par rapport aux requêtes originales et par rapport aux requêtes étendues par une méthode de l’état de l’art. / As a query expansion and reformulation solution, we are interested in the different ways the semantic could be used to translate users information need into a query. We define two types of concepts : those which we can identify in a semantic resource like an ontology, and the ones we extract from the collection of documents via pseudo relevance feedback procedure. We propose a semantic and mixed approach to query expansion and reformulation (ASMER) that allows to integrate these two types of concepts in an automatically modified query. Our approach considers many challenges, especially selective terms expansion, named entity treatment and query reformulation.Even though the precision is the evaluation criteria the most adapted to a web context, we also considered evaluating the recall to study the behavior of our model from different aspects. This choice led us to handle a different problem related to evaluating the recall in information retrieval. After realizing that actual measures don't satisfy our constraints, we proposed a new recall oriented measure (MOR) which considers the recall as a priority without ignoring the precision.Among other measures, MOR was considered to evaluate our approach ASMER on four web collection from the standard evaluation campaigns Inex and Trec. Our experiments showed that ASMER improves the precision of the non modified original queries. In most cases, our approach achieved statistically significant enhancements when compared to a state of the art query expansion method. In addition, ASMER retrieves the first relevant document in better ranks than the compared approaches, it also has slightly better recall according to the measure MOR.

Cette thèse porte sur la mise en place d'un système de requêtage sur des flux sous contraintes de capacités. Ce système est porté par ses utilisateurs-trices et basé sur les similitudes entre requêtes. Les relations d'équivalences entre les différentes requêtes permettent de réunir les participants au sein de communautés d'intérêt. Celles-ci forment alors une abstraction permettant de séparer le problème d'organisation du système en plusieurs sous-problèmes plus simples et de taille réduite. Afin de garantir une généricité vis-à-vis du langage, l'organisation repose sur une API simple et modulable. Nous avons ainsi recours au mécanisme de réécritures de requêtes utilisant des vues matérialisées, connu en bases de données, pour déterminer les relations possibles entre les communautés. Le choix entre ces différentes possibilités est ensuite effectué à l'aide d'un modèle de coût paramétrable. Les relations entre communautés sont concrétisées par un échange de ressources entre elles, un participant de l'une venant contribuer à l'autre. Cela permet de s'affranchir des limitations de capacités au niveau abstrait, tout en en tenant hautement compte pour la mise en relation effective des participants. Au sein des communautés, un arbre de diffusion permet à l'ensemble des participants de récupérer les résultats requis. L'approche, mise en œuvre de manière incrémentale, permet une réduction efficace des coûts de calcul et de diffusion (l'optimalité est atteinte, notamment, dans le cas de l'inclusion de requête) pour un coût d'organisation limité et une latence raisonnable. Les expérimentations réalisées ont montré une grande adaptabilité aux variations concernant les requêtes exprimées et les capacités des participants. Le démonstrateur mis en place peut être utilisé à la fois pour des simulations (automatiques ou interactives) et pour un déploiement réel, par une implémentation commune générique vis-à-vis du langage. / This thesis addresses the problem of the organization of querying system on data streams under capacity constraints, such system being user-powered and based on the queries' similarity. Equivalence relations between queries allow to group the participants into communities. Those communities are then used as an abstraction to split the general organization problem into several easier and smaller subproblems. In order to stay language-independent, the organization is based on a simple and modular API, that rely on a query answering using views mechanism, well known in databases. Choice between the different rewritten queries is done using an adjustable cost model. Relations between communities are thus materialized by a spreading mechanism, a participant from one community joining the other(s) to contribute. This allows to avoid the capacities problem on the organization's abstract level, while efficiently taking care of it on the concrete one. Inside the communities, all the participants receive the common results they need using a spanning tree. The QTor approach, incrementally built, allows an efficient reduce of the processing and diffusion costs (processing cost being optimal in some cases, e.g. containment) with a reasonable latency, for a limited organization cost. Experiments have shown that the organization is flexible, regarding both the expressed queries and the participants' capacities. A demonstrator was built, allowing to both perform (automatic or interactive) simulations, and deploy the system over a real network, with a single.

Le traitement de flux de données est au cœur des problématiques actuelles liées au Big Data. Face à de grandes quantités de données (Volume) accessibles de manière éphémère (Vélocité), des solutions spécifiques tels que les systèmes de gestion de flux de données (SGFD) ont été développés. Ces SGFD reçoivent des flux et des requêtes continues pour générer de nouveaux résultats aussi longtemps que des données arrivent en entrée. Dans le contexte de cette thèse, qui s’est réalisée dans le cadre du projet ANR Socioplug (ANR-13-INFR-0003), nous considérons une plateforme collaborative de traitement de flux de données à débit variant en termes de volume et de distribution des valeurs. Chaque utilisateur peut soumettre des requêtes continues et contribue aux ressources de traitement de la plateforme. Cependant, chaque unité de traitement traitant les requêtes dispose de ressources limitées ce qui peut engendrer la congestion du système en fonction des variations des flux en entrée. Le problème est alors de savoir comment adapter dynamiquement les ressources utilisées par chaque requête continue par rapport aux besoins de traitement. Cela soulève plusieurs défis : i) comment détecter un besoin de reconfiguration ? ii) quand reconfigurer le système pour éviter sa congestion ? Durant ces travaux de thèse, nous nous sommes intéressés à la gestion automatique de la parallélisation des opérateurs composant une requête continue. Nous proposons une approche originale basée sur une estimation des besoins de traitement dans un futur proche. Ainsi, nous pouvons adapter le niveau de parallélisme des opérateurs de manière proactive afin d’ajuster les ressources utilisées aux besoins des traitements. Nous montrons qu’il est possible d’éviter la congestion du système mais également de réduire significativement la consommation de ressources à performance équivalente. Ces différents travaux ont été implémentés et validés dans un SGFD largement utilisé avec différents jeux de tests reproductibles. / In a Big Data context, stream processing has become a very active research domain. In order to manage ephemeral data (Velocity) arriving at important rates (Volume), some specific solutions, denoted data stream management systems (DSMSs),have been developed. DSMSs take as inputs some queries, called continuous queries,defined on a set of data streams. Acontinuous query generates new results as long as new data arrive in input. In many application domains, data streams haveinput rates and distribution of values which change over time. These variations may impact significantly processingrequirements for each continuous query.This thesis takes place in the ANR project Socioplug (ANR-13-INFR-0003). In this context, we consider a collaborative platformfor stream processing. Each user can submit multiple continuous queries and contributes to the execution support of theplatform. However, as each processing unit supporting treatments has limited resources in terms of CPU and memory, asignificant increase in input rate may cause the congestion of the system. The problem is then how to adjust dynamicallyresource usage to processing requirements for each continuous query ? It raises several challenges : i) how to detect a need ofreconfiguration ? ii) when reconfiguring the system to avoid its congestion at runtime ?In this work, we are interested by the different processing steps involved in the treatment of a continuous query over adistributed infrastructure. From this global analysis, we extract mechanisms enabling dynamic adaptation of resource usage foreach continuous query. We focus on automatic parallelization, or auto-parallelization, of operators composing the executionplan of a continuous query. We suggest an original approach based on the monitoring of operators and an estimation ofprocessing requirements in near future. Thus, we can increase (scale-out), or decrease (scale-in) the parallelism degree ofoperators in a proactive many such as resource usage fits to processing requirements dynamically. Compared to a staticconfiguration defined by an expert, we show that it is possible to avoid the congestion of the system in many cases or to delay itin most critical cases. Moreover, we show that resource usage can be reduced significantly while delivering equivalentthroughput and result quality. We suggest also to combine this approach with complementary mechanisms for dynamic adaptation of continuous queries at runtime. These differents approaches have been implemented within a widely used DSMS and have been tested over multiple and reproductible micro-benchmarks.

L’article 493 du Code de procédure civile définit l’ordonnance sur requête comme une « décision provisoire rendue non contradictoirement dans les cas où le requérant est fondé à ne pas appeler de partie adverse ». Proche, dans sa nature, de l’ordonnance de référé, elle s’en démarque par son aspect unilatéral, qui en conditionne l’efficacité. L’ordonnance sur requête est au cœur de nombreuses controverses, d’une part sur sa qualification, d’autre part sur l’autorité dont elle doit être revêtue. Ces incertitudes rendent inconstant le régime des ordonnances sur requête, dont l’application varie fortement selon les juridictions. La notion de provisoire, combinée à la considération du caractère unilatéral de la procédure, doit servir de guide pour lever ces doutes. L’analyse de l’ordonnance sur requête sous ce prisme aboutit à la conclusion que l’ordonnance sur requête est une mesure procédurale d’attente, provisoire en ce qu’elle permet de préparer l’intervention du juge du principal sans le lier dans la sa décision. / The 493rd article of the french code of civil proceedings defines the injunction on demand as a “provisional decision taken unilaterally when there is no need to call the opposing party”. While close by its nature to the refere injunction, the injunction on demand is specific by its unilaterral side that marks its efficiency as a procedure. Numerous questions remain to this day unsolved regarding both its legal definition and its significance.These controversies make the daily use of the injunction on demand vary wildly according to every court. The concept of provisional decision, as well as the unilaterral side of this specific injunction, can serve as a guide to finding a satisfying solution. The research leads to the conclusion that the injunction ondemand is provisional in the sense that its role is to preserve the rights of the parties involved in order to prepare the definitive decision taken by the court, on which the injunction has no legal influence.

Les services Web proposent un paradigme intéressant pour la publication, la découverte et la consommation de services. Ce sont des applications faiblement couplées qui peuvent être exécutées seules ou être composées pour créer de nouveaux services à valeur ajoutée. Ils peuvent être consommés comme des services individuels qui fournissent une interface unique qui reçoit des inputs et retourne des outputs (cas 1), ou bien ils peuvent être consommés en tant que composants à intégrer dans des procédés métier (cas 2). Nous appelons le premier cas de consommation « utilisation individuelle » et le second cas de consommation « utilisation en procédé métier ». La nécessité d'avoir des outils dédiés pour aider les consommateurs dans les deux cas de consommation a impliqué de nombreux travaux de recherche dans les milieux académiques ou industriels. D'une part, beaucoup de portails et de moteurs de recherche de services ont été développés pour aider les utilisateurs à rechercher et invoquer les services Web pour une utilisation individuelle. Cependant, les approches actuelles prennent principalement en compte les connaissances explicites présentées par les descriptions de service. Ils font des recommandations sans tenir compte des données qui reflètent l'intérêt des utilisateurs et peuvent demander des informations supplémentaires aux utilisateurs. D'autre part, plusieurs techniques et mécanismes associées aux procédés métier ont été élaborés pour rechercher des modèles de procédé métiers similaires, ou utiliser des modèles de référence. Ces mécanismes sont utilisés pour assister les analystes métiers à la conception de procédés métiers. Cependant, ils sont lents, source d'erreurs, grands consommateurs de ressources humaines, et peuvent induire à l’erreur les analystes métier. Dans notre travail, nous cherchons à faciliter la consommation de services Web pour une utilisation individuelle ou en procédé métier en proposant des techniques de recommandation. Notre objectif est de recommander aux utilisateurs des services qui sont proches de leur intérêt et de recommander aux analystes métier des services qui sont pertinents pour un procédé métier en cours de conception. Pour recommander des services pour une utilisation individuelle, nous prenons en compte l’historique des données d'utilisation de l'utilisateur qui reflètent ses intérêts. Nous appliquons des techniques de filtrage collaboratif bien connues pour faire des recommandations. Nous avons proposé cinq algorithmes et développé une application Web qui permet aux utilisateurs d'utiliser des services recommandés. Pour recommander des services pour une utilisation en procédé métier, nous prenons en compte les relations entre les services du procédé métier. Nous proposons de recommander les services en fonction de leurs localisations dans le procédé métier. Nous avons définit le contexte de voisinage d'un service. Nous avons présenté des recommandations basées sur l'appariement de contexte de voisinage. Par ailleurs, nous avons développé un langage de requête pour permettre aux analystes métier d'exprimer formellement des contraintes de filtrage. Nous avons proposé également une approche pour extraire le contexte de voisinage à partir de traces d’exécution de procédés métier. Enfin, nous avons développé trois applications afin de valider notre approche. Nous avons effectué des expérimentations sur des données recueillies par nos applications et sur deux grands ensembles de données publiques. Les résultats expérimentaux montrent que notre approche est faisable, précise et performante dans des cas d'utilisation réels / Web services have been developed as an attractive paradigm for publishing, discovering and consuming services. They are loosely-coupled applications that can be run alone or be composed to create new value-added services. They can be consumed as individual services which provide a unique interface to receive inputs and return outputs; or they can be consumed as components to be integrated into business processes. We call the first consumption case individual use and the second case business process use. The requirement of specific tools to assist consumers in the two service consumption cases involves many researches in both academics and industry. On the one hand, many service portals and service crawlers have been developed as specific tools to assist users to search and invoke Web services for individual use. However, current approaches take mainly into account explicit knowledge presented by service descriptions. They make recommendations without considering data that reflect user interest and may require additional information from users. On the other hand, some business process mechanisms to search for similar business process models or to use reference models have been developed. These mechanisms are used to assist process analysts to facilitate business process design. However, they are labor-intense, error-prone, time-consuming, and may make business analyst confused. In our work, we aim at facilitating the service consumption for individual use and business process use using recommendation techniques. We target to recommend users services that are close to their interest and to recommend business analysts services that are relevant to an ongoing designed business process. To recommend services for individual use, we take into account the user's usage data which reflect the user's interest. We apply well-known collaborative filtering techniques which are developed for making recommendations. We propose five algorithms and develop a web-based application that allows users to use services. To recommend services for business process use, we take into account the relations between services in business processes. We target to recommend relevant services to selected positions in a business process. We define the neighborhood context of a service. We make recommendations based on the neighborhood context matching. Besides, we develop a query language to allow business analysts to formally express constraints to filter services. We also propose an approach to extract the service's neighborhood context from business process logs. Finally, we develop three applications to validate our approach. We perform experiments on the data collected by our applications and on two large public datasets. Experimental results show that our approach is feasible, accurate and has good performance in real use-cases

Les systèmes d'information font face à un problème de pertinence dans les recherches dû à l'augmentation considérable des données accessibles. De plus, le nombre d'appareils communicants ne cesse de croître et de menacer le modèle client/serveur. Une nouvelle architecture distribuée tend donc à s'imposer : les réseaux pair-à-pair (P2P). Mais ils sont peu économes en ressource réseau (une requête inonde le réseau) et offrent des fonctionnalités limitées (recherche par mots-clés). Dans les deux communautés, RI et systèmes P2P, les recherches penchent vers l'utilisation de sémantique. En informatique, les approches basées sur la sémantique nécessitent souvent de définir des ontologies. Le développement important et distribué des ontologies génère une hétérogénéité sémantique. La solution classique est d'utiliser des correspondances entre parties de deux ontologies. Mais c'est une solution qui est difficile à obtenir et qui n'est pas toujours complète. Souvent les parties non-partagées de deux ontologies ne sont pas gérées, ce qui entraîne une perte d'information. Notre solution : EXSI2D, utilise une expansion particulière, appelée expansion structurante, du côté de l'initiateur de requêtes. Cela lui permet de préciser les dimensions de sa requête sans modifier la requête elle-même. EXSI2D offre aussi la possibilité au fournisseur d'information d'interpréter l'expansion structurante dans sa propre ontologie. Ainsi, il est possible à chaque participant d'un système d'information sémantiquement hétérogène d'utiliser toute son ontologie, y compris les parties non partagées. Nous montrons aussi l'utilisation d'EXSI2D dans un système P2P, grâce à SPARTANBFS, un protocole « frugal » pour systèmes P2P non structurés.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Les systèmes de recherche d’information utilisent généralement une multitude de fonctionnalités pour classer les documents. Néanmoins, un élément reste essentiel pour le classement, qui est les modèles standards de recherche d’information.Cette thèse aborde une limitation fondamentale des modèles de recherche d’information, à savoir le problème de la disparité des termes <Term Mismatch Problem>. Le problème de la disparité des termes est un problème de longue date dans la recherche d'informations. Cependant, le problème de la récurrence de la disparité des termes n'a pas bien été défini dans la recherche d'information, son importance, et à quel point cela affecterai les résultats de la recherche. Cette thèse tente de répondre aux problèmes présentés ci-dessus.Nos travaux de recherche sont rendus possibles par la définition formelle de la probabilité de la disparité des termes. Dans cette thèse, la disparité des termes est définie comme étant la probabilité d'un terme ne figurant pas dans un document pertinent pour la requête. De ce fait, cette thèse propose des approches pour réduire la probabilité de la disparité des termes. De plus, nous confortons nos proposions par une analyse quantitative de la probabilité de la disparité des termes qui décrit de quelle manière les approches proposées permettent de réduire la probabilité de la disparité des termes tout en conservant les performances du système.Au première niveau, à savoir le document, nous proposons une approche de modification des documents en fonction de la requête de l'utilisateur. Il s'agit de traiter les termes de la requête qui n'apparaissent pas dans le document. Le modèle de document modifié est ensuite utilisé dans un modèle standard de recherche afin d'obtenir un modèle permettant de traiter explicitement la disparité des termes.Au second niveau, à savoir la requête, nous avons proposé deux majeures contributions.Premièrement, nous proposons une approche d'expansion de requête sémantique basée sur une ressource collaborative. Nous concentrons plutôt sur la structure de ressources collaboratives afin d'obtenir des termes d'expansion intéressants qui contribuent à réduire la probabilité de la disparité des termes, et par conséquent, d'améliorer la qualité de la recherche.Deuxièmement, nous proposons un modèle d'expansion de requête basé sur les modèles de langue neuronaux. Les modèles de langue neuronaux sont proposés pour apprendre les représentations vectorielles des termes dans un espace latent, appelées <Distributed Neural Embeddings>. Ces représentations vectorielles s'appuient sur les relations entre les termes permettant ainsi d'obtenir des résultats impressionnants en comparaison avec l'état de l'art dans les taches de similarité de termes. Cependant, nous proposons d'utiliser ces représentations vectorielles comme une ressource qui définit les relations entre les termes.Nous adaptons la définition de la probabilité de la disparité des termes pour chaque contribution ci-dessus. Nous décrivons comment nous utilisons des corpus standard avec des requêtes et des jugements de pertinence pour estimer la probabilité de la disparité des termes. Premièrement, nous estimons la probabilité de la disparité des termes à l'aide les documents et les requêtes originaux. Ainsi, nous présentons les différents cas de la disparité des termes clairement identifiée dans les systèmes de recherche pour les différents types de termes d'indexation. Ensuite, nous indiquons comment nos contributions réduisent la probabilité de la disparité des termes estimée et améliorent le rappel du système.Des directions de recherche prometteuses sont identifiées dans le domaine de la disparité des termes qui pourrait présenter éventuellement un impact significatif sur l'amélioration des scénarios de la recherche. / Even though modern retrieval systems typically use a multitude of features to rank documents, the backbone for search ranking is usually the standard retrieval models.This thesis addresses a limitation of the standard retrieval models, the term mismatch problem. The term mismatch problem is a long standing problem in information retrieval. However, it was not well understood how often term mismatch happens in retrieval, how important it is for retrieval, or how it affects retrieval performance. This thesis answers the above questions.This research is enabled by the formal definition of term mismatch. In this thesis, term mismatch is defined as the probability that a term does not appear in a document given that this document is relevant. We propose several approaches for reducing term mismatch probability through modifying documents or queries. Our proposals are then followed by a quantitative analysis of term mismatch probability that shows how much the proposed approaches reduce term mismatch probability with maintaining the system performance. An essential component for achieving term mismatch probability reduction is the knowledge resource that defines terms and their relationships.First, we propose a document modification approach according to a user query. The main idea of our document modification approach is to deal with mismatched query terms. While prior research on document enrichment provides a static approach for document modification, we are concerned to only modify the document in case of mismatch. The modified document is then used in a standard retrieval model in order to obtain a mismatch aware retrieval model.Second, we propose a semantic query expansion approach based on a collaborative knowledge resource. We focus on the collaborative resource structure to obtain interesting expansion terms that contribute to reduce term mismatch probability, and as a result, improve the effectiveness of search.Third, we propose a query expansion approach based on neural language models. Neural language models are proposed to learn term vector representations, called distributed neural embeddings. Distributed neural embeddings capture relationships between terms, and they obtained impressive results comparing with state of the art approaches in term similarity tasks. However, in information retrieval, distributed neural embeddings are newly started to be exploited. We propose to use distributed neural embeddings as a knowledge resource in a query expansion scenario.Fourth, we apply the term mismatch probability definition for each contribution of the above contributions. We show how we use standard retrieval corpora with queries and relevance judgments to estimate the term mismatch probability. We estimate the term mismatch probability using original documents and queries, and we figure out how mismatch problem is clearly found in search systems for different types of indexing terms. Then, we point out how much our contributions reduce the estimated mismatch probability, and improve the system recall. As a result, we present how the modified document and query representations contribute to build a mismatch aware retrieval model that mitigate term mismatch problem theoretically and practically.This dissertation shows the effectiveness of our proposals to improve retrieval performance. Our experiments are conducted on corpora from two different domains: medical domain and cultural heritage domain. Moreover, we use two different types of indexing terms for representing documents and queries: words and concepts, and we exploit several types of relationships between indexing terms: hierarchical relationships, relationships based on a collaborative resource structure, relationships defined on distributed neural embeddings.Promising research directions are identified where the term mismatch research may make a significance impact on improving the search scenarios.

L'objet de notre étude est la requête adressée à un moteur de recherche Web par un usager dans le cadre d'une recherche d'information. Nous souhaitons mieux comprendre l'étape de la recherche d'information située entre le besoin d'information et la formulation / reformulation de la requête. Notre thèse est articulée autour de deux hypothèses de recherche. D'abord, nous avons émis l'hypothèse qu'une requête adressée à un moteur de recherche Web peut receler de l'implicite. Ensuite, nous avons considéré que ce contenu implicite peut être utilisé par les usagers dans des tactiques de formulation / reformulation de la requête. Nous avons notamment analysé le discours de 61 étudiants que nous avons interrogés sur leur intention de recherche. Ce discours était principalement constitué d'un niveau sémantique (qui décrit le thème de la recherche) et d'un niveau pragmatique (composé d'un but seul ou d'un but ou plusieurs sous-but(s)). Les termes représentant le niveau sémantique pouvaient être complètement ou partiellement formulés dans la requête, mais ceux représentant le niveau pragmatique n'étaient généralement pas formulés. Cette situation de communication s'apparente à une négociation entre le moteur de recherche et l'usager. Le moteur de recherche tente de disposer d'éléments sur le besoin d'information de l'usager et ce dernier tente d'obtenir à partir d'un contenu explicitement formulé dans sa requête, un ensemble d'information afin de progresser sur la résolution de son problème / The object of our study is the query, sent to a Web search engine, by an Internet user. We aim to reach a better understanding of the phase of information seeking located between the information need and the query formulation. Our thesis is based on two core hypotheses, all related to the query. Firstly, we considered that the query expressed partially the user’s information need and therefore contain an implicit part. Secondly, we also considered that the implicit part can be used by the users in their query formulation tactics. We notably analyzed 61 students’ speech about their search intent. The speech was based mainly on a semantic level (the terms representing the topic of the research) and a pragmatic level (composed of an only purpose or purpose and of many under purposes). The terms representing the semantic level could be rather completely or partially formulated in the query but those representing the pragmatic level weren’t formulated. This situation of communication is similar to a negotiation between the Web search engine and the user. The search engine Web tries to have elements on user’s information need and the user tries to obtain, from a contents explicitly formulated in his query, a set of information in order to progress on his resolution of its problem

La quantité croissante des données s’accompagne par l’augmentation du nombre de programmes de transformation de données, généralement des requêtes, et par la nécessité d’analyser et comprendre leurs résultats : (a) pourquoi telle réponse figure dans le résultat ? ou (b) pourquoi telle information n’y figure pas ? La première question demande de trouver l’origine ou la provenance des résultats dans la base, un problème très étudié depuis une 20taine d’années. Par contre, expliquer l’absence de réponses dans le résultat d’une requête est un problème peu exploré jusqu’à présent. Répondre à une question Pourquoi-Pas consiste à fournir des explications quant à l’absence de réponses. Ces explications identifient pourquoi et comment les données pertinentes aux réponses manquantes sont absentes ou éliminées par la requête. Notre travail suppose que la base de données n’est pas source d’erreur et donc cherche à fournir des explications fondées sur (les opérateurs de) la requête qui peut alors être raffinée ultérieurement en modifiant les opérateurs "fautifs". Cette thèse développe des outils formels et algorithmiques destinés au débogage et à la réparation de requêtes SQL afin de traiter des questions de type Pourquoi-Pas. Notre première contribution, inspirée par une étude critique de l’état de l’art, utilise un arbre de requête pour rechercher les opérateurs "fautifs". Elle permet de considérer une classe de requêtes incluant SPJA, l’union et l’agrégation. L’algorithme NedExplain développé dans ce cadre, a été validé formellement et expérimentalement. Il produit des explications de meilleure qualité tout en étant plus efficace que l’état de l’art.L’approche précédente s’avère toutefois sensible au choix de l’arbre de requête utilisé pour rechercher les explications. Notre deuxième contribution réside en la proposition d’une notion plus générale d’explication sous forme de polynôme qui capture toutes les combinaisons de conditions devant être modifiées pour que les réponses manquantes apparaissent dans le résultat. Cette méthode s’applique à la classe des requêtes conjonctives avec inégalités. Sur la base d’un premier algorithme naïf, Ted, ne passant pas à l’échelle, un deuxième algorithme, Ted++, a été soigneusement conçu pour éliminer entre autre les calculs itérés de sous-requêtes incluant des produits cartésien. Comme pour la première approche, une évaluation expérimentale a prouvé la qualité et l’efficacité de Ted++. Concernant la réparation des requêtes, notre contribution réside dans l’exploitation des explications polynômes pour guider les modifications de la requête initiale ce qui permet la génération de raffinements plus pertinents. La réparation des jointures "fautives" est traitée de manière originale par des jointures externes. L’ensemble des techniques de réparation est mis en oeuvre dans FixTed et permet ainsi une étude de performance et une étude comparative. Enfin, Ted++ et FixTed ont été assemblés dans une plate-forme pour le débogage et la réparation de requêtes relationnelles. / With the increasing amount of available data and data transformations, typically specified by queries, the need to understand them also increases. “Why are there medicine books in my sales report?” or “Why are there not any database books?” For the first question we need to find the origins or provenance of the result tuples in the source data. However, reasoning about missing query results, specified by Why-Not questions as the latter previously mentioned, has not till recently receivedthe attention it is worth of. Why-Not questions can be answered by providing explanations for the missing tuples. These explanations identify why and how data pertinent to the missing tuples were not properly combined by the query. Essentially, the causes lie either in the input data (e.g., erroneous or incomplete data) or at the query level (e.g., a query operator like join). Assuming that the source data contain all the necessary relevant information, we can identify the responsible query operators formingquery-based explanations. This information can then be used to propose query refinements modifying the responsible operators of the initial query such that the refined query result contains the expected data. This thesis proposes a framework targeted towards SQL query debugging and fixing to recover missing query results based on query-based explanations and query refinements.Our contribution to query debugging consist in two different approaches. The first one is a tree-based approach. First, we provide the formal framework around Why-Not questions, missing from the state-of-the-art. Then, we review in detail the state-of-the-art, showing how it probably leads to inaccurate explanations or fails to provide an explanation. We further propose the NedExplain algorithm that computes correct explanations for SPJA queries and unions there of, thus considering more operators (aggregation) than the state of the art. Finally, we experimentally show that NedExplain is better than the both in terms of time performance and explanation quality. However, we show that the previous approach leads to explanations that differ for equivalent query trees, thus providing incomplete information about what is wrong with the query. We address this issue by introducing a more general notion of explanations, using polynomials. The polynomial captures all the combinations in which the query conditions should be fixed in order for the missing tuples to appear in the result. This method is targeted towards conjunctive queries with inequalities. We further propose two algorithms, Ted that naively interprets the definitions for polynomial explanations and the optimized Ted++. We show that Ted does not scale well w.r.t. the size of the database. On the other hand, Ted++ is capable ii of efficiently computing the polynomial, relying on schema and data partitioning and advantageous replacement of expensive database evaluations by mathematical calculations. Finally, we experimentally evaluate the quality of the polynomial explanations and the efficiency of Ted++, including a comparative evaluation.For query fixing we propose is a new approach for refining a query by leveraging polynomial explanations. Based on the input data we propose how to change the query conditions pinpointed by the explanations by adjusting the constant values of the selection conditions. In case of joins, we introduce a novel type of query refinements using outer joins. We further devise the techniques to compute query refinements in the FixTed algorithm, and discuss how our method has the potential to be more efficient and effective than the related work.Finally, we have implemented both Ted++ and FixTed in an system prototype. The query debugging and fixing platform, short EFQ allows users to nteractively debug and fix their queries when having Why- Not questions.