Tesi sul tema "Théorie des bases de données"
Segui questo link per vedere altri tipi di pubblicazioni sul tema: Théorie des bases de données.
Cita una fonte nei formati APA, MLA, Chicago, Harvard e in molti altri stili
Vedi i top-50 saggi (tesi di laurea o di dottorato) per l'attività di ricerca sul tema "Théorie des bases de données".
Accanto a ogni fonte nell'elenco di riferimenti c'è un pulsante "Aggiungi alla bibliografia". Premilo e genereremo automaticamente la citazione bibliografica dell'opera scelta nello stile citazionale di cui hai bisogno: APA, MLA, Harvard, Chicago, Vancouver ecc.
Puoi anche scaricare il testo completo della pubblicazione scientifica nel formato .pdf e leggere online l'abstract (il sommario) dell'opera se è presente nei metadati.
Vedi le tesi di molte aree scientifiche e compila una bibliografia corretta.
1
Ripoche, Hugues. "Une construction interactive d'interprétations de données : application aux bases de données de séquences génétiques". Montpellier 2, 1995. http://www.theses.fr/1995MON20248.
Abstract (sommario):
L'objectif de cette these est de faciliter l'interpretation de grands ensembles de donnees, c'est-a-dire d'extraire des connaissances a partir de donnees. Nous avons utilise deux domaines complementaires: bases de donnees (objet) et apprentissage automatique. Dans une premiere etape, nous proposons d'extraire des descripteurs a partir d'ensembles de donnees de reference, puis d'utiliser ces descripteurs pour interpreter de nouvelles donnees (non encore caracterisees). Dans une seconde etape, une classification construite a partir de donnees interpretees par des descripteurs peut etre critiquee par une methode d'analyse specifique, ce qui conduit en retour a une revision des donnees et des descripteurs. Une application a ete menee dans le cadre de l'analyse de sequences genetiques (proteines) en utilisant des motifs proteiques comme descripteurs, des treillis de concept comme methode de classification et l'alignement multiple de sequences pour la critique
2
Stamate, Daniel. "Applications des logiques multivaluées aux bases de données avec informations incertaines". Paris 11, 1999. http://www.theses.fr/1999PA112374.
Abstract (sommario):
La thèse propose une approche de bases de données déductives avec informations incertaines qui se base sur le formalisme des logiques multivaluées. Dans la première partie du document, en considérant une logique à cinq valeurs, nous décrivons la sémantique stable multivaluée des bases de données déductives et de leurs mises à jour. L'approche consiste dans des mises à jours déterministes, qui concernent les prédicats extensionnels (comme dans les approches usuelles) mais aussi les prédicats intentionnels. Nous montrons l'existence de bonnes propriétés des mises à jour comme l'idempotence, la réversibilité, la monotonie par rapport au degré de connaissance et la monotonie par rapport au degré de vérité dans les bases avec des règles sans négation. Dans la deuxième partie de la thèse nous introduisons un cadre logique pour décrire et imposer de manière automatique des contraintes sur des bases de données avec des informations incertaines, au cours des mises à jour. Il existe une variété émergente d'applications pour lesquelles l'application automatique des contraintes est plus appropriée que dans l'approche classique (selon laquelle les mises à jour sont rejetées en cas d'inconsistance). Dans ce cadre nous proposons et traitons le problème suivant : quel type de contraintes permet d'effectuer les mises à jour sur l'état de la base de données de manière déterministe, sous des suppositions raisonnables dont fait partie celle du changement minimal. Les résultats principaux de cette partie concernent la caractérisation des ensembles de contraintes déterministes. En ce qui concerne l'optimisation des requêtes, un problème important est l'inclusion des requêtes. Dans la troisième partie de la thèse nous avons considéré et étudié le problème de l'inclusion des requêtes dans le contexte des informations incertaines.
3
Acosta, Francisco. "Les arbres balances : spécification, performances et contrôle de concurrence". Montpellier 2, 1991. http://www.theses.fr/1991MON20201.
Abstract (sommario):
Dans le cadre de la gestion d'une base de donnees, nous etudions les problemes relatifs a la specification, aux performances des operations d'acces et au partage des donnees. Dans la premiere partie de l'etude nous introduisons les notions de base pour la specification de donnees et nous etudions les methodes classiques d'acces aux donnees; cette etude montre que les arbres balances (les b-arbres et leurs variations) sont une solution interessante pour la gestion de donnees stockees sur disque. Nous etudions ensuite la specification algebrique des arbres balances, afin de degager leurs caracteristiques intrinseques. Nous definissons les classes b(k, m) des b-arbres, dans lesquelles les parametres k et m permettent de controler de facon simple le rapport espace-temps de leur complexite. Cette proposition generalise, a l'aide du parametre k, les variations les plus classiques de ces arbres, telles que les arbres b*. Dans la seconde partie de l'etude, nous exposons les concepts de base du controle de concurrence. Nous etudions par la suite le modele d'execution concurrente sur les arbres de recherche de shasha et goodman, puis les methodes de controle de concurrence pour ces arbres. Finalement, nous degageons les principes d'une methode originale dans laquelle le controle s'exerce au meilleur moment de l'execution des operations
4
Magnier, Nicolas. "Validation des transactions dans les bases de données : classes décidables et vérification automatique". Bordeaux 1, 1998. http://www.theses.fr/1998BOR10506.
Abstract (sommario):
Dans cette these, on introduit un modele de donnees relationnel pour etudier le probleme de valider des transactions. Dans notre contexte, valider une transaction c'est demontrer qu'elle preserve la coherence par rapport a une specification statique, et au premier ordre, de l'integrite des bases de donnees. Nous avons defini et implante un systeme, base sur une extension de la construction de plus faible precondition, pour valider des transactions de ce modele de facon automatique. La principale originalite de ce modele reside dans son langage de transactions. Il permet en effet d'exprimer des mises a jours de domaine de bases de donnees. En plus de leur interet pour definir simplement les transformations de graphes, nous avons montre qu'elles permettent d'exprimer simplement des creations ou des suppressions d'objets dans des modeles semantiques. L'autre contribution de ce travail est la mise en evidence de quatre nouvelles classes decidables du probleme de preservation dans le cadre de notre modele relationnel. Aucune de ces classes n'est incluse dans l'une des autres. En particulier, une de ces classes generalise la classe mise en evidence par abiteboul et vianu. De plus, nous avons montre que la presence de transactions qui peuvent modifier le domaine affecte peu la decidabilite du probleme. En effet, toutes les classes que nous avons etablies contiennent ce type de transactions. De plus, on montre que notre systeme de validation experimental decide (en particulier) toutes ces classes. Cette propriete est un atout majeur par rapport aux systemes existants. En effet, dans les systemes proposes, aucune caracterisation de ce type n'est etablie.
5
Lerat, Nadine. "Représentation et traitement des valeurs nulles dans les bases de données". Paris 11, 1986. http://www.theses.fr/1986PA112383.
Abstract (sommario):
Cette thèse étudie la représentation et le traitement de deux types d'informations incomplètes dans le contexte des bases de données : les valeurs nulles non applicables et les valeurs nulles représentant des objets inconnus. Dans une première partie, les requêtes portant sur une table unique contenant des valeurs non applicables sont traduites par un ensemble de requêtes sur des multitables conventionnelles. Dans une seconde partie, les valeurs nulles inconnues sont représentées par des constantes de Skolem et une méthode adaptant à ce contexte un algorithme de "chasse" permet d'évaluer des requêtes en présence de dépendances fonctionnelles ou d'inclusion. Des techniques efficaces d'évaluation sont proposées. On montre, en conclusion, que les deux types de valeurs nulles ci-dessus peuvent être pris en compte simultanémentThis thesis deals with the representation and treatment of two cases of information incompleteness in the field of databases: non applicable null values and null values representing unknown objects. In the first part, queries on a unique table containing non applicable nulls are translated into a set of queries on conventional multitables. In the second part, unknown null values are represented by Skolem constants and a method adapting to this context a "chase" algorithm allows evaluating queries when functional or inclusion dependencies are satisfied. Eventually, it is shown that these two types of null values can be taken into account simultaneously
6
Fansi, Janvier. "Sécurité des bases de données XML (eXtensible Markup Language)". Pau, 2007. http://www.theses.fr/2007PAUU3007.
Abstract (sommario):
XML est devenu le standard de représentation et d'échange de données sur Internet. Puisque Internet est un réseau public, les entreprises et organismes qui se servent de XML ont besoin de mécanismes de protection des données XML contre les accès non autorisés. C'est ainsi que plusieurs travaux se sont intéressés à la protection de XML. Ceux-ci peuvent être classés en deux grandes catégories, à savoir celles qui procèdent par matérialisation des vues et celles qui opèrent par réécriture des requêtes. Dans cette thèse, nous montrons les limites des approches qui procèdent par matérialisation des vues à travers le développement d'un prototype de base de données XML basé sur l'une de ces approches. Par la suite, nous proposons une technique de protection des documents XML par réécriture des requêtes. Nous prouvons sa correction et montrons qu'elle est plus efficace que les approches concurrentes. Enfin, nous étendons notre proposition afin de prendre en compte le contrôle des accès en écriture aux bases de données XMLXML has emerged as the de facto standard for representing and exchanging information on the Internet. As Internet is a public network, corporations and organizations which use XML need mechanisms to protect XML data against unauthorised access. Thus, several schemes for XML access control have been proposed. They can be classified in two major categories: views materialization and queries rewriting techniques. In this thesis, we point out the drawbacks of views materialization approaches through the development of a prototype of secured XML database based on one of those approaches. Afterwards, we propose a technique aimed at securing XML by means of queries rewriting. We prove its correctness and show that it is more efficient than competing works. Finally, we extend our proposal in order to controlling the updating of XML databases
7
Casali, Alain. "Treillis cubes contraints et fermés dans la fouille de bases de données multidimensionnelles". Aix-Marseille 2, 2004. http://www.theses.fr/2004AIX22078.
8
Slimane, Mohammed. "Le langage des gractes et son usage fondamental en algèbre en logique et dans la théorie des bases de données relationnelles". Paris 5, 1986. http://www.theses.fr/1986PA05S008.
9
D'Ambrosio, Roberto. "Classification de bases de données déséquilibrées par des règles de décomposition". Thesis, Nice, 2014. http://www.theses.fr/2014NICE4007/document.
Abstract (sommario):
Le déséquilibre entre la distribution des a priori est rencontré dans un nombre très large de domaines. Les algorithmes d’apprentissage conventionnels sont moins efficaces dans la prévision d’échantillons appartenant aux classes minoritaires. Notre but est de développer une règle de reconstruction adaptée aux catégories de données biaisées. Nous proposons une nouvelle règle, la Reconstruction Rule par sélection, qui, dans le schéma ‘One-per-Class’, utilise la fiabilité, des étiquettes et des distributions a priori pour permettre de calculer une décision finale. Les tests démontrent que la performance du système s’améliore en utilisant cette règle plutôt que des règles classiques. Nous étudions également les règles dans l’ ‘Error Correcting Output Code’ (ECOC) décomposition. Inspiré par une règle de reconstitution de données statistiques conçue pour le ‘One-per-Class’ et ‘Pair-Wise Coupling’ des approches sur la décomposition, nous avons développé une règle qui s’applique à la régression ‘softmax’ sur la fiabilité afin d’évaluer la classification finale. Les résultats montrent que ce choix améliore les performances avec respect de la règle statistique existante et des règles de reconstructions classiques. Sur ce thème d’estimation fiable nous remarquons que peu de travaux ont porté sur l’efficacité de l’estimation postérieure dans le cadre de boosting. Suivant ce raisonnement, nous développons une estimation postérieure efficace en boosting Nearest Neighbors. Utilisant Universal Nearest Neighbours classification nous prouvons qu’il existe une sous-catégorie de fonctions, dont la minimisation apporte statistiquement de simples et efficaces estimateurs de Bayes postérieursDisproportion among class priors is encountered in a large number of domains making conventional learning algorithms less effective in predicting samples belonging to the minority classes. We aim at developing a reconstruction rule suited to multiclass skewed data. In performing this task we use the classification reliability that conveys useful information on the goodness of classification acts. In the framework of One-per-Class decomposition scheme we design a novel reconstruction rule, Reconstruction Rule by Selection, which uses classifiers reliabilities, crisp labels and a-priori distributions to compute the final decision. Tests show that system performance improves using this rule rather than using well-established reconstruction rules. We investigate also the rules in the Error Correcting Output Code (ECOC) decomposition framework. Inspired by a statistical reconstruction rule designed for the One-per-Class and Pair-Wise Coupling decomposition approaches, we have developed a rule that applies softmax regression on reliability outputs in order to estimate the final classification. Results show that this choice improves the performances with respect to the existing statistical rule and to well-established reconstruction rules. On the topic of reliability estimation we notice that small attention has been given to efficient posteriors estimation in the boosting framework. On this reason we develop an efficient posteriors estimator by boosting Nearest Neighbors. Using Universal Nearest Neighbours classifier we prove that a sub-class of surrogate losses exists, whose minimization brings simple and statistically efficient estimators for Bayes posteriors
10
Djennaoui, Mohand-Said. "Structuration des données dans le cadre d'un système de gestion de bases de connaissances". Lyon, INSA, 1992. http://www.theses.fr/1992ISAL0077.
Abstract (sommario):
La déduction et la structuration des informations sont des caractéristiques essentielles pour la nouvelle génération des Systèmes de Gestion de Bases de Données (appelés communément Systèmes de Gestion de Bases de Connaissances((SGBC) EPSILON est un SGBC basé sur l'intégration de la programmation logique (PROLOG) et des Bases de Données Relationnelles. Il permet d'utiliser les données stockées dans une Base de Données comme des faits PROLOG- et de façon transparente à l'uti1isateur. Cette thèse décrit l'enrichissement de ce système en le dotant de mécanismes de structuration de données dans le sens des relations NF2 (relations imbriquées). L'utilisateur peut définir des vues externes basées sur un modèle NF2. Au niveau interne, les relations restent compatibles avec le modèle relationnel classique. Sans remettre en cause le noyau d'EPSILON, nous avons ajouté les éléments suivants : • Un méta-interprète d'un langage de programmation logique incluant des constructeurs d'ensemble et de tuple. Un traducteur rendant transparent l'utilisation du méta-interprête précédent • un méta-interprète permettant d'interprêter des requêtes SQL qui manipulent des relations imbriquéesBoth the deduction and the structuration of the information are essential features for the new generation of DBMS (namely Knowledge Base management System : KBMS). EPSILON is KBMS integration (combining) logic programming (PROLOG) and relational databases ; It allows to use data stored in the data bases as prolog's facts and with user transparency. This work descibes the system's enriching by endowing it with structuration mechanisms in the sens of NF2 relations (Nested relations). The user can define external views based on a NF2 model. At the internal level, the relations remain compatible with the traditional relational model. Around the EPSILON kermel, we have designed and developed: - A meta-interpreter of logic based language including sets and tuples constructors. - A translater which allows to use the met-interpreter in a transparency way. - A meta-interpreter which allows to handle SQL request relation
11
El, Abed Walid. "Meta modèle sémantique et noyau informatique pour l'interrogation multilingue des bases de données en langue naturelle (théorie et application)". Besançon, 2001. http://www.theses.fr/2001BESA1014.
Abstract (sommario):
L'interrogation d'une base de données relationnelles, par un non spécialiste, constitue un véritable problème. En effet, l'utilisateur final doit au préalable connaître le langage de requête SQL (Structured Query Langage) et la structure, souvent complexe, de la base de données. Dans un tel contexte, il devient essentiel d'organiser des domaines interrogeables en langue naturelle. Un domaine est une base de données regroupant toute l'information pertinente autour d'un thème ou d'un sujet offrant ainsi la possibilité à l'utilisateur d'accéder à l'information sur le sujet en utilisant le langage naturel. . .
12
Laabi, Abderrazzak. "Étude et réalisation de la gestion des articles appartenant à des bases de données gérées par une machine bases de données". Paris 11, 1987. http://www.theses.fr/1987PA112338.
Abstract (sommario):
Le travail présenté dans cette thèse se situe dans le cadre d'un projet d'étude et de réalisation de trois couches du S. G. B. D. De la machine bases de données DORSAL-32. La première couche assure la gestion des articles dans le espaces de stockage, l'organisation des verrouillages des articles et des pages selon le mode d'accès effectue et le degré de cohérence de la transaction. Elle assure également la gestion des micro-journalisations qui permettent de garantir la propriété d'atomicité d'une action. La seconde assure la gestion du journal des transactions et la procédure de reprise à chaud, qui permettent de garantir les propriétés d'atomicité et de durabilité d'une transaction. Quant à la troisième couche, elle assure le contrôle concurrents, et la gestion des tables de verrous. Des accès des mesures de performances des méthodes utilisées sont présentés dans ce rapport. Le dernier chapitre contient un travail de recherche concernant la mise en pratique de la méthode de hachage virtuel linéaire dans notre S. G. B. D. Le problème étudie est celui des déplacements des articles d’une page à l'autre. Dans de telles conditions, les pointeurs d'articles classiquement utilises ne permettent pas d'effectuer des accès directs. Nous proposons un nouveau pointeur qui permet de réaliser un accès direct à l'article, et ceci quelle que soit la page où il se trouve à un instant donnéThe work presented in this thesis is part of a study and development project concerning the design of three layers of the DBMS on the DORSAL-32 Data Base Machine. The first layer ensures record management within the storage areas, record and page locking organization according to the access mode and transaction coherency degree. It ensures also the handling of micro-logs which permit to guarantee the atomicity of an action. The second layer ensures handling of transaction logging and warm restarts which guarantee the atomicity and durability of a transaction. The third layer ensures simultaneous access management and handling of lock tables. Performance measures of the methods used are also presented. The last chapter of this report contains a research work concerning the implementation of the virtual linear hashing method in our DBMS. The problem studied is the transfer of records from one page to another. Under these conditions, the record pointers which are classically used don't permit direct access. We propose a new pointer which enables direct access to the record, on no matter which page it is contained at a given instant
13
Baklouti, Fatma. "Algorithmes de construction du Treillis de Galois pour des contextes généralisés". Paris 9, 2006. https://portail.bu.dauphine.fr/fileviewer/index.php?doc=2006PA090003.
Abstract (sommario):
Dans cette thèse, nous nous intéressons à la structure du treillis de concepts (ou treillis de Galois). Plusieurs travaux antérieurs ont montré l'intérêt des treillis de concepts à l'analyse de données, la classification supervisée ou non supervisée, à la recherche documentaire, et plus récemment à la recherche des règles d'association. Plusieurs algorithmes d'extraction de concepts à partir de contextes binaires ont été proposés. Cependant, dans la pratique les bases de données utilisées sont de grande taille et ne sont pas toujours binaires. Ainsi, nous proposons un algorithme rapide, appelé ELL, d'extractions de concepts à partir de bases de données généralisés. A fin d'obtenir de meilleures performances et de traiter des bases de données volumineuses, nous proposons également une version distribuée de l'algorithme ELL appelé SD-ELLOur main concern in this thesis is concept (or Galois) lattices. As shown by previous works, concept lattices is an effective tool for data analysis and knowledge discovery, especially for classification, clustering, information retrieval, and more recently for association rules mining. Several algorithms were proposed to generate concepts or concept lattices on a data context. They focus on binary data arrays, called contexts. However, in practice we need to deal with contexts which are large and not necessarily binary. We propose a fast Galois lattice-building algorithm, called ELL algorithm, for generating closed itemsets from objects having general descriptions and we compare its performance with other existing algorithms. In order to have better performance et to treat bigger contexts we propose also a distributed version of ELL algorithm called SD-ELL
14
Olteanu, Ana-Maria. "Fusion de connaissances imparfaites pour l'appariement de données géographiques : proposition d'une approche s'appuyant sur la théorie des fonctions de croyance". Phd thesis, Université Paris-Est, 2008. http://tel.archives-ouvertes.fr/tel-00469407.
Abstract (sommario):
De nos jours, il existe de nombreuses bases de données géographiques (BDG) couvrant le même territoire. Les données géographiques sont modélisées différemment (par exemple une rivière peut être modélisée par une ligne ou bien par une surface), elles sont destinées à répondre à plusieurs applications (visualisation, analyse) et elles sont créées suivant des modes d'acquisition divers (sources, processus). Tous ces facteurs créent une indépendance entre les BDG, qui pose certains problèmes à la fois aux producteurs et aux utilisateurs. Ainsi, une solution est d'expliciter les relations entre les divers objets des bases de données, c'est-à-dire de mettre en correspondance des objets homologues représentant la même réalité. Ce processus est connu sous le nom d'appariement de données géographiques. La complexité du processus d'appariement fait que les approches existantes varient en fonction des besoins auxquels l'appariement répond, et dépendent des types de données à apparier (points, lignes ou surfaces) et du niveau de détail. Nous avons remarqué que la plupart des approches sont basées sur la géométrie et les relations topologiques des objets géographiques et très peu sont celles qui prennent en compte l'information descriptive des objets géographiques. De plus, pour la plupart des approches, les critères sont enchaînés et les connaissances sont à l'intérieur du processus. Suite à cette analyse, nous proposons une approche d'appariement de données qui est guidée par des connaissances et qui prend en compte tous les critères simultanément en exploitant à la fois la géométrie, l'information descriptive et les relations entre eux. Afin de formaliser les connaissances et de modéliser leurs imperfections (imprécision, incertitude et incomplétude), nous avons utilisé la théorie des fonctions de croyance [Shafer, 1976]. Notre approche d'appariement de données est composée de cinq étapes : après une sélection des candidats, nous initialisons les masses de croyance en analysant chaque candidat indépendamment des autres au moyen des différentes connaissances exprimées par divers critères d'appariement. Ensuite, nous fusionnons les critères d'appariement et les candidats. Enfin, une décision est prise. Nous avons testé notre approche sur des données réelles ayant des niveaux de détail différents représentant le relief (données ponctuelles) et les réseaux routiers (données linéaires)
15
Robidou, Sébastien. "Représentation de l'imperfection des connaissances dans les bases de situation des systèmes de commandement". Rouen, 1997. http://www.theses.fr/1997ROUES083.
Abstract (sommario):
On peut définir la fusion de données comme un processus visant à unifier un flux d'informations issues de capteurs hétérogènes dans le but d'élaborer une représentation la plus exacte, complète et cohérente possible du monde extérieur, appelée situation. Cependant les informations capteurs en entrée des systèmes de fusion ne constituent qu'une description partielle entachée d'incertitude et d'imprécision de la réalité, dont il faut pouvoir rendre compte de manière pertinente, en particulier au sein des bases de données utilisées par ces systèmes. Dans ce contexte nous proposons une approche formelle originale basée sur les notions de collection floue et de quantité fonctionnelle floue, afin de rendre compte des formes d'imprécision et d'incertitudes complexes rencontrées : représenter le doute sur l'existence d'une entité perçue ou exprimer une situation perçue comme un ensemble de situations possibles constituées d'objets de situation décrits de manière plus ou moins précise et complète. Afin de rendre compte de ces différentes formes d'imperfection au sein d'une base de données de situation nous introduisons un langage de description de données et un langage de manipulation de données dans le cadre du standard ODMG-93, permettant d'interroger la base de données au moyen de critères portant sur des attributs imprécis et sur des objets dont l'existence est plus ou moins certaine.
16
Taraviras, Stavros. "Évaluation de la diversité moléculaire des bases de données de molécules à intérêt pharmaceutique, en utilisant la théorie des graphes chimiques". Nice, 2000. http://www.theses.fr/2000NICE5472.
Abstract (sommario):
La compétition entre les grands groupes pharmaceutiques dans la recherche de nouvelles substances actives a favorisé le développement de nouvelles techniques de synthèses (chimie combinatoire et synthèse parallèle) et de méthodes de tests rapides des molécules (High-throughput screening ou HTS). Contrairement aux méthodes classiques, ces techniques ont pour caractéristique commune d'opérer sur de très grands nombres de molécules. Malgré leur puissance, il est vite apparu nécessaire de sélectionner des sous-ensembles représentatifs de l'énorme éventail de molécules potentiellement actives. Cette exigence est à la base du concept de diversité moléculaire. Les structures chimiques sont usuellement caractérisées par des descripteurs moléculaires qui appartiennent à plusieurs classes distinctes. Les descripteurs topologiques, qui sont au nombre de plusieurs centaines, apparaissent bien adaptés pour aborder ce problème. Le but de ce travail est de proposer des méthodes pour choisir des ensembles optimaux de descripteurs, afin de bien échantillonner la diversité de l'espace chimique.
17
Groz, Benoît. "XML security views : queries, updates and schemas". Thesis, Lille 1, 2012. http://www.theses.fr/2012LIL10143/document.
Abstract (sommario):
Les évolutions technologiques ont consacré l'émergence des services web et du stockage des données en ligne, en complément des bases de données traditionnelles. Ces évolutions facilitent l'accès aux données, mais en contrepartie soulèvent de nouvelles problématiques de sécurité. La mise en œuvre de politiques de contrôle d'accès appropriées est une des approches permettant de réduire ces risques. Nous étudions ici les politiques de contrôle d'accès au niveau d'un document XML, politiques que nous modélisons par des vues de sécurité XML (non matérialisées) à l'instar de Fan et al. Ces vues peuvent être représentées facilement par des alignements d'arbres grâce à l'absence d'opérateurs arithmétiques ou de restructuration. Notre objectif est par conséquent d'examiner comment manipuler efficacement ce type de vues, à l'aide des méthodes formelles, et plus particulièrement des techniques de réécriture de requêtes et la théorie des automates d'arbres. Trois directions principales ont orienté nos recherches: nous avons tout d'abord élaboré des algorithmes pour évaluer l'expressivité d'une vue, en fonction des requêtes qui peuvent être exprimées à travers cette vue. Il s'avère que l'on ne peut décider en général si une vue permet d'exprimer une requête particulière, mais cela devient possible lorsque la vue satisfait des hypothèses générales. En second lieu, nous avons considéré les problèmes soulevés par la mises à jour du document à travers une vue. Enfin, nous proposons des solutions pour construire automatiquement un schéma de la vue. En particulier, nous présentons différentes techniques pour représenter de façon approchée l'ensemble des documents au moyen d'une DTDThe evolution of web technologies and social trends fostered a shift from traditional enterprise databases to web services and online data. While making data more readily available to users, this evolution also raises additional security concerns regarding the privacy of users and more generally the disclosure of sensitive information. The implementation of appropriate access control models is one of the approaches to mitigate the threat. We investigate an access control model based on (non-materialized) XML views, as presented among others by Fan et al. The simplicity of such views, and in particular the absence of arithmetic features and restructuring, facilitates their modelization with tree alignments. Our objective is therefore to investigate how to manipulate efficiently such views, using formal methods, and especially query rewriting and tree automata. Our research follows essentially three directions: we first develop new algorithms to assess the expressivity of views, in terms of determinacy, query rewriting and certain answers. We show that those problems, although undecidable in our most general setting, can be decided under reasonable restrictions. Then we address the problem of handling updates in the security view framework. And last, we investigate the classical issues raised by schemata, focusing on the specific "determinism'' requirements of DTDs and XML Schemata. In particular, we survey some techniques to approximate the set of all possible view documents with a DTD, and we provide new algorithms to check if the content models of a DTD are deterministic
18
Chéry, Alexis. "Étude des occurences des films et des cinéastes dans les ouvrages français de théorie sur le cinéma". Paris 1, 2009. http://www.theses.fr/2009PA010536.
Abstract (sommario):
Adossés aux films, les ouvrages de théorie constituent la pierre angulaire de la recherche en cinéma. Essayer de mieux cerner les références des théoriciens est donc une démarche saine du point de vue de la compréhension des résultats des travaux universitaires. Au travers de l'analyse des références d'une centaine d'ouvrages et grâce à l'utilisation de l'outil informatique, cette étude ambitionne de décrire précisément la structure des panthéons cinématographiques des analystes français. Les résultats obtenus démontrent principalement la très forte concentration des références autour de quelques oeuvres, la prédominance des films des années 1950 et 1960, l'hégémonie des films américains et français et la disjonction de ces références avec les champions du box-office. La thèse tente également de fournir des pistes permettant d'expliquer les hiérarchies ainsi observées. Importance de l'apport théorique de l'œuvre certes, mais pas seulement: impact de la réception critique, débat éventuel créé autour du film, appartenance ou non de celui-ci à un mouvement qui cherche à s'imposer par les écrits, verve théorique de son réalisateur, ou encore manque de renouvellement des références, influent également sur le niveau de présence du film dans les ouvrages. Par la suite, cette thèse pourrait trouver deux prolongements principaux : l'extension de la démarche à des ouvrages étrangers, par exemple américains, et la mise à jour de cette étude dans quelques dizaines d'années, pour déterminer dans quelle mesure les références auront évolué.
19
Moll, Georges-Henri. "Un langage pivot pour le couplage de Prolog avec des bases de données : formalisation et environnement opérationnel". Lyon 1, 1987. http://www.theses.fr/1987LYO10102.
Abstract (sommario):
Un langage pivot, base sur l'algebre relationnelle, a ete defini pour servir de pont semantique entre prolog et les differents langages de manipulation de donnees des bases. Il joue un role operationnel grace a des modules: de separation automatique des parties concernant les bases dans un programme prolog; de traduction et d'optimisation lui conferant la puissance d'un langage pour manipuler des donnees reparties
20
Castagliola, Carole. "Héritage et valuation dans les réseaux sémantiques pour les bases de données objets". Compiègne, 1991. http://www.theses.fr/1991COMPD363.
Abstract (sommario):
Les bases de données objets s'articulent autour de trois pôles : les langages à objets, l'intelligence artificielle et les techniques de bases de données. Dans les produits ou systèmes existants, ces pôles sont réunis deux à deux. G-BASE TM, la base de données objets de GRAPHAEL TM, regroupe à la fois les techniques d'IA et celles des bases de données. Nous décrivons la solution adoptée afin d'y intégrer les mécanismes des langages à objets, faisant ainsi cohabiter les trois aspects dans un même environnement. L'extension des mécanismes de représentation de la connaissance dans le modèle de G-BASE est étudiée. Une solution est notamment proposée pour l'implantation des prototypes dans le modèle de G-BASE. Une étude portant sur les assertions et sur leur représentation par des méthodes déclaratives ou procédurales est menée. Toutefois, aucune solution satisfaisante n'a pu être dégagée. Il apparaît que la logique soit beaucoup plus adaptée au traitement des assertions que ne le sont les réseaux sémantiques. La dernière partie du travail est consacrée à la valuation des réseaux sémantiques. Les applications sont passées en revue et certains problèmes non résolus sont mis en lumière. La valuation des réseaux sémantiques est une solution élégante à un certain nombre de difficultés. Citons, par exemple, la représentation d'informations complexes et nuancées, la détermination de la granularité, le traitement des exceptions ou encore la réorganisation d'un réseau en fonction des contextes etc. Une telle notion est cependant source de problèmes non résolus. A savoir l'attribution initiale des distances et leur ajustement par des techniques d'apprentissage, la non-transitivité des arcs qui est un obstacle a la généralisation de la valuation et enfin la sémantique des valeurs attribuées.
21
Ait, Taleb Saadia. "La terminologie arabe contemporaine : théorie et application dans la base des données Lexar". Bordeaux 3, 1988. http://www.theses.fr/1988BOR30046.
22
Mokhtari, Amine. "Système personnalisé de planification d'itinéraire unimodal : une approche basée sur la théorie des ensembles flous". Rennes 1, 2011. http://www.theses.fr/2011REN1E004.
Abstract (sommario):
Dans cette thèse, nous présentons un ensemble de contributions destinées à la définition d’une nouvelle génération de systèmes de planification d’itinéraire unimodal, capable de prendre en charge des préférences utilisateur complexes. La théorie des ensembles flous a été utilisée comme socle formel pour nos contributions. La première est une typologie des préférences utilisateur ayant du sens dans le cadre d’un déplacement unimodal. La nature bipolaire des préférences utilisateur dans un tel contexte est aussi discutée et prise en considération. Notre seconde contribution porte sur un langage fondé sur le calcul relationnel de tuples, RPQL, permettant la formulation de requêtes bipolaires de planification d’itinéraire avec préférences. Une approche permettant d’augmenter une requête avec de nouvelles préférences, déduites du contexte de l’utilisateur, constitue notre troisième contribution. Par ailleurs, l’architecture d’un système personnalisé de planification d’itinéraire a été proposée, ainsi qu’une approche efficace pour l’évaluation de requêtes de planification avec préférences. Enfin, des résultats expérimentaux, issus d’une plateforme de test mettant en œuvre notre système, sont présentés et discutés.
23
Ileana, Ioana. "Réécriture de requêtes avec des vues : une perspective théorique et pratique". Electronic Thesis or Diss., Paris, ENST, 2014. http://www.theses.fr/2014ENST0062.
Abstract (sommario):
Dans ce document, nous adressons le problème de la réécriture de requêtes avec des vues, en adoptant une perspective à la fois théorique et pratique. Dans le premier et principal chapitre, nous approchons le sujet de la recherche de toutes les reformulations minimales (sans atomes relationnels redondants) pour une requête relationnelle conjonctive, sous des contraintes d’intégrité qui incluent la relation entre les schémas source et cible. Nous présentons un nouvel algorithme, correct et complet, le Provenance-Aware Chase & Backchase, qui résout le problème des reformulations avec des performances significatives sur le plan pratique. Nous présentons sa caractérisation théorique détaillée, son implémentation optimisée et son évaluation, montrant des gains de performance jusqu’à deux ordres de grandeur par rapport à un SGBD commercial. Nous généralisons notre algorithme pour trouver directement des reformulations de coût minimum pour les fonctions de coût monotones, et montrons les gains de performance de cette adaptation. Avec notre algorithme, nous introduisons également un nouveau type de chase, la Provenance-Aware Chase, qui comporte son propre intérêt théorique, en tant que moyen de raisonnement sur l’interaction entre la provenance et les contraintes. Dans le deuxième chapitre, nous nous plaçons dans un contexte XML et nous revisitons le travail de Cautis, Deutsch and Onose sur problème de la réécriture de requêtes XPath par un seul niveau d’intersection de plusieurs vues. Nous étendons l’analyse de ce probleme en montrant ses connexions avec les problèmes de l’équivalence DAG-arbre et de la union-freeness d’un DAG. Nous raffinons un algorithme de réécriture proposé par Cautis, Deutsch and Onose pour obtenir une complexité polynomiale et améliorer sa complétude, et présentons un ensemble d’optimisations des procedures de réécriture, necessaires pour atteindre des performances pratiques. Nous fournissons une implementation complète comprenant ces optimizations ainsi que son evaluation experimentale extensive, montrant la performance et l’utilité de la technique polynomiale de réécritureIn this work, we address the problem of query rewriting using views, by adopting both a theoretical and a pragmatic perspective. In the first and main chapter, we approach the topic of finding all minimal (i.e. with no redundant relational atoms) conjunctive query reformulations for a relational conjunctive query, under constraints expressed as embedded dependencies, including the relationship between the source and the target schemas. We present a novel sound and complete algorithm, the Provenance-Aware Chase & Backchase, that solves the minimal reformulations problem with practically relevant performance. We provide a detailed theoretical characterization of our algorithm. We further present the optimized implementation and the experimental evaluation thereof, and exhibit natural scenarios yielding speed-ups of up to two orders of magnitude between the execution of a best view-based rewriting found by a commercial DBMS and that of a best rewriting found by our algorithm. We generalize the Provenance-Aware Chase & Backchase towards directly finding minimum-cost reformulations for monotonic cost functions, and show the performance improvements this adaptation further enables. With our algorithm, we introduce a novel chase flavour, the Provenance-Aware Chase, which is interesting on its own, as a means of reasoning about the interaction between provenance and constraints. In the second chapter, we move to an XML context and revisit the previous work of Cautis, Deutsch and Onose on the problem of finding XPath query rewritings with a single level of intersection of multiple views. We enrich the analysis of the rewriting problem by showing its links to the problems of DAG-tree equivalence and union-freeness. We refine the rule-based rewriting technique proposed by Cautis, Deutsch and Onose to ensure its polynomial complexity and improve its completeness, and present a range of optimizations on the rewriting procedures, necessary to achieve practical performance. We provide a complete implementation comprising these optimizations and a thorough experimental evaluation thereof, showing the performanceand utility of the polynomial rewriting technique
24
Machado, Javam de Castro. "Parallélisme et transactions dans les bases de données à objets". Université Joseph Fourier (Grenoble), 1995. https://tel.archives-ouvertes.fr/tel-00005039.
Abstract (sommario):
Notre travail cherche à exploiter le parallélisme dans le contexte des systèmes de gestion de bases de données a objets a d'autres niveaux d'abstraction que celui d'une requête SQL, à savoir le parallélisme intra-transaction et le parallélisme intra-application. Notre approche pour parallélisassions des transactions considère un modèle de transactions classiques, ou une transaction est une séquence d’Operations. Le parallélisme intra-transaction consiste à transformer le code d'une transaction pour pouvoir exécuter ses opérations en parallèle. Notre approche pour l'exploitation du parallélisme intra-application étend tout d'abord le modèle de parallélisme intra-transaction de manière à considérer la transaction comme unité de parallélisassions. Deuxièmement nous avons considère l'exploitation du parallélisme intra-application dans un contexte ou le modèle de transaction fournit des transactions emboitées. Nous avons développé un modèle de parallélisassions des applications où nous associons le parallélisme offert par le modèle des transactions emboitées avec le parallélisme par transformation de notre approche de parallélisation des transactionsNous avons implanté un premier prototype qui met en œuvre le modèle de parallélisation des transactions. Pour cela, nous avons utilisé le système de bases de données à objet 02. Notre prototype introduit le parallélisme par la création et la synchronisation des activités parallèles au sein du processus client 02 qui exécute une application. Le système étant développé sur une machine monoprocesseur, les fonctions liées au parallélisme utilisent de processus légers. Nous avons applique ensuite notre modèle de parallélisations au système de règles NAOS. Notre approche considère l'ensemble de règles d'un cycle d'exécution, dites règles candidates, pour la parallélisation. Nous construisons un plan d'exécution pour les règles candidates d'un cycle qui détermine l'exécution séquentielle ou parallèle pour les règles
25
Bouarar, Selma. "Vers une conception logique et physique des bases de données avancées dirigée par la variabilité". Thesis, Chasseneuil-du-Poitou, Ecole nationale supérieure de mécanique et d'aérotechnique, 2016. http://www.theses.fr/2016ESMA0024/document.
Abstract (sommario):
Le processus de conception des BD ne cesse d'augmenter en complexité et d'exiger plus de temps et de ressources afin de contenir la diversité des applications BD. Rappelons qu’il se base essentiellement sur le talent et les connaissances des concepteurs. Ces bases s'avèrent de plus en plus insuffisantes face à la croissante diversité de choix de conception, en soulevant le problème de la fiabilité et de l'exhaustivité de cette connaissance. Ce problème est bien connu sous le nom de la gestion de la variabilité en génie logiciel. S’il existe quelques travaux de gestion de variabilité portant sur les phases physique et conceptuelle, peu se sont intéressés à la phase logique. De plus, ces travaux abordent les phases de conception de manière séparée, ignorant ainsi les différentes interdépendances.Dans cette thèse, nous présentons d'abord la démarche à suivre afin d'adopter la technique des lignes de produits et ce sur l'ensemble du processus de conception afin de (i) considérer les interdépendances entre les phases, (ii) offrir une vision globale au concepteur, et (iii) augmenter l'automatisation. Vu l'étendue de la question, nous procédons par étapes dans la réalisation de cette vision, en consacrant cette thèse à l'étude d'un cas choisi de façon à montrer : (i) l'importance de la variabilité de la conception logique, (ii) comment la gérer en offrant aux concepteurs l'exhaustivité des choix, et la fiabilité de la sélection, (iii) son impact sur la conception physique (gestion multiphase),(iv) l'évaluation de la conception logique, et de l'impact de la variabilité logique sur la conception physique (sélection des vues matérialisées) en termes des besoins non fonctionnel(s) :temps d'exécution, consommation d'énergie voire l'espace de stockageThe evolution of computer technology has strongly impacted the database design process which is henceforth requiring more time and resources to encompass the diversity of DB applications.Note that designers rely on their talent and knowledge, which have proven insufficient to face the increasing diversity of design choices, raising the problem of the reliability and completeness of this knowledge. This problem is well known as variability management in software engineering. While there exist some works on managing variability of physical and conceptual phases, very few have focused on logical design. Moreover, these works focus on design phases separately, thus ignore the different interdependencies. In this thesis, we first present a methodology to manage the variability of the whole DB design process using the technique of software product lines, so that (i)interdependencies between design phases can be considered, (ii) a holistic vision is provided to the designer and (iii) process automation is increased. Given the scope of the study, we proceed step-bystepin implementing this vision, by studying a case that shows: (i) the importance of logical design variability (iii) its impact on physical design (multi-phase management), (iv) the evaluation of logical design, and the impact of logical variability on the physical design (materialized view selection) in terms of non-functional requirements: execution time, energy consumption and storage space
26
Alilaouar, Abdeslame. "Contribution à l'interrogation flexible de données semi-structurées". Toulouse 3, 2007. http://thesesups.ups-tlse.fr/90/.
Abstract (sommario):
Pour manipuler les Données Semi-Structurées (DSS) et en extraire les informations pertinentes en termes de structure et/ou de contenu pour l'utilisateur, de nombreux langages de requêtes ont été proposés. Ces langages de requêtes devraient donc prendre en compte non seulement le contenu mais aussi la structure sous-jacente car cette dernière peut changer complètement leur pertinence et leur adéquation vis à vis des besoins exprimés par l'utilisateur. Cependant, la non connaissance a priori et l'hétérogénéité de structure de DSS rendent les langages d'interrogation de BD classiques incompatibles avec l'interrogation de telles collections semi-structurées. Les techniques standards d'interrogations basées sur l'appariement exact sont donc inadaptées pour interroger des sources de DSS : une requête peut aboutir à un ensemble vide ou incomplet de réponses lors de l'interrogation même s'il existe des réponses pertinentes dans la(les) source(s) à interroger. Un autre problème relève de la prise en compte de l'information "manquante". En effet, puisque la structure de l'instance de document est par essence incomplète, il est possible que l'information ne soit pas explicitement signifiée ou encore qu'elle n'ait pas été correctement élicitée. Ceci implique de ne pas considérer cette absence d'information comme une information négative, mais de traiter ces cas avec l'incertitude qui convient, dans un algorithme général de "ranking". Pour résoudre ces problèmes le recours aux techniques d'appariement flexible (approximatif) et la réponse sous forme des listes ordonnées de réponses selon les préférences de l'utilisateur, représentent un choix presque inévitable. Les travaux menés jusqu'ici dans le cadre de l'interrogation flexible de BD ont révélé que la logique floue constitue un cadre particulièrement bien adapté pour modéliser la notion de flexibilité et de préférences selon le raisonnement humain. Dans ce sens, nous proposons un modèle d'interrogation flexible pour les DSS en général et pour les documents XML en particulier, en prenant en compte le contenu et la structure sous-jacente des DSS. La logique floue sera utilisée pour représenter les préférences de l'utilisateur sur le contenu et la structure des DSS. D'autre part, à la fin du processus d'interrogation, chaque réponse est associée à un degré compris dans l'intervalle ]0,1]. Plus ce degré est faible, moins la réponse semble pertinente. Ce degré est calculé en utilisant le degré d'appartenance (m) et des mesures de similarité connues dans les systèmes de recherche d'informations (SRI) pour le contenu, et l'arbre recouvrant minimal pour la structure. Le modèle proposé a été évalué et validé dans le cadre de plateforme PRETI et d'INEX, grâce au prototype que nous avons développéMany querying languages have been proposed to manipulate Semi-Structured Data (SSD) and to extract relevant information (in terms of structure and/or content) to the user. Such querying languages should take into account not only the content but also the underlying structure since it can completely change their relevance and adequacy with respect to the needs expressed by the user. However, not having prior knowledge and the heterogeneity of SSD structure makes classical database languages inadequate. The work undertaken on database flexible querying revealed that fuzzy logic is particularly well-suited for modelling the notion of flexibility and preferences according to human reasoning. In this sense, we propose a model of flexible query for SSD in general and XML documents, taking into account the content and the underlying structure of SSD. Fuzzy logic is used to represent the user's preferences on the content and structure of SSD. At the end of the evaluation process, every response is associated with a degree in the interval ]0. 1]. The more this degree is low, the answer seems less relevant. This degree is calculated using the degree of ownership and measures known similarity in information retrieval systems for content, and the minimum spanning tree for the structure. The proposed model has been reviewed and validated using PRETI Platform and INEX benchmark, thanks to the prototype that we've developped
27
Coupaye, Thierry. "Un modèle d'exécution paramétrique pour systèmes de bases de données actifs". Phd thesis, Université Joseph Fourier (Grenoble), 1996. http://tel.archives-ouvertes.fr/tel-00004983.
Abstract (sommario):
Un systeme de bases de données actif est capable d'executer automatiquement des actions predefinies en reponse a des evenements specifiques lorsque certaines conditions sont satisfaites. Les regles actives, de la forme evenement-Condition-Action, sont au coeur de cette approche. Dans cette these, nous nous interessons aux modeles d'execution des systemes actifs. Le modele d'execution d'un systeme actif decrit quand et comment (ordonnancement, synchronisation) sont executées, au cours d'une application, les regles declenchées lors de l'execution d'une transaction. Nous proposons tout d'abord une taxonomie et une representation graphique des modeles d'execution des systemes actifs. Nous exposons ensuite un modele d'execution parametrique nomme Flare (Flexible active rule execution). Une caracteristique essentielle de ce modele est de considerer des modules de regles - chaque module etant destine a une utilisation particuliere des regles. On peut specifier, d'une part, le comportement de chaque regle d'un module, et d'autre part, la strategie d'execution de chaque module. Il suffit, pour cela, de choisir une valeur pour chacun des parametres proposes parmi un ensemble de valeurs predefinies. Nous donnons egalement une semantique denotationnelle (ou fonctionnelle) du modele. Nous montrons que ce formalisme fournit une specification implantable que nous utilisons dans le cadre de l'experimentation que nous menons autours de NAOS - un mecanisme de regles actives pour le SGBD a objets O2 - afin de remplacer son moteur d'execution par Flare.
28
Mouaddib, Noureddine. "Gestion des informations nuancées : une proposition de modèle et de méthode pour l'identification nuancée d'un phénomène". Nancy 1, 1989. http://www.theses.fr/1989NAN10475.
Abstract (sommario):
Cette thèse présente une solution globale au problème de l'identification d'un phénomène ou d'un objet mal défini dans un domaine d'application décrit par des connaissances nuancées. Cette solution comprend trois éléments: un modèle de représentation des connaissances nuancées, une méthode de détermination des objets ressemblant au phénomène à identifier, un processus d'identification dans un système possédant une base de données multimédia. Le modèle de représentation des connaissances présente les particularités suivantes: une ou plusieurs nuances, exprimées en langue naturelle, peuvent être associés à chacune des valeurs prise par un caractère d'un objet, à chaque domaine de définition discret de caractère peut être associé un micro-thésaurus dont les liens (généricité, synonymie, opposition) peuvent être munis de coefficients exprimant certaines distances sémantiques entre les termes, des poids d'importance ou de confiance peuvent être associés à chaque caractère aussi bien dans la description des objets de référence que dans la description du phénomène à identifier. La méthode d'identification repose sur la théorie des possibilités dont nous avons assoupli l'application en diminuant le nombre de fonctions caractéristiques à fournir, par le spécialiste du domaine d'application, grâce à l'introduction d'heuristiques permettant soit de les générer à partir des micro-thérausus soit de les calculer à partir d'autres déjà définies par composition ou par transformation. Le processus d'identification permet une identification interactive et progressive au cours de laquelle alternent des phases de filtrage, d'affichage de résultats, d'observation d'images et de consultation de textes. En cas d'échec, nous proposons une stratégie de retour-arrière qui s'appuie sur les poids des caractères.
29
Simon, Arnaud. "Outils classificatoires par objets pour l'extraction de connaissances dans des bases de données". Nancy 1, 2000. http://www.theses.fr/2000NAN10069.
Abstract (sommario):
Cette dernière décennie a vu évoluer la problématique relative au traitement des données d'une part par un facteur d'échelle - les données ainsi que la représentation qui leur est associée sont de plus en plus nombreuses - et de disponibilité (notamment par le développement des réseaux de communication et des supports de stockage) de l'autre. L'étude des techniques permettrait d'exploiter ces masses de données maintenant disponibles fait l'objet du courant de recherche appelé extraction de connaissances dans des bases de données ou ECBD. Les principales techniques étudiées dans le cadre de l'ECBD sont issues des bases de données, de l'apprentissage, de la représentation des connaissances, des statistiques, de l'analyse de données et de la visualisation. L'ECBD est ainsi un domaine de recherche pluridisciplinaire où l'ensemble des techniques mises en oeuvre visent l'objectif commun qui consiste à exploiter au mieux les données. L'approche de l'ECBD qui est adoptée dans ce mémoire de thèse est fondée sur l'étude d'outils classificatoires par objets. Les techniques classiques d'arbres de décision et principalement de treillis de Galois sont adaptées - ces techniques relèvent des problématiques issues des modèles fondés sur des « tableaux de données» -- au cas ou les données relèvent d'un système de représentation des connaissances par objets, ou système de RCO. Un système de RCO a pour fonction de stocker et d'organiser les connaissances autour de la notion de hiérarchie d'objets et de fournir des services inférentiels - qui sont destinés à compléter l'information disponible - et d'accès à l'information (filtrage) tous deux fondés sur des méthodes classificatoires. Par ailleurs, un système de RCO permet de manipuler des données « complexes» car leurs attributs ne se réduisent pas à des types de base atomique mais peuvent être d'autres objets (relations) ; aussi bien mono que multivalués. Les fonctionnalités de représentation et inférentielles des systèmes de RCO sont mises à profit pour l'ECBD pour elles-même mais aussi pour la construction de structures classificatoires d'arbres de décision et de treillis de Galois. Les structures ainsi construites sont des hiérarchies d'objets qui relèvent du modèle de RCO. Une telle approche a pour avantages de prendre en compte les connaissances disponibles et de produire des structures directement interprétables et réutilisables - pour mener à bien des inférences ou des constructions de nouvelles structures. Les structures de treillis de Galois sont également mises à profit pour la construction de toutes les règles d'association partielles. Nous montrons que notre approche possède l'avantage de construire moins de règles, car des règles redondantes ne sont pas produites, de permettre une mise à jour des règles pour tenir compte de nouveaux individus ou de nouvelles propriétés et d'améliorer l'expressivité des règles.
30
Ileana, Ioana. "Réécriture de requêtes avec des vues : une perspective théorique et pratique". Thesis, Paris, ENST, 2014. http://www.theses.fr/2014ENST0062/document.
Abstract (sommario):
Dans ce document, nous adressons le problème de la réécriture de requêtes avec des vues, en adoptant une perspective à la fois théorique et pratique. Dans le premier et principal chapitre, nous approchons le sujet de la recherche de toutes les reformulations minimales (sans atomes relationnels redondants) pour une requête relationnelle conjonctive, sous des contraintes d’intégrité qui incluent la relation entre les schémas source et cible. Nous présentons un nouvel algorithme, correct et complet, le Provenance-Aware Chase & Backchase, qui résout le problème des reformulations avec des performances significatives sur le plan pratique. Nous présentons sa caractérisation théorique détaillée, son implémentation optimisée et son évaluation, montrant des gains de performance jusqu’à deux ordres de grandeur par rapport à un SGBD commercial. Nous généralisons notre algorithme pour trouver directement des reformulations de coût minimum pour les fonctions de coût monotones, et montrons les gains de performance de cette adaptation. Avec notre algorithme, nous introduisons également un nouveau type de chase, la Provenance-Aware Chase, qui comporte son propre intérêt théorique, en tant que moyen de raisonnement sur l’interaction entre la provenance et les contraintes. Dans le deuxième chapitre, nous nous plaçons dans un contexte XML et nous revisitons le travail de Cautis, Deutsch and Onose sur problème de la réécriture de requêtes XPath par un seul niveau d’intersection de plusieurs vues. Nous étendons l’analyse de ce probleme en montrant ses connexions avec les problèmes de l’équivalence DAG-arbre et de la union-freeness d’un DAG. Nous raffinons un algorithme de réécriture proposé par Cautis, Deutsch and Onose pour obtenir une complexité polynomiale et améliorer sa complétude, et présentons un ensemble d’optimisations des procedures de réécriture, necessaires pour atteindre des performances pratiques. Nous fournissons une implementation complète comprenant ces optimizations ainsi que son evaluation experimentale extensive, montrant la performance et l’utilité de la technique polynomiale de réécritureIn this work, we address the problem of query rewriting using views, by adopting both a theoretical and a pragmatic perspective. In the first and main chapter, we approach the topic of finding all minimal (i.e. with no redundant relational atoms) conjunctive query reformulations for a relational conjunctive query, under constraints expressed as embedded dependencies, including the relationship between the source and the target schemas. We present a novel sound and complete algorithm, the Provenance-Aware Chase & Backchase, that solves the minimal reformulations problem with practically relevant performance. We provide a detailed theoretical characterization of our algorithm. We further present the optimized implementation and the experimental evaluation thereof, and exhibit natural scenarios yielding speed-ups of up to two orders of magnitude between the execution of a best view-based rewriting found by a commercial DBMS and that of a best rewriting found by our algorithm. We generalize the Provenance-Aware Chase & Backchase towards directly finding minimum-cost reformulations for monotonic cost functions, and show the performance improvements this adaptation further enables. With our algorithm, we introduce a novel chase flavour, the Provenance-Aware Chase, which is interesting on its own, as a means of reasoning about the interaction between provenance and constraints. In the second chapter, we move to an XML context and revisit the previous work of Cautis, Deutsch and Onose on the problem of finding XPath query rewritings with a single level of intersection of multiple views. We enrich the analysis of the rewriting problem by showing its links to the problems of DAG-tree equivalence and union-freeness. We refine the rule-based rewriting technique proposed by Cautis, Deutsch and Onose to ensure its polynomial complexity and improve its completeness, and present a range of optimizations on the rewriting procedures, necessary to achieve practical performance. We provide a complete implementation comprising these optimizations and a thorough experimental evaluation thereof, showing the performanceand utility of the polynomial rewriting technique
31
Crosetti, Nicolas. "Enrichir et résoudre des programmes linéaires avec des requêtes conjonctives". Electronic Thesis or Diss., Université de Lille (2022-....), 2023. http://www.theses.fr/2023ULILB003.
Abstract (sommario):
L'optimisation mathématique et la gestion des données sont deux domaines majeurs de l'informatique qui sont largement étudiés par des communautés essentiellement distinctes.Cependant, les problèmes d'optimisation complexes dépendent souvent de grands jeux de données qui peuvent être difficiles à gérer,alors que la gestion de grandes quantités de données n'est utile que dans la mesure où l'on analyse ces données pour en extraire des connaissancesafin de résoudre un problème pratique, de sorte que ces domaines sont souvent entremêlés en pratique.Cette thèse se place à la croisée de ces deux domaines en étudiant les programmes linéaires qui raisonnent sur les réponses de requêtes de bases de données.La première contribution de cette thèse est la définition de ce que nous appelons le langage des programmes linéaires avec requêtes conjonctives (que nous noterons LP(CQ)).Il s'agit d'un langage de modélisation de programmes linéaires avec des constructions permettant d'exprimer des contraintes et sommes linéairesqui raisonnent sur les ensembles de réponses de requêtes de bases de données sous forme conjonctive.Nous décrivons ensuite la sémantique naturelle du langage en montrant comment de tels modèles peuvent être interprétés,en conjonction avec une base de données, en de vrais programmes linéairesqui peuvent ensuite être résolus par tout solveur de programmes linéaires standard et nous discutons de la difficulté de résoudre les modèles LP(CQ).Motivés par la difficulté de résoudre les modèles LP(CQ) en général, nous introduisons ensuiteun processus basé sur ce que nous appelons l'interprétation T-factorisée pour résoudre de tels modèles plus efficacement.Cette approche est basée sur des techniques classiques en théorie des bases de donnéespour exploiter la structure des requêtes en utilisant des décompositions arborescentes de petite largeur.L'interprétation T-factorisée produit un programme linéaire qui a la même valeur optimale que la sémantique naturelle du modèle mais moins de variableset qui peut donc être utilisé pour résoudre le modèle plus efficacement.La troisième contribution est une généralisation du résultat précédent au cadre des bases de données factorisées.Nous introduisons une structure de données spécifique pour coder succinctement les relations sous forme de circuit.Nous définissons ensuite l'interprétation dite C-factorisée qui exploite le caractère succinct de ces circuitspour produire un programme linéaire qui a la même valeur optimale que la sémantique naturelle du modèle mais avec moins de variablesde manière similaire à l'interprétation T-factorisée.Enfin, nous montrons que nous pouvons explicitement compiler les ensembles de réponses de requêtes conjonctives admettant une décomposition de petite largeuren circuits succincts, ce qui nous permet de récapturer l'interprétation T-factoriséeMathematical optimization and data management are two major fields of computer science that are widely studied by mostly separate communities.However complex optimization problems often depend on large datasets that may be cumbersome to manage,while managing large amounts of data is only useful insofar as one analyzes this data to extract some knowledgein order to solve some practical problem, so these fields are often actually intertwined in practice.This thesis places itself at the crossroads between these two fields by studying linear programs that reason about the answers of database queries.The first contribution of this thesis is the definition of the so-called language of linear programs with conjunctive queries, or LP(CQ) for short.It is a language to model linear programs with constructs that allow one to express linear constraints and linear sumsthat reason over the answer sets of database queries in the form of conjunctive queries.We then describe the natural semantics of the languageby showing how such models can be interpreted, in conjunction with a database, into actual linear programsthat can then be solved by any standard linear program solver and discuss the hardness of solving LP(CQ) models.Motivated by the hardness of solving LP(CQ) models in general, we then introducea process based on the so-called T-factorized interpretation to solve such models more efficiently.This approach is based on classical techniques from database theoryto exploit the structure of the queries using hypertree decompositions of small width.The T-factorized interpretation yields a linear programthat has the same optimal value as the natural semantics of the model but fewer variableswhich can thus be used to solve the model more efficiently.The third contribution is a generalization of the previous result to the framework of factorized databases.We introduce a specific circuit data-structure to succintly encode relations.We the define the so-called C-factorized interpretation that leverages the succintness of these circuitsto yield a linear program that has the same optimal value as the natural semantics of the model but fewer variablessimilarly to the T-factorized interpretation.Finally we show that we can explicitly compile the answer sets of conjunctive queries with small fractional hypertreewidthinto succinct circuits, thus allowing us to recapture the T-factorized interpretation
32
Grazziottin, Ribeiro Helena. "Un service de règles actives pour fédérations de bases de données". Université Joseph Fourier (Grenoble), 2000. http://www.theses.fr/2000GRE10084.
Abstract (sommario):
Dans les SGBD actifs la notion de réaction automatique à des événements est offerte au travers de règles actives de la forme Événement-Condition-Action. Ces règles sont gérées par des mécanismes spécifiques, dits actifs, intégrés dans les SGBD. Nous nous intéressons à l'introduction de ces mécanismes dans les fédérations de données. Les fédérations sont caractérisées par la distribution et l'autonomie de leurs composants et les mécanismes actifs doivent donc s'adapter à de telles caractéristiques. Notre approche propose de mettre en œuvre ces mécanismes sous forme d'un service de règles et un service d'événements qui coopèrent. Dans cette thèse nous nous intéressons plus précisément à la définition et à la structuration d'un service de règles. Nous proposons un service adaptable nommé ADRUS (pour ADaptable RUle Service) qui permet la construction et le contrôle de gestionnaires de règles spécialisés selon les besoins des applications de la fédération bases de données. Les modèles implantés par ces gestionnaires sont spécifiés à partir des trois métamodèles offerts par le service : le métamodèle de définition et de manipulation de règles, le métamodèle d'exécution de règles et le métamodèle de coopération entre gestionnaires. Notre travail se concentre sur la définition de la structure et des caractéristiques des métamodèles. Nous modélisons la coopération entre gestionnaires de règles, d'événements et de transactions car celle-ci est fondamentale pour l'exécution des règles dans une fédération. Nous présentons une expérience d'utilisation de notre service dans le cadre de la mise en œuvre de systèmes ODAS. Ces systèmes sont basés sur des services d'événements et de règles ouverts et répartis (Open and Distributed Active Services) utilisés au niveau d'une fédération de bases de données dans le contexte d'une application de type commerce électronique
33
Dellal, Ibrahim. "Gestion et exploitation de larges bases de connaissances en présence de données incomplètes et incertaines". Thesis, Chasseneuil-du-Poitou, Ecole nationale supérieure de mécanique et d'aérotechnique, 2019. http://www.theses.fr/2019ESMA0016/document.
Abstract (sommario):
Avec l’émergence et la prolifération des applications du Web sémantique, de nombreuses et récentes larges bases de connaissances (BC) sont disponibles sur le Web. Ces BC contiennent des entités (nommées) et des faits sur ces entités. Elles contiennent également les classes sémantiques de ces entités et leurs liens mutuels.De plus, plusieurs BC peuvent être interconnectées au niveau entités, formant ainsi le noyau du Web des données liées (ou ouvertes). Une caractérisation essentielle de ces BC est qu’elles contiennent des millions à des billions de triplets RDF incertains. Les causes de cette incertitude sont diverses et multiples. Elle peut résulter de l’intégration de sources de données de différents niveaux de fiabilité ou elle peut être causée par des considérations de préservation de la confidentialité. Aussi, elle peut être due à des facteurs li´es au manque d’informations, à la limitation des équipements de mesures ou à l’évolution d’informations. L’objectif de ce travail de thèse est d’améliorer l’ergonomie et la convivialité des systèmes modernes visant à exploiter des BC entachées d’incertitude. En particulier, ce travail propose des techniques coopératives et intelligentes aidant l’utilisateur dans ses prises de décisions quand ses recherches retournent des résultats insatisfaisants en termes de quantité ou de fiabilité.Dans un premier temps, nous nous sommes intéressés au problème des requêtes RDF retournant un ensemble vide de réponses. Ce type de réponse est frustrant et ne sert pas les attentes de l’utilisateur. L’approche proposée pour le traitement de ce problème est guidée par la requête initiale et offre un double avantage :(i) elle permet de fournir une explication sur l’échec de la requête en identifiant les MFS (Minimal Failing Sub-queries) et, (ii) elle permet de calculer des requêtes alternatives appelées XSS (maXimal Succeeding Subqueries),sémantiquement proches de la requête initiale et dont les réponses sont non-vides. Par ailleurs, d’un point de vue utilisateur, cette solution présente un niveau élevé de flexibilité dans le sens o`u plusieurs degrés d‘incertitude peuvent être simultanément considérés. Dans une seconde contribution, nous avons abord´e l’étude du problème dual au problème cité ci-dessus,c’est-`a-dire le cas des requêtes retournant un nombre trop élevé de réponses dans le contexte des données RDF.La solution préconisée vise `a réduire cet ensemble de réponses pour permettre à l’utilisateur de les examiner.Des contreparties des MFS et des XSS ont été établies, ce qui a permis d’identifier, d’une part, les causes du problème et, d’autre part, des requêtes alternatives dont les résultats peuvent être directement et facilement exploitables à des fins de décision.L’ensemble de nos propositions ont été validées par une série d’expérimentations portant sur différentes larges bases de connaissances en présence d’incertitude (WatDiv et LUBM). Nous avons aussi utilisé plusieurs Triplestores pour mener nos testsIn the era of digitilization, and with the emergence of several semantic Web applications, many new knowledge bases (KBs) are available on the Web. These KBs contain (named) entities and facts about these entities. They also contain the semantic classes of these entities and their mutual links. In addition, multiple KBs could be interconnected by their entities, forming the core of the linked data web. A distinctive feature of these KBs is that they contain millions to trillions of unreliable RDF triples. This uncertainty has multiple causes. It can result from the integration of data sources with various levels of intrinsic reliability or it can be caused by some considerations to preserve confidentiality. Furthermore, it may be due to factors related to the lack of information, the limits of measuring equipment or the evolution of information. The goal of this thesis is to improve the usability of modern systems aiming at exploiting uncertain KBs. In particular, this work proposes cooperative and intelligent techniques that could help the user in his decision-making when his query returns unsatisfactory results in terms of quantity or reliability. First, we address the problem of failing RDF queries (i.e., queries that result in an empty set of responses).This type of response is frustrating and does not meet the user’s expectations. The approach proposed to handle this problem is query-driven and offers a two fold advantage: (i) it provides the user with a rich explanation of the failure of his query by identifying the MFS (Minimal Failing Sub-queries) and (ii) it allows the computation of alternative queries called XSS (maXimal Succeeding Sub-queries), semantically close to the initial query, with non-empty answers. Moreover, from a user’s point of view, this solution offers a high level of flexibility given that several degrees of uncertainty can be simultaneously considered.In the second contribution, we study the dual problem to the above problem (i.e., queries whose execution results in a very large set of responses). Our solution aims at reducing this set of responses to enable their analysis by the user. Counterparts of MFS and XSS have been defined. They allow the identification, on the one hand, of the causes of the problem and, on the other hand, of alternative queries whose results are of reasonable size and therefore can be directly and easily used in the decision making process.All our propositions have been validated with a set of experiments on different uncertain and large-scale knowledge bases (WatDiv and LUBM). We have also used several Triplestores to conduct our tests
34
Boneva, Iovka. "Expressivité, satisfiabilité et model checking d'une logique spatiale pour arbres non ordonnés". Lille 1, 2006. https://ori-nuxeo.univ-lille1.fr/nuxeo/site/esupversions/dffac6b2-50d6-4e6d-9e4c-f8f5731c75e2.
Abstract (sommario):
Les structures arborescentes (arbres) sont largement étudiées en informatique. Les données semi-structurées en sont un récent champ d'application : il est admis que les arbres ordonnés d'arité non bornée sont un bon modèle pour ces données. Dans certains cas il est intéressant de considérer des arbres non ordonnés. Des formalismes logiques (logiques) sont utilisés pour décrire des requêtes ou vérifier des propriétés sur des données semi-structurées. Il est important d'identifier des logiques représentant un compromis entre expressivité et praticabilité des algorithmes. Des critères pertinents sont la satisfiabilité et la complexité du model checking de la logique. Nous étudions une logique spatiale, LS, qui est à la base d'un langage de requètes pour données semi-structurées modélisées par des arbres non ordonnés. La logique LS est très expressive, incluant des opérateurs spatiaux pour décrire localement la structure d'un arbre, un opérateur de point fixe et permettant de quantifier sur des étiquettes et sur des arbres. Nous établissons des résultats sur la satisfiabilité et la complexité du model checking pour différents fragments de LS. Nous identifions deux fragments syntaxiques de LS à satisfiabilité décidable, montrons que ces fragments sont équivalents aux logiques MSO et PMSO respectivement, et introduisons des classes d'automates d'arbres qui capturent ces deux fragments. Nous montrons que la complexité du mode! checking de LS est dans PSPACE-complet. Si seule la taille de l'arbre est prise en compte, la complexité du model checking va de linéaire à PSP ACE-complet pour les différents fragments de la logique.
35
Pech, Palacio Manuel Alfredo. "Spatial data modeling and mining using a graph-based representation". Lyon, INSA, 2005. http://theses.insa-lyon.fr/publication/2005ISAL0118/these.pdf.
Abstract (sommario):
Est proposé un unique modèle basé sur des graphes pour représenter des données spatiales, les données non-spatiales et les relations entre les objets spatiaux. Ainsi un graphe est généré à partir de ces trois éléments. On considère que l'outil de fouille de données basé sur les graphes peut découvrir des patterns incluant ces trois éléments, selon trois types de relation spatiale (topologique, cardinale et de distance). Dans notre modèle, les données spatiales, non-spatiales (attributs non-spatiaux), et les relations spatiales représentent une collections d'un ou plusieurs graphes orientés. Les sommets représentent soit les objets spatiaux, soit les relations spatiales entre deux objets spatiaux, ou les attributs non-spatiaux. De plus, un sommet peut représenter soit un attribut, soit le nom d'une relation spatiale. Les noms des attributs peuvent référencer des objets spatiaux ou non-spatiaux. Les arcs orientés sont utilisés pour représenter des informations directionnelles sur les relations entre les éléments, et pour décrire les attributs des objets. On a adopté SUBDUE comme un outil de fouille de graphes. Une caractéristique particulière dite de recouvrement joue un rôle important dans la découverte de patterns. Cependant, elle peut-être implémentée pour recouvrir la totalité du graphe, ou bien ne considérer aucun sommet. En conséquence, nous proposons une troisième piste nommée recouvrement limité, laquelle donne à l'utilisateur la capacité de choisir le recouvrement. On analyse directement trois caractéristiques de l'algorithme proposé, la réduction de l'espace de recherche, la réduction du temps de calcul, et la découverte de patterns grâce à ce type de recouvrementWe propose a unique graph-based model to represent spatial data, non-spatial data and the spatial relations among spatial objects. We will generate datasets composed of graphs with a set of these three elements. We consider that by mining a dataset with these characteristics a graph-based mining tool can search patterns involving all these elements at the same time improving the results of the spatial analysis task. A significant characteristic of spatial data is that the attributes of the neighbors of an object may have an influence on the object itself. So, we propose to include in the model three relationship types (topological, orientation, and distance relations). In the model the spatial data (i. E. Spatial objects), non-spatial data (i. E. Non-spatial attributes), and spatial relations are represented as a collection of one or more directed graphs. A directed graph contains a collection of vertices and edges representing all these elements. Vertices represent either spatial objects, spatial relations between two spatial objects (binary relation), or non-spatial attributes describing the spatial objects. Edges represent a link between two vertices of any type. According to the type of vertices that an edge joins, it can represent either an attribute name or a spatial relation name. The attribute name can refer to a spatial object or a non-spatial entity. We use directed edges to represent directional information of relations among elements (i. E. Object x touches object y) and to describe attributes about objects (i. E. Object x has attribute z). We propose to adopt the Subdue system, a general graph-based data mining system developed at the University of Texas at Arlington, as our mining tool. A special feature named overlap has a primary role in the substructures discovery process and consequently a direct impact over the generated results. However, it is currently implemented in an orthodox way: all or nothing. Therefore, we propose a third approach: limited overlap, which gives the user the capability to set over which vertices the overlap will be allowed. We visualize directly three motivations issues to propose the implementation of the new algorithm: search space reduction, processing time reduction, and specialized overlapping pattern oriented search
36
Chardain, Antoine. "Innovation et régulation : cas de l'accès aux données bancaires". Electronic Thesis or Diss., Aix-Marseille, 2022. http://www.theses.fr/2022AIXM0398.
Abstract (sommario):
L’accélération du rythme des innovations constitue un challenge pour les acteurs en charge de la régulation et de la supervision du secteur financier. La façon dont ils appréhendent l’innovation a des impacts bien au-delà du secteur financier, sur le quotidien des habitants, des organisations et des Etats. La régulation, par définition, vise à construire et maintenir des équilibres que l’innovation, par nature, vient bousculer. Dès lors, comment concilier innovation et régulation dans le contexte de la transformation numérique ? Cette thèse propose d’éclairer cette problématique à travers une étude de cas, celui de l’accès aux données bancaires par des acteurs non bancaires, au sein de l’Union européenne. Cette étude de cas unique, longitudinale, menée selon une méthodologie compréhensive, éclaire la problématique sous trois angles différents. La première analyse met en évidence les rôles des régulateurs et superviseurs, européens et nationaux, qui ont des impacts sur les temporalités d’une innovation. La seconde analyse se focalise sur la façon dont les technologies de l’information et de la communication sont prises en compte dans le processus d’élaboration d’une réglementation, au niveau de l’Union européenne. Enfin, la troisième analyse porte sur l'émergence des infrastructures numériques qui, à l’ère du numérique, assurent un rôle de coordination et de régulation qui leur confère un rôle stratégique dans les écosystèmes innovants et les plateformes numériques. Une grille d’analyse de l’émergence d’une infrastructure, basée sur l’analyse de l’état de légitimité et d’illégitimité de l’infrastructure aux yeux des différentes parties prenantes, est proposéeThe accelerating pace of innovation and digitalisation is a challenge for those responsible for regulating and supervising the financial sector. The way they approach innovation has impacts far beyond the financial sector, on the daily lives of people, organisations and states. Regulation, by definition, aims to build and maintain balances that innovation, by its nature, upsets. So how can innovation and regulation be reconciled in the context of digital transformation? This thesis proposes to shed light on this issue through a case study, the case of access to banking data by non-banking actors, within the European Union. This unique longitudinal case study, conducted according to a comprehensive methodology, sheds light on the issue from three different angles. The first analysis highlights the roles of European and national regulators and supervisors, which have an impact on the temporalities of an innovation. The second analysis focuses on the way in which information and communication technologies are taken into account in the regulatory process, at EU level. Finally, the third analysis focuses on digital infrastructures which, in the digital age, coordinate the actions and interactions of many actors in innovative ecosystems and digital platforms. An analysis grid of the emergence of an infrastructure, based on the analysis of the state of legitimacy and illegitimacy of the infrastructure in the eyes of the different stakeholders, is proposed
37
Vigny, Alexandre. "Query enumeration and nowhere dense graphs". Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCC211.
Abstract (sommario):
Les travaux présentés dans ma thèse se situent à l’interface entre complexité, algorithmique et logique. Plus particulièrement, on s’intéresse à la complexité d'évaluation de requêtes.Plus précisément, étant donné G un graphe fini. Une requête q définit un sous ensemble de k-uplets de sommets de G que l'on note q(G). On appelle k l'arité de q et on se essaye alors d'effectuer efficacement les taches suivantes :1) décider si l'ensemble q(G) est vide ou non.2) décider si un k-uplet donné appartient à l'ensemble des solutions q(G).3) calculer le nombre de solutions.4) énumérer les éléments de q(G).En ce qui concerne la 4ème tache, un algorithme qui va énumérer les solutions sera décomposé en deux parties. La première est appelé le pré-calcul et sert à préparer l’énumération. Idéalement cette étape de requière qu’un temps linéaire en la taille du graphe. La deuxième étape est ensuite l’énumération des solutions. Le temps nécessaire pour obtenir une nouvelle solution est appelé le délai. Idéalement on souhaite que le délai de dépende pas de la taille du graphes mais uniquement de la taille de la requête. On parle alors d’énumération à délai constant après pré-calcul linéaire.Au début de cette thèse, une grand part des interrogations au sujet des classes de graphes pour lesquelles une énumération à délai constant serait possible semblait se trouver au niveau des classes de graphes nulle-part dense. Le résultat principal de cette thèse est de montrer qu’il est possible d’énumérer les solutions des requêtes du premier ordre sur les graphes nulle-part dense avec un délai constant après un pré-calcul pseudo linéaireThe topic of my thesis lies between complexity, algorithmic and logic. In particular, we are interested in the complexity of evaluating query.More precisely, given G a finite graph. A query q defines a subset of k-tuples of vertices of G that we note q(G). We call k the arity of q and we then try to efficiently perform the following tasks:1) decide whether the set q G) is empty.2) decide whether a given k-tuplet belongs to the set of solutions q(G).3) calculate the number of solutions.4) enumerate the elements of q(G).Regarding the 4th task, an algorithm that will enumerate the solutions can be decomposed into two steps. The first is called preprocessing and is used to prepare the enumeration. Ideally this step only requires a time linear in the size of the graph. The second step is the enumeration properly speaking. The time needed to get a new solution is called the delay. Ideally we want the delay to not depend on the size of the graph but only on the size of the query. We then talk about constant delay enumeration after linear preprocessing.At the beginning of this thesis, a large part of the interrogations about classes of graphs for which a constant delay enumeration is possible seemed to be located around the classes of nowhere dense graphs
38
Djouadi, Yassine-Mansour. "Logique possibiliste & amélioration génétique pour la sélection et l'agencement d'objets cartographiques". Lyon 1, 1996. http://www.theses.fr/1996LYO10083.
Abstract (sommario):
Le probleme de selection et d'agencement d'objets spatiaux consiste a rechercher les objets les plus pertinents puis a les representer sur le support choisi compte tenu des contraintes que peut exiger une pareille visualisation. La pertinence de ces objets doit etre etablie de maniere graduelle afin de permettre une interrogation flexible. La selection d'objets dans les bases de donnees spatiales est generalement basee sur la notion de relation spatiale. Les relations spatiales permettent d'exprimer la topologie et la semantique. Il s'avere que ces relations peuvent presenter un caractere vague (flou) en ce qui concerne la topologie et presentent un caractere incertain en ce qui concerne la semantique. Aussi, la premiere partie de cette these consiste a proposer une approche pour la modelisation et l'analyse (manipulation) des connaissances spatiales vagues ou incertaines. Au niveau de la modelisation, la theorie des possibilites sera retenue pour representer les aspects incertain et vague conjointement. Tandis que nous proposerons l'extension de la logique du premier ordre a la logique possibiliste pour l'analyse des connaissances spatiales vagues ou incertaines. Au dela du probleme de selection d'objets, se pose le probleme de leur restitution. En effet, les resultats d'interrogation de bases de donnees spatiales doivent refleter la nature geometrique des informations manipulees et les concepts sous-jacents de geometrie et de topologie. D'autre part, la programmation logique contrainte proposee pour l'interrogation contrainte prend en charge une classe limitee de contraintes. Par consequent, les objets selectionnees peuvent ne pas satisfaire totalement les regles de placement. Notre proposition consiste a proposer une approche pour l'amelioration de l'agencement original des objets. Cette approche est base sur les algorithmes genetiques et constitue notre seconde contribution. Une variante d'algorithmes utilisant des probabilites adaptatives est proposee. La theorie des schemes sera utilisee pour valider l'approche proposee
39
Martel, Christian. "Développement d'un cadre théorique pour la gestion des représentations multiples dans les bases de données spatiales". Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape8/PQDD_0020/MQ49037.pdf.
40
Ingalalli, Vijay. "Querying and Mining Multigraphs". Thesis, Montpellier, 2017. http://www.theses.fr/2017MONTS080/document.
Abstract (sommario):
Avec des volumes de données et d’informations de plus en plus importants, des données de plus en plus complexes et fortement inter-reliées, l’extraction de connaissances reste un véritable défi. Les graphes offrent actuellement un support de représentation efficace pour représenter ces données. Parmi les approches existantes, les multi-graphes ont montré que leur pouvoir d’expression était particulièrement adapté pour manipuler des données complexes possédant de nombreux types de relations entre elles. Cette thèse aborde deux aspects principaux liés aux multigraphes : la recherche de sous graphes et la fouille de sous graphes fréquents dans des multigraphes.Elle propose trois propositions dans le domaines du requêtage et de la fouille de données.La première contribution s’inscrit dans la recherche de sous graphes et concerne l’isomorphisme de sous graphes dans des multigraphes. Cette approche peut, par exemple, être appliquée dans de nombreux domaines d’applications comme l’analyse d’images satellites ou de réseaux sociaux. Dans la seconde, nous nous intéressons aux graphes de connaissances et abordons la problématique de l’homorphisme de graphes dans des multigraphes RDF. Dans les deux contributions, nous proposons de nouvelles techniques d’indexations pour représenter efficacement les informations contenues dans les multigraphes. La recherche des sous graphes tire avantage de ces nouveaux index et différentes heuristiques et optimisations sont également proposées pour garantir de bonnes performances lors de l’exécution des requêtes. La seconde contribution s’inscrit dans le domaine de la fouille de données et nous proposons un algorithme efficace pour extraire les multigraphes fréquents. Etant donné l’espace de recherche à considérer, la recherche de motifs fréquents dans des graphes est un problème difficile en fouille de données. Pour parcourir efficacement l’espace de recherche encore plus volumineux pour les multigraphes, nous proposons de nouvelles techniques et méthodes pour le traverser efficacement notamment en éliminant des candidats où détectant à l’avance les motifs non fréquents. Pour chacune de ces propositions de nombreuses expérimentations sont réalisées pour valider à la fois leurs performances et exactitudes en les comparant avec les approches existantes. Finalement, nous proposons une étude de cas sur des jeux de données issues d’images satellites modélisées sous la forme de multigraphe et montrons que l’application de nos propositions permet de mettre en évidence de nouvelles connaissances utilesWith the ever-increasing growth of data and information, extracting the right knowledge has become a real challenge.Further, the advanced applications demand the analysis of complex, interrelated data which cannot be adequately described using a propositional representation. The graph representation is of great interest for the knowledge extraction community, since graphs are versatile data structures and are one of the most general forms of data representation. Among several classes of graphs, textit{multigraphs} have been captivating the attention in the recent times, thanks to their inherent property of succinctly representing the entities by allowing the rich and complex relations among them.The focus of this thesis is streamlined into two themes of knowledge extraction; one being textit{knowledge retrieval}, where we focus on the subgraph query matching aspects in multigraphs, and the other being textit{knowledge discovery}, where we focus on the problem of frequent pattern mining in multigraphs.This thesis makes three main contributions in the field of query matching and data mining.The first contribution, which is very generic, addresses querying subgraphs in multigraphs that yields isomorphic matches, and this problem finds potential applications in the domains of remote sensing, social networks, bioinformatics, chemical informatics. The second contribution, which is focussed on knowledge graphs, addresses querying subgraphs in RDF multigraphs that yield homomorphic matches. In both the contributions, we introduce efficient indexing structures that capture the multiedge information. The query matching processes introduced have been carefully optimized, w.r.t. the time performance and the heuristics employed assure robust performance.The third contribution is in the field of data mining, where we propose an efficient frequent pattern mining algorithm for multigraphs. We observe that multigraphs pose challenges while exploring the search space, and hence we introduce novel optimization techniques and heuristic search methods to swiftly traverse the search space.For each proposed approach, we perform extensive experimental analysis by comparing with the existing state-of-the-art approaches in order to validate the performance and correctness of our approaches.In the end, we perform a case study analysis on a remote sensing dataset. Remote sensing dataset is modelled as a multigraph, and the mining and query matching processes are employed to discover some useful knowledge
41
Roncancio, Claudia Lucia. "Règles actives et règles déductives dans les bases de données à objets". Université Joseph Fourier (Grenoble), 1994. http://www.theses.fr/1994GRE10240.
Abstract (sommario):
L'objectif de cette thèse est l'enrichissement d'un système de gestion de bases de données à objets (SGBDO) par l'intégration de certaines fonctions typiquement remplies par des langages de règles. Plus précisément, nous nous sommes intéressés à l'intégration de règles actives dans un système à objets, afin de lui conférer la capacité de réagir à des situations particulières. Nous avons travaillé cet aspect en profondeur et nous proposons un modèle de règles actives qui tient pleinement compte des spécificités du contexte objet. Nous avons étudié l'approche langage de programmation pour base de données (LPBD) et l'intégration des règles actives dans un tel langage. Ceci a été validé par l'application de notre modèle de règles au LPBD orienté objet Peplom, pour lequel nous proposons les éléments nécessaires à une intégration harmonieuse du point de vue du modèle de données, du langage proprement dit ainsi que de sa mise en œuvre. Ceci constitue la partie principale de notre travail. Une deuxième partie de cette thèse, plus prospective et complémentaire à la première, porte sur l'intégration de règles déductives dans ce même contexte. Nous nous intéressons ici à des règles propres aux bases de données déductives, dont le principal objectif est de fournir un langage à la fois déclaratif et puissant pour la déduction d'information. Ces caractéristiques, fortement appréciées pour la manipulation de données, sont absentes de la plupart des LPBD des systèmes à objets et ne sont pas non plus les traits essentiels des règles actives telles que nous les proposons. Face à cette constatation, nous proposons l'intégration d'un langage de règles déductives à un langage de programmation essentiellement impératif
42
Bousnina, Fatma Ezzahra. "Modeling and Querying Evidential Databases". Thesis, Chasseneuil-du-Poitou, Ecole nationale supérieure de mécanique et d'aérotechnique, 2019. http://www.theses.fr/2019ESMA0007/document.
Abstract (sommario):
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
43
Lambert, de Cambray Béatrix. "Etude de la modélisation de la manipulation et de la représentation de l'information spatiale tridimensionnelle dans les bases de données géographiques". Paris 6, 1994. http://www.theses.fr/1994PA066518.
Abstract (sommario):
De plus en plus de domaines d'application des systèmes d'information géographique ont besoin de gérer l'information spatiale 3D. Cette thèse traite la modélisation, la représentation et la manipulation de l'information spatiale 3D (c'est-à-dire de l'information géographique localisée dans un espace 3D) dans les bases de données géographiques. Cependant, les données saisies dans une base de données géographique peuvent être définies dans une dimension autre que 3D, bien qu'elles reflètent des données géographiques réelles qui sont, elles, situées dans un espace 3D. Afin de résoudre ce problème, cette thèse propose de modéliser les relations spatiales selon l'axe z entre objets géographiques. Ces relations permettent de plonger toute donnée géographique dans l'espace 3D. De plus, grâce à ces relations et aux descriptions géométriques, le modèle de manipulation de données est capable, pour chaque donnée, de dériver sa représentation à la dimension attendue par une opération spatiale à partir de celle stockée dans la base de données. Cette thèse propose un modèle de données multidimensionnel unifié qui intègre les données du relief (données 2. 5D) avec les données spatiales 2D et 3D. Elle propose aussi une extension du langage de requêtes sql aux données géographiques multidimensionnelles
44
Ba, Mouhamadou Lamine. "Exploitation de la structure des données incertaines". Electronic Thesis or Diss., Paris, ENST, 2015. http://www.theses.fr/2015ENST0013.
Abstract (sommario):
Cette thèse s’intéresse à certains problèmes fondamentaux découlant d’un besoin accru de gestion des incertitudes dans les applications Web multi-sources ayant de la structure, à savoir le contrôle de versions incertaines dans les plates-formes Web à large échelle, l’intégration de sources Web incertaines sous contraintes, et la découverte de la vérité à partir de plusieurs sources Web structurées. Ses contributions majeures sont : la gestion de l’incertitude dans le contrôle de versions de données arborescentes en s’appuyant sur un modèle XML probabiliste ; les étapes initiales vers un système d’intégration XML probabiliste de sources Web incertaines et dépendantes ; l’introduction de mesures de précision pour les données géographiques et ; la conception d’algorithmes d’exploration pour un partitionnement optimal de l’ensemble des attributs dans un processus de recherche de la vérité sur des sources Web conflictuellesThis thesis addresses some fundamental problems inherent to the need of uncertainty handling in multi-source Web applications with structured information, namely uncertain version control in Web-scale collaborative editing platforms, integration of uncertain Web sources under constraints, and truth finding over structured Web sources. Its major contributions are: uncertainty management in version control of treestructured data using a probabilistic XML model; initial steps towards a probabilistic XML data integration system for uncertain and dependent Web sources; precision measures for location data and; exploration algorithms for an optimal partitioning of the input attribute set during a truth finding process over conflicting Web sources
45
Pradel, Camille. "D'un langage de haut niveau à des requêtes graphes permettant d'interroger le web sémantique". Toulouse 3, 2013. http://thesesups.ups-tlse.fr/2237/.
Abstract (sommario):
Les modèles graphiques sont de bons candidats pour la représentation de connaissances sur le Web, où tout est graphes : du graphe de machines connectées via Internet au "Giant Global Graph" de Tim Berners-Lee, en passant par les triplets RDF et les ontologies. Dans ce contexte, le problème crucial de l'interrogation ontologique est le suivant : est-ce qu'une base de connaissances composée d'une partie terminologique et d'une partie assertionnelle implique la requête, autrement dit, existe-t-il une réponse à la question ? Ces dernières années, des logiques de description ont été proposées dans lesquelles l'expressivité de l'ontologie est réduite de façon à rendre l'interrogation calculable (familles DL-Lite et EL). OWL 2 restreint OWL-DL dans ce sens en se fondant sur ces familles. Nous nous inscrivons dans le contexte d'utilisation de formalismes graphiques pour la représentation (RDF, RDFS et OWL) et l'interrogation (SPARQL) de connaissances. Alors que les langages d'interrogation fondés sur des graphes sont présentés par leurs promoteurs comme étant naturels et intuitifs, les utilisateurs ne pensent pas leurs requêtes en termes de graphes. Les utilisateurs souhaitent des langages simples, proches de la langue naturelle, voire limités à des mots-clés. Nous proposons de définir un moyen générique permettant de transformer une requête exprimée en langue naturelle vers une requête exprimée dans le langage de graphe SPARQL, à l'aide de patrons de requêtes. Le début de ce travail coïncide avec les actions actuelles du W3C visant à préparer une nouvelle version de RDF, ainsi qu'avec le processus de standardisation de SPARQL 1. 1 gérant l'implication dans les requêtesGraph models are suitable candidates for KR on the Web, where everything is a graph, from the graph of machines connected to the Internet, the "Giant Global Graph" as described by Tim Berners-Lee, to RDF graphs and ontologies. In that context, the ontological query answering problem is the following: given a knowledge base composed of a terminological component and an assertional component and a query, does the knowledge base implies the query, i. E. Is there an answer to the query in the knowledge base? Recently, new description logic languages have been proposed where the ontological expressivity is restricted so that query answering becomes tractable. The most prominent members are the DL-Lite and the EL families. In the same way, the OWL-DL language has been restricted and this has led to OWL2, based on the DL-Lite and EL families. We work in the framework of using graph formalisms for knowledge representation (RDF, RDF-S and OWL) and interrogation (SPARQL). Even if interrogation languages based on graphs have long been presented as a natural and intuitive way of expressing information needs, end-users do not think their queries in terms of graphs. They need simple languages that are as close as possible to natural language, or at least mainly limited to keywords. We propose to define a generic way of translating a query expressed in a high-level language into the SPARQL query language, by means of query patterns. The beginning of this work coincides with the current activity of the W3C that launches an initiative to prepare a possible new version of RDF and is in the process of standardizing SPARQL 1. 1 with entailments
46
François, Hélène. "Synthèse de la parole par concaténation d'unités acoustiques : construction et exploitation d'une base de parole continue". Rennes 1, 2002. http://www.theses.fr/2002REN10127.
Abstract (sommario):
Ces travaux s'inscrivent dans le cadre de la synthèse de la parole par concaténation d'unités acoustiques de taille variable multi-représentées. Pour remédier à l'hétérogénéité de la qualité et de l'intelligibilité des voix synthétiques, nous utilisons une base de parole continue riche au niveau linguistique, ici un jeu de phrases naturelles. Sa construction est vue comme un problème NP-complet de recouvrement minimal d'ensemble. Les méthodes gloutonne, cracheuse et d'échange par paire condensent ainsi des corpus de 100000 à 5000 phrases. Ensuite nous cherchons dans un corpus spécifique l'ensemble des séquences d'unités acoustiques permettant la synthèse de 10 phrases tests. Pour chaque séquence trouvée ses unités sont concaténées, puis sa qualité est évaluée de façon objective en mesurant sa distance acoustique à une référence naturelle. Cela permet de spécifier et de caractériser des bases "génératives", de développer et d'évaluer de nouvelles méthodes de sélection d'unités.
47
Moreau, Aurélien. "How fuzzy set theory can help make database systems more cooperative". Thesis, Rennes 1, 2018. http://www.theses.fr/2018REN1S043/document.
Abstract (sommario):
Dans ces travaux de thèse nous proposons de tirer parti de la théorie des ensembles flous afin d'améliorer les interactions entre les systèmes de bases de données et les utilisateurs. Les mécanismes coopératifs visent à aider les utilisateurs à mieux interagir avec les SGBD. Ces mécanismes doivent faire preuve de robustesse : ils doivent toujours pouvoir proposer des réponses à l'utilisateur. Empty set (0,00 sec) est un exemple typique de réponse qu'il serait désirable d'éradiquer. Le caractère informatif des explications de réponses est parfois plus important que les réponses elles-mêmes : ce peut être le cas avec les réponses vides et pléthoriques par exemple, d'où l'intérêt de mécanismes coopératifs robustes, capables à la fois de contribuer à l'explication ainsi qu'à l'amélioration des résultats. Par ailleurs, l'utilisation de termes de la langue naturelle pour décrire les données permet de garantir l'interprétabilité des explications fournies. Permettre à l'utilisateur d'utiliser des mots de son propre vocabulaire contribue à la personnalisation des explications et améliore l'interprétabilité. Nous proposons de nous intéresser aux explications dans le contexte des réponses coopératives sous trois angles : 1) dans le cas d'un ensemble pléthorique de résultats ; 2) dans le contexte des systèmes de recommandation ; 3) dans le cas d'une recherche à partir d'exemples. Ces axes définissent des approches coopératives où l'intérêt des explications est de permettre à l'utilisateur de comprendre comment sont calculés les résultats proposés dans un effort de transparence. Le caractère informatif des explications apporte une valeur ajoutée aux résultats bruts, et forme une réponse coopérativeIn this thesis, we are interested in how we can leverage fuzzy logic to improve the interactions between relational database systems and humans. Cooperative answering techniques aim to help users harness the potential of DBMSs. These techniques are expected to be robust and always provide answer to users. Empty set (0,00 sec) is a typical example of answer that one may wish to never obtain. The informative nature of explanations is higher than that of actual answers in several cases, e.g. empty answer sets and plethoric answer sets, hence the interest of robust cooperative answering techniques capable of both explaining and improving an answer set. Using terms from natural language to describe data --- with labels from fuzzy vocabularies --- contributes to the interpretability of explanations. Offering to define and refine vocabulary terms increases the personalization experience and improves the interpretability by using the user's own words. We propose to investigate the use of explanations in a cooperative answering setting using three research axes: 1) in the presence of a plethoric set of answers; 2) in the context of recommendations; 3) in the context of a query/answering problem. These axes define cooperative techniques where the interest of explanations is to enable users to understand how results are computed in an effort of transparency. The informativeness of the explanations brings an added value to the direct results, and that in itself represents a cooperative answer
48
Abbaci, Katia. "Contribution à l'interrogation flexible et personnalisée d'objets complexes modélisés par des graphes". Thesis, Rennes 1, 2013. http://www.theses.fr/2013REN1S105/document.
Abstract (sommario):
Plusieurs domaines d'application traitent des objets et des données complexes dont la structure et la sémantique de leurs composants sont des informations importantes pour leur manipulation et leur exploitation. La structure de graphe a été bien souvent adoptée, comme modèles de représentation, dans ces domaines. Elle permet de véhiculer un maximum d'informations, liées à la structure, la sémantique et au comportement de ces objets, nécessaires pour assurer une meilleure représentation et une manipulation efficace. Ainsi, lors d'une comparaison entre deux objets complexes, l'opération d'appariement est appliquée entre les graphes les modélisant. Nous nous sommes intéressés dans cette thèse à l'appariement approximatif qui permet de sélectionner les graphes les plus similaires au graphe d'une requête. L'objectif de notre travail est de contribuer à l'interrogation flexible et personnalisée d'objets complexes modélisés sous forme de graphes pour identifier les graphes les plus pertinents aux besoins de l'utilisateur, exprimés d'une manière partielle ou imprécise. Dans un premier temps, nous avons proposé un cadre de sélection de services Web modélisés sous forme de graphes qui permet (i) d'améliorer le processus d'appariement en intégrant les préférences des utilisateurs et l'aspect structurel des graphes comparés, et (ii) de retourner les services les plus pertinents. Une deuxième méthode d'évaluation de requêtes de recherche de graphes par similarité a également été présentée pour calculer le skyline de graphes d'une requête utilisateur en tenant compte de plusieurs mesures de distance de graphes. Enfin, des approches de raffinement ont été définies pour réduire la taille, souvent importante, du skyline. Elles ont pour but d'identifier et d'ordonner les points skyline qui répondent le mieux à la requête de l'utilisateurSeveral application domains deal with complex objects whose structure and semantics of their components are crucial for their handling. For this, graph structure has been adopted, as a model of representation, in these areas to capture a maximum of information, related to the structure, semantics and behavior of such objects, necessary for effective representation and processing. Thus, when comparing two complex objects, a matching technique is applied between their graph structures. In this thesis, we are interested in approximate matching techniques which constitute suitable tools to automatically find and select the most similar graphs to user graph query. The aim of our work is to develop methods to personalized and flexible querying of repositories of complex objects modeled thanks to graphs and then to return the graphs results that fit best the users ’needs, often expressed partially and in an imprecise way. In a first time, we propose a flexible approach for Web service retrieval that relies both on preference satisfiability and structural similarity between process model graphs. This approach allows (i) to improve the matching process by integrating user preferences and the graph structural aspect, and (ii) to return the most relevant services. A second method for evaluating graph similarity queries is also presented. It retrieves graph similarity skyline of a user query by considering a vector of several graph distance measures instead of a single measure. Thus, graphs which are maximally similar to graph query are returned in an ordered way. Finally, refinement methods have been developed to reduce the size of the skyline when it is of a significant size. They aim to identify and order skyline points that match best the user query
49
Dachelet, Roland. "Sur la notion de sous-langage". Paris 8, 1994. http://www.theses.fr/1994PA080968.
Abstract (sommario):
La notion de sous-langage prend place dans la theorie linguistique de z. S. Harris. Parmi les souslangages, les sous-langages de domaine accueillent l'expression des sciences, dont la linguistique ou, specifiquement, la metalangue est interne a son objet. Un sous-langage incarne une vision de la semantique tres differente de la semantique classique. Nous illustrons ce point dans le cadre de la relation entre langage et base de donnees. Nous prenons comme supports une technologie : les interfaces en langage naturel a des bases de donnees, et un probleme ergonomique : la caracterisation de l'univers de discours des utilisateurs de tels systemes. Le premier chapitre presente les bases de donnees relationnelles, l'approche logique et les modeles semantiques associes. Le second chapitre presente les interfaces en langage naturel parmi lesquelles les interfaces a grammaire semantique. Le troisieme chapitre est consacre a une presentation de la notion de sous-langage et de sa place dans la la theorie du langage de harris. Au chapitre 4, nous presentons la base de donnees reelle qui sert de support a notre etude. Nous associons au schema entite-association de cette base un ensemble de formules de type sous-langage et a ces formules, un ensemble d'items langagier. La chapitre 5 presente un corpus de requetes, ses emetteurs et ses condtions de production. Au chapitre 6, nous procedons a une analyse du corpus par les methodes de l'analyse des sous-langages. Nous montrons que les formules derivables de ce corpus sont tres peu nombreuses, qu'elles se repartissent en deux groupes et qu'elles vehiculent un univers de discours different de celui de la base de donnees. Au chapitre 7, nous confrontons la conception de la semantique qui s'incarne dans la notion de sous-langage avec celle qui inspire le semantique classique. Nous montrons quelle rupture la theorie harrissienne introduit dans le champ linguistiqueThe notion of sublanguage is part of z. S. Harris's linguistic theory. Among sublanguages, domain sublanguages enable to express sciences, one of them being linguistics where, specifically, metalanguage is internal to its object. Sublanguages embody a vision of semantics well different from classical semantics. This point is illustrated within the framework of the relationship between language and databases as one can see it through a technology : natural language database front-ends and an ergonomic problem : characterizing the universe of discourse of such systems users. In the first chapter we present relational databases, their associated logical approach and semantic models. In the second chapter we present natural language front-ends, in particular the semantic grammar type. The third chapter is devoted to a presentation of the notion of sublanguage and of its place within harris's theory of language. In chapter 4, we present the particular database on which the study is based. To the entity-relationship schema, we associate a set of sublanguage-type formulas, and to the formulas, a set of language items. In chapter 5, we present a query corpus and its production conditions. In chapter 6, we analyze the corpus using the sublanguage analysis methods. We show that the derived formulas are very few, that they fall into two classes, and that they express a universe of discourse different from the database one. In chapter 7, we compare semantics as it is embodied in the notion of sublanguage with classical semantics. We show that harriss's theory breaks-up conceptions most commonly taken for granted in the linguistic field
50
Conde, Cespedes Patricia. "Modélisations et extensions du formalisme de l'analyse relationnelle mathématique à la modularisation des grands graphes". Paris 6, 2013. http://www.theses.fr/2013PA066654.
Abstract (sommario):
Un graphe étant un ensemble d'objets liés par une certaine relation typée, le problème de "modularisation" des grands graphes (qui revient à leur partitionnement en classes) peut, alors, être modélisé mathématiquement en utilisant l'Analyse Relationnelle. Cette modélisation permet de comparer sur les mêmes bases un certain nombre de critères de découpage de graphe c'est-à-dire de modularisation. Nous proposons une réécriture Relationnelle des critères de modularisation connus tels le critère de Newman-Girvan, Zahn-Condorcet, Owsinski-Zadrozny, Condorcet pondéré, Demaine-Immorlica, Wei-Cheng, la Différence de profils et Michalski-Goldberg. Nous introduisons trois critères : la Modularité équilibrée, l'écart à l'Indétermination et l'écart à l'Uniformité. Nous identifions les propriétés vérifiées par ces critères et pour certains critères, notamment les critères linéaires, nous caractérisons les partitions obtenues via leur optimisation dans le but de faciliter leur compréhension et d'interpréter plus clairement leurs finalités en y associant la preuve de leur utilité dans certains contextes pratiques. Les résultats trouvés sont testés sur des graphes réels de tailles différentes avec l'algorithme de Louvain génériqueGraphs are the mathematical representation of networks. Since a graph is a special type of binary relation, graph clustering (or modularization), can be mathematically modelled using the Mathematical Relational analysis. This modelling allows to compare numerous graph clustering criteria on the same type of formal representation. We give through a relational coding, the way of comparing different modularization criteria such as: Newman-Girvan, Zahn-Condorcet, Owsinski-Zadrozny, Demaine-Immorlica, Wei-Cheng, Profile Difference et Michalski-Goldberg. We introduce three modularization criteria: the Balanced Modularity, the deviation to Indetermination and the deviation to Uniformity. We identify the properties verified by those criteria and for some of those criteria, specially linear criteria, we characterize the partitions obtained by the optimization of these criteria. The final goal is to facilitate their understanding and their usefulness in some practical contexts, where their purposes become easily interpretable and understandable. Our results are tested by modularizing real networks of different sizes with the generalized Louvain algorithm