Дисертації з теми "Données Transactionnelles"

Les architectures multicœurs changent notre façon d'écrire des programmes. L'écriture de programmes concurrents est bien connue pour être difficile. Traditionnellement, l'utilisation de verrous (locks) permettant au code de s'exécuter en exclusion mutuelle, a été l'abstraction la plus largement utilisée pour l'écriture des programmes concurrents. Malheureusement, il est difficile d'écrire des programmes concurrents efficaces et corrects reposant sur des verrous. En outre, les verrous présentent d'autres problèmes, notamment celui du passage à l'échelle. Le concept de mémoire transactionnelle a été proposé comme une solution à ces difficultés. Les transactions peuvent être considérées comme une abstraction de haut niveau, ou une méthodologie pour l'écriture de programmes concurrents, ce qui permet au programmeur de pouvoir déclarer des sections de code devant être exécutés de façon atomique, sans avoir à se soucier des détails de synchronisation. Malheureusement, bien qu'assurément plus facile à utiliser que les verrous, la mémoire transactionnelle souffre encore de problèmes de performance et de facilité d'utilisation. En fait, de nombreux concepts relatifs à l'utilisation et à la sémantique des transactions n'ont pas encore des normes convenues. Cette thèse propose de nouvelles solutions permettant de faciliter l'utilisation des mémoires transactionellles. La thèse débute par un chapitre qui donne un bref aperçu de la mémoire transactionnelle logicielle (STM) ainsi qu'une discussion sur le problème de la facilité d'utilisation. Les contributions à la recherche sont ensuite divisées en quatre chapitres principaux, chacun proposant une approche différente afin de rendre les STMs plus facile à utiliser.

Les algorithmes actuels pour la fouille d’ensembles fréquents sont dépassés par l’augmentation des volumes de données. Dans cette thèse nous nous intéressons plus particulièrement aux données transactionnelles (des collections d’ensembles d’objets, par exemple des tickets de caisse) qui contiennent au moins un million de transactions portant sur au moins des centaines de milliers d’objets. Les jeux de données de cette taille suivent généralement une distribution dite en "longue traine": alors que quelques objets sont très fréquents, la plupart sont rares. Ces distributions sont le plus souvent tronquées par les algorithmes de fouille d’ensembles fréquents, dont les résultats ne portent que sur une infime partie des objets disponibles (les plus fréquents). Les méthodes existantes ne permettent donc pas de découvrir des associations concises et pertinentes au sein d’un grand jeu de données. Nous proposons donc une nouvelle sémantique, plus intuitive pour l’analyste: parcourir les associations par objet, au plus une centaine à la fois, et ce pour chaque objet présent dans les données.Afin de parvenir à couvrir tous les objets, notre première contribution consiste à définir la fouille centrée sur les objets. Cela consiste à calculer, pour chaque objet trouvé dans les données, les k ensembles d’objets les plus fréquents qui le contiennent. Nous présentons un algorithme effectuant ce calcul, TopPI. Nous montrons que TopPI calcule efficacement des résultats intéressants sur nos jeux de données. Il est plus performant que des solutions naives ou des émulations reposant sur des algorithms existants, aussi bien en termes de rapidité que de complétude des résultats. Nous décrivons et expérimentons deux versions parallèles de TopPI (l’une sur des machines multi-coeurs, l’autre sur des grappes Hadoop) qui permettent d’accélerer le calcul à grande échelle.Notre seconde contribution est CAPA, un système permettant d’étudier quelle mesure de qualité des règles d’association serait la plus appropriée pour trier nos résultats. Cela s’applique aussi bien aux résultats issus de TopPI que de jLCM, notre implémentation d’un algorithme récent de fouille d’ensembles fréquents fermés (LCM). Notre étude quantitative montre que les 39 mesures que nous comparons peuvent être regroupées en 5 familles, d’après la similarité des classements de règles qu’elles produisent. Nous invitons aussi des experts en marketing à participer à une étude qualitative, afin de déterminer laquelle des 5 familles que nous proposons met en avant les associations d’objets les plus pertinentes dans leur domaine.Notre collaboration avec Intermarché, partenaire industriel dans le cadre du projet Datalyse, nous permet de présenter des expériences complètes et portant sur des données réelles issues de supermarchés dans toute la France. Nous décrivons un flux d’analyse complet, à même de répondre à cette application. Nous présentons également des expériences portant sur des données issues d’Internet; grâce à la généricité du modèle des ensembles d’objets, nos contributions peuvent s’appliquer dans d’autres domaines.Nos contributions permettent donc aux analystes de découvrir des associations d’objets au milieu de grandes masses de données. Nos travaux ouvrent aussi la voie vers la fouille d’associations interactive à large échelle, afin d’analyser des données hautement dynamiques ou de réduire la portion du fichier à analyser à celle qui intéresse le plus l’analyste
The recent increase of data volumes raises new challenges for itemset mining algorithms. In this thesis, we focus on transactional datasets (collections of items sets, for example supermarket tickets) containing at least a million transactions over hundreds of thousands items. These datasets usually follow a "long tail" distribution: a few items are very frequent, and most items appear rarely. Such distributions are often truncated by existing itemset mining algorithms, whose results concern only a very small portion of the available items (the most frequents, usually). Thus, existing methods fail to concisely provide relevant insights on large datasets. We therefore introduce a new semantics which is more intuitive for the analyst: browsing associations per item, for any item, and less than a hundred associations at once.To address the items' coverage challenge, our first contribution is the item-centric mining problem. It consists in computing, for each item in the dataset, the k most frequent closed itemsets containing this item. We present an algorithm to solve it, TopPI. We show that TopPI computes efficiently interesting results over our datasets, outperforming simpler solutions or emulations based on existing algorithms, both in terms of run-time and result completeness. We also show and empirically validate how TopPI can be parallelized, on multi-core machines and on Hadoop clusters, in order to speed-up computation on large scale datasets.Our second contribution is CAPA, a framework allowing us to study which existing measures of association rules' quality are relevant to rank results. This concerns results obtained from TopPI or from jLCM, our implementation of a state-of-the-art frequent closed itemsets mining algorithm (LCM). Our quantitative study shows that the 39 quality measures we compare can be grouped into 5 families, based on the similarity of the rankings they produce. We also involve marketing experts in a qualitative study, in order to discover which of the 5 families we propose highlights the most interesting associations for their domain.Our close collaboration with Intermarché, one of our industrial partners in the Datalyse project, allows us to show extensive experiments on real, nation-wide supermarket data. We present a complete analytics workflow addressing this use case. We also experiment on Web data. Our contributions can be relevant in various other fields, thanks to the genericity of transactional datasets.Altogether our contributions allow analysts to discover associations of interest in modern datasets. We pave the way for a more reactive discovery of items' associations in large-scale datasets, whether on highly dynamic data or for interactive exploration systems

Les données numériques jouent un rôle crucial dans notre vie quotidienne en communiquant, en enregistrant des informations, en exprimant nos pensées et nos opinions et en capturant nos moments précieux sous forme d'images et de vidéos numériques. Les données numériques présentent d'énormes avantages dans tous les aspects de la vie moderne, mais constituent également une menace pour notre vie privée. Dans cette thèse, nous considérons trois types de données numériques en ligne générées par les utilisateurs des médias sociaux et les clients du commerce électronique : les graphiques, les transactions et les images. Les graphiques sont des enregistrements des interactions entre les utilisateurs qui aident les entreprises à comprendre qui sont les utilisateurs influents dans leur environnement. Les photos postées sur les réseaux sociaux sont une source importante de données qui nécessitent des efforts d'extraction. Les ensembles de données transactionnelles représentent les opérations qui ont eu lieu sur les services de commerce électronique.Nous nous appuyons sur une technique de préservation de la vie privée appelée Differential Privacy (DP) et sa généralisation Blowfish Privacy (BP) pour proposer plusieurs solutions permettant aux propriétaires de données de bénéficier de leurs ensembles de données sans risque de violation de la vie privée pouvant entraîner des problèmes juridiques. Ces techniques sont basées sur l'idée de récupérer l'existence ou la non-existence de tout élément dans l'ensemble de données (tuple, ligne, bord, nœud, image, vecteur, ...) en ajoutant respectivement un petit bruit sur la sortie pour fournir un bon équilibre entre intimité et utilité.Dans le premier cas d'utilisation, nous nous concentrons sur les graphes en proposant trois mécanismes différents pour protéger les données personnelles des utilisateurs avant d'analyser les jeux de données. Pour le premier mécanisme, nous présentons un scénario pour protéger les connexions entre les utilisateurs avec une nouvelle approche où les utilisateurs ont des privilèges différents : les utilisateurs VIP ont besoin d'un niveau de confidentialité plus élevé que les utilisateurs standard. Le scénario du deuxième mécanisme est centré sur la protection d'un groupe de personnes (sous-graphes) au lieu de nœuds ou d'arêtes dans un type de graphes plus avancé appelé graphes dynamiques où les nœuds et les arêtes peuvent changer à chaque intervalle de temps. Dans le troisième scénario, nous continuons à nous concentrer sur les graphiques dynamiques, mais cette fois, les adversaires sont plus agressifs que les deux derniers scénarios car ils plantent de faux comptes dans les graphiques dynamiques pour se connecter à des utilisateurs honnêtes et essayer de révéler leurs nœuds représentatifs dans le graphique.Dans le deuxième cas d'utilisation, nous contribuons dans le domaine des données transactionnelles en présentant un mécanisme existant appelé Safe Grouping. Il repose sur le regroupement des tuples de manière à masquer les corrélations entre eux que l'adversaire pourrait utiliser pour violer la vie privée des utilisateurs. D'un autre côté, ces corrélations sont importantes pour les propriétaires de données dans l'analyse des données pour comprendre qui pourrait être intéressé par des produits, biens ou services similaires. Pour cette raison, nous proposons un nouveau mécanisme qui expose ces corrélations dans de tels ensembles de données, et nous prouvons que le niveau de confidentialité est similaire au niveau fourni par Safe Grouping.Le troisième cas d'usage concerne les images postées par les utilisateurs sur les réseaux sociaux. Nous proposons un mécanisme de préservation de la confidentialité qui permet aux propriétaires des données de classer les éléments des photos sans révéler d'informations sensibles. Nous présentons un scénario d'extraction des sentiments sur les visages en interdisant aux adversaires de reconnaître l'identité des personnes
Digital data is playing crucial role in our daily life in communicating, saving information, expressing our thoughts and opinions and capturing our precious moments as digital pictures and videos. Digital data has enormous benefits in all the aspects of modern life but forms also a threat to our privacy. In this thesis, we consider three types of online digital data generated by users of social media and e-commerce customers: graphs, transactional, and images. The graphs are records of the interactions between users that help the companies understand who are the influential users in their surroundings. The photos posted on social networks are an important source of data that need efforts to extract. The transactional datasets represent the operations that occurred on e-commerce services.We rely on a privacy-preserving technique called Differential Privacy (DP) and its generalization Blowfish Privacy (BP) to propose several solutions for the data owners to benefit from their datasets without the risk of privacy breach that could lead to legal issues. These techniques are based on the idea of recovering the existence or non-existence of any element in the dataset (tuple, row, edge, node, image, vector, ...) by adding respectively small noise on the output to provide a good balance between privacy and utility.In the first use case, we focus on the graphs by proposing three different mechanisms to protect the users' personal data before analyzing the datasets. For the first mechanism, we present a scenario to protect the connections between users (the edges in the graph) with a new approach where the users have different privileges: the VIP users need a higher level of privacy than standard users. The scenario for the second mechanism is centered on protecting a group of people (subgraphs) instead of nodes or edges in a more advanced type of graphs called dynamic graphs where the nodes and the edges might change in each time interval. In the third scenario, we keep focusing on dynamic graphs, but this time the adversaries are more aggressive than the past two scenarios as they are planting fake accounts in the dynamic graphs to connect to honest users and try to reveal their representative nodes in the graph. In the second use case, we contribute in the domain of transactional data by presenting an existed mechanism called Safe Grouping. It relies on grouping the tuples in such a way that hides the correlations between them that the adversary could use to breach the privacy of the users. On the other side, these correlations are important for the data owners in analyzing the data to understand who might be interested in similar products, goods or services. For this reason, we propose a new mechanism that exposes these correlations in such datasets, and we prove that the level of privacy is similar to the level provided by Safe Grouping.The third use-case concerns the images posted by users on social networks. We propose a privacy-preserving mechanism that allows the data owners to classify the elements in the photos without revealing sensitive information. We present a scenario of extracting the sentiments on the faces with forbidding the adversaries from recognizing the identity of the persons. For each use-case, we present the results of the experiments that prove that our algorithms can provide a good balance between privacy and utility and that they outperform existing solutions at least in one of these two concepts

Nous étudions le problème de spécifier opérationnellement les contraintes dynamiques d'une base de données dans le cadre du modèle relationnel. Plus exactement, étant donné un ensemble de contraintes dynamiques nous cherchons à trouver un ensemble d'opérations avec lesquelles on puisse générer toutes les suites d'états satisfaisant ces contraintes. Dans cette étude, nous nous restreignons à des classes particulières de contraintes, à savoir les dépendances dynamiques d'antériorité et les dépendances dynamiques de transition. Ce qui caractérise la première classe est le fait que leur vérification exige que des états non nécessairement consécutifs de la base soient comparés tandis que pour la deuxième classe, la vérification consiste à examiner des états consécutifs. Nous introduisons une sous-classe assez large de dépendances dynamiques d'antériorité que nous appelons les dépendances dynamiques algébriques (ddas). Ces dépendances expriment des restrictions du type: si une propriété p est vérifiée à l'état présent alors une autre propriété q doit avoir été vérifiée dans un état précédent. Dans un premier temps, nous introduisons une notion de spécification procédurale basée sur le concept de schéma transactionnel de Abiteboul & Vianu. Nous montrons que cette notion est inadéquate pour résoudre le problème proposé. Au vu de ce résultat négatif nous sommes amenés à généraliser la notion de schéma transactionnel en introduisant les schémas transactionnels généralisés qui utilisent en plus d'un ensemble de transactions t une expression régulière e ayant comme alphabet t et qui va spécifier les bonnes suites de transactions pour passer d'un état à l'autre. Avec cette notion, Nous obtenons une spécification procédurale équivalente à un ensemble de ddas. Les techniques utilisées pour montrer cette équivalence sont appliquées pour spécifier opérationnellement une sous-classe de dépendances dynamiques de transition, les dépendances fonctionnelles dynamiques.

Les moyens offerts par les systèmes de gestion de base de données et les systèmes transactionnels pour maintenir la cohérence et l'intégrité des systèmes d'information sont tout d'abord analysés tant en centralisé qu'en réparti. La seconde partie est consacrée à l'étude de deux grandes classes de méthodes de conception, l'une fondée sur les modèles de description de données, l'autre sur les types abstraits. Dans chaque cas, une méthode particulière est présentée et analysée. Après présentation de l'application bancaire pilote, la troisième partie définit un modèle pour la description des applications transactionnelles. Celui-ci est appliqué et confronté à l'application pilote. La dernière partie décrit la réalisation de ce modèle dans le langage ADA. Un environnement de conception est construit et se présente comme un sur-ensemble du langage ADA. Enfin, cet outil est comparé à d'autres propositions du domaine de la recherche

Les transactions, la duplication et les communications de groupes sont des outils importants pour la réalisation d'applications réparties, tolérant les défaillances et devant respecter des contraintes de cohérence de données. Cette thèse traite de la duplication de données dans un cadre transactionnel en utilisant la communication de groupes. Nous nous intéressons à un nouveau modèle de duplication partielle ou chaque objet est dupliqué de manière indépendante sur un groupe de processus particulier. Sur ce modèle nous proposons un protocole de contrôle de duplication qui assure la sérialisibilité à une copie des transactions et la validation atomique non-bloquante de celles-ci. Par ailleurs, nous présentons deux variantes de ce protocole qui évitent les interblocages de transactions. L'une des variantes ne provoque jamais l'annulation de transactions en écriture seule. L'autre n'annule jamais de transactions en lecture seule. On garantit que toutes les transactions ne sont pas annulées. Ces protocoles reposent sur deux primitives de diffusion, la diffusion fiable uniforme et la diffusion fiable totalement ordonnée (ou diffusion atomique) dans plusieurs groupes. Nous proposons aussi un protocole de diffusion fiable totalement ordonnée. Cette primitive assure la fiabilité des livraisons des messages et garantit également que ces livraisons respectent un ordre total. Elle repose sur une primitive de consensus uniforme. En outre,l'algorithme possède les propriétés suivantes : la minimalité qui garantit que seuls le processus émetteur et les processus des groupes destinataires d'un message sont impliques dans sa diffusion et sa livraison ; et la localité qui exprime le fait qu'une éxecution de consensus ne concerne qu'un seul groupe de processus. Finalement nous décrivons une maquette mettant en oeuvre ce protocole et présentons une étude de ses performances.

Cette thèse propose des solutions pour mettre en oeuvre, de manière flexible et performante, le stockage et les manipulations transactionnels d'une base de données déductive à objets (dood) ; elle s'inscrit dans le développement du système validity. Outre une analyse et une synthèse de l'état de l'art, nos travaux comportent une validation pratique par la réalisation d'un véritable système de stockage et par son évaluation à l'aide d'un ensemble de mesures de performance. Nous exposons les principes dood et leurs impacts fonctionnels, transactionnels et opérationnels : les convergences et les divergences avec les modèles relationnel et objet sont approfondies. Deux axes principaux sont ensuite étudiés : (1) une synthèse des mécanismes de gestion de la mémoire persistante (organisation sur les supports physiques, contrôle des caches et stratégie de reprise) assurant l'atomicité et la durabilité des écritures, (2) le protocole original rc2pl intégrant le verrouillage a deux phases (2pl) et l'ordonnancement par multiversion pour isoler les transactions. Rc2pl décompose les transactions en deux phases : une phase de mise à jour (lectures et écritures) isolée par verrouillage, suivie d'une phase de vérification (lectures seulement) isolée par multiversion. Ainsi, rc2pl assure une isolation stricte et non conflictuelle des lectures exécutées en fin de transaction pour vérifier les contraintes d'intégrité sans pénaliser la concurrence. L'algorithme, la correction et les techniques de mises en oeuvre sont détaillés. Finalement, nous comparons les performances de rc2pl avec les différentes stratégies de vérification sous 2pl (avant, pendant et après les écritures). Les résultats démontrent que rc2pl réduit le nombre de conflits : la verification des contraintes d'integrité déclaratives après les écritures sous rc2pl offre des performances comparables à la meilleure optimisation des vérifications programmées à la main dans les applications sous 2pl.

Cette these s'inscrit dans le cadre de la reprise dans les systemes transactionnels exploitant la semantique des operations typees. Le travail a consiste a: etendre les histoires produites par les differents controles de concurrence (exploitant les proprietes de commutativite et de recouvrabilite relative des operations typees) pour tenir compte du rejet apres faute et de la reprise ; classer ces histoires en fonction du degres de concurrence que les protocoles permettent d'obtenir ; proposer, en partant du systeme de reprise aries, des algorithmes de rejet et de reprise adaptes a chaque histoire ; fournir les bases pour integrer, dans le modele des transactions multi-niveaux, les resultats precedents qui concernent le modele des transactions plates

Le controle des acces concurrents a des donnees partagees et manipulees simultanement par plusieurs utilisateurs, ainsi que la reprise, sont des composantes essentielles de tout systeme de gestion de donnees actuel. Tout d'abord, une technique de controle de concurrence adaptee aux bases de donnees a objets, car s'appuyant sur le graphe d'heritage, est proposee. Par la suite, une technique plus fine de controle de concurrence et de reprise exploitant la commutativite des operations est introduite et mise en uvre. Enfin, une variante qui automatise l'extraction des proprietes de commutativite et la definition des operations de compensation est presentee

Actuellement, la majorité des architectures de processeurs sont fondées sur une mémoire partagée avec cohérence de caches. Des prototypes intégrant de grandes quantités de cœurs, reliés par une infrastructure de transmission de messages, indiquent que, dans un proche avenir, les architectures de processeurs vont probablement avoir ces caractéristiques. Ces deux tendances exigent que les processus s'exécutent en parallèle et rendent la programmation concurrente nécessaire. Cependant, la difficulté inhérente du raisonnement sur la concurrence peut rendre ces nouvelles machines difficiles à programmer. Nous explorons trois approches ayant pour but de faciliter la programmation concurrente. Nous proposons WFR-TM, une approche fondé sur la mémoire transactionnelle (TM), un paradigme de programmation concurrente qui utilise des transactions afin de synchroniser l'accès aux données partagées. Une transaction peut soit terminer (commit), rendant visibles ses modifications, soit échouer (abort), annulant toutes ses modifications. WFR-TM tente de combiner des caractéristiques désirables des TM optimistes et pessimistes. Une TM pessimiste n'échoue jamais aucune transaction; néanmoins les algorithmes existants utilisent des verrous pour exécuter de manière séquentielle les transactions qui contiennent des opérations d'écriture. Les algorithmes TM optimistes exécutent toutes les transactions en parallèle mais les terminent seulement si elles n'ont pas rencontré de conflit au cours de leur exécution. WFR-TM fournit des transactions en lecture seule qui sont wait-free, sans jamais exécuter d'opérations de synchronisation coûteuse (par ex. CAS, LL\SC, etc) ou sacrifier le parallélisme entre les transactions d'écriture. Nous présentons également Dense, une implémentation concurrente de graphe. Les graphes sont des structures de données polyvalentes qui permettent la mise en oeuvre d'une variété d'applications. Cependant, des applications multi-processus qui utilisent des graphes utilisent encore largement des versions séquentielles. Nous introduisons un nouveau modèle de graphes concurrents, permettant l'ajout ou la suppression de n'importe quel arc du graphe, ainsi que la traversée atomique d'une partie (ou de l'intégralité) du graphe. Dense offre la possibilité d'effectuer un snapshot partiel d'un sous-ensemble du graphe défini dynamiquement. Enfin, nous ciblons les futures architectures. Dans l'intérêt de la réutilisation du code il existe depuis quelques temps une tentative d'adaptation des environnements d'exécution de logiciel - comme par ex. JVM, l'environnement d'exécution de Java - initialement prévus pour mémoire partagée, à des machines sans cohérence de caches. Nous étudions des techniques générales pour implémenter des structures de données distribuées en supposant qu'elles vont être utilisées sur des architectures many-core, qui n'offrent qu'une cohérence partielle de caches, voir pas de cohérence du tout
Though a majority of current processor architectures relies on shared, cache-coherent memory, current prototypes that integrate large amounts of cores, connected through a message-passing substrate, indicate that architectures of the near future may have these characteristics. Either of those tendencies requires that processes execute in parallel, making concurrent programming a necessary tool. The inherent difficulty of reasoning about concurrency, however, may make the new processor architectures hard to program. In order to deal with issues such as this, we explore approaches for providing ease of programmability. We propose WFR-TM, an approach based on transactional memory (TM), which is a concurrent programming paradigm that employs transactions in order to synchronize the access to shared data. A transaction may either commit, making its updates visible, or abort, discarding its updates. WFR-TM combines desirable characteristics of pessimistic and optimistic TM. In a pessimistic TM, no transaction ever aborts; however, in order to achieve that, existing TM algorithms employ locks in order to execute update transactions sequentially, decreasing the degree of achieved parallelism. Optimistic TMs execute all transactions concurrently but commit them only if they have encountered no conflict during their execution. WFR-TM provides read-only transactions that are wait-free, without ever executing expensive synchronization operations (like CAS, LL/SC, etc), or sacrificing the parallelism between update transactions. We further present Dense, a concurrent graph implementation. Graphs are versatile data structures that allow the implementation of a variety of applications. However, multi-process applications that rely on graphs still largely use a sequential implementation. We introduce an innovative concurrent graph model that provides addition and removal of any edge of the graph, as well as atomic traversals of a part (or the entirety) of the graph. Dense achieves wait-freedom by relying on light-weight helping and provides the inbuilt capability of performing a partial snapshot on a dynamically determined subset of the graph. We finally aim at predicted future architectures. In the interest of ode reuse and of a common paradigm, there is recent momentum towards porting software runtime environments, originally intended for shared-memory settings, onto non-cache-coherent machines. JVM, the runtime environment of the high-productivity language Java, is a notable example. Concurrent data structure implementations are important components of the libraries that environments like these incorporate. With the goal of contributing to this effort, we study general techniques for implementing distributed data structures assuming they have to run on many-core architectures that offer either partially cache-coherent memory or no cache coherence at all and present implementations of stacks, queues, and lists

Cette thèse traite les aspects liés à la gestion à grande échelle de données issues de capteurs hétérogènes. En effet, les capteurs sont de moins en moins chers, de plus en plus nombreux et hétérogènes dans les applications. Ceci implique naturellement le problème de passage à l'échelle et la nécessité de pouvoir exploiter les données provenant de différents types de capteurs. Nous proposons une architecture distribuée et orientée services dans laquelle les tâches de traitement de données sont réparties sur plusieurs niveaux. Les fonctionnalités de gestion de données sont fournies en termes de < > afin de cacher l'hétérogénéité des capteurs sous des services génériques. Nous traitons également les aspects liés à l'administration de parc de capteurs, un sujet non abordé dans ce contexte
This dissertation deals with the issues related to scalable management of heterogeneous sensor data. Ln fact, sensors are becoming less and less expensive, more and more numerous and heterogeneous. This naturally raises the scalability problem and the need for integrating data gathered from heterogeneous sensors. We propose a distributed and service-oriented architecture in which data processing tasks are distributed at severallevels in the architecture. Data management functionalities are provided in terms of "services", in order to hide sensor heterogeneity behind generic services. We equally deal with system management issues in sensor farms, a subject not yet explored in this context

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 transactions
Nous 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

Les architectures multicœurs changent notre façon d'écrire des programmes. L'écriture de programmes concurrents est bien connue pour être difficile. Traditionnellement, l'utilisation de verrous (locks) permettant au code de s'exécuter en exclusion mutuelle, a été l'abstraction la plus largement utilisée pour l'écriture des programmes concurrents. Malheureusement, il est difficile d'écrire des programmes concurrents efficaces et corrects reposant sur des verrous. En outre, les verrous présentent d'autres problèmes, notamment celui du passage à l'échelle. Le concept de mémoire transactionnelle a été proposé comme une solution à ces difficultés. Les transactions peuvent être considérées comme une abstraction de haut niveau, ou une méthodologie pour l'écriture de programmes concurrents, ce qui permet au programmeur de pouvoir déclarer des sections de code devant être exécutés de façon atomique, sans avoir à se soucier des détails de synchronisation. Malheureusement, bien qu'assurément plus facile à utiliser que les verrous, la mémoire transactionnelle souffre encore de problèmes de performance et de facilité d'utilisation. En fait, de nombreux concepts relatifs à l'utilisation et à la sémantique des transactions n'ont pas encore des normes convenues. Cette thèse propose de nouvelles solutions permettant de faciliter l'utilisation des mémoires transactionellles. La thèse débute par un chapitre qui donne un bref aperçu de la mémoire transactionnelle logicielle (STM) ainsi qu'une discussion sur le problème de la facilité d'utilisation. Les contributions à la recherche sont ensuite divisées en quatre chapitres principaux, chacun proposant une approche différente afin de rendre les STMs plus facile à utiliser
Multicore architectures are changing the way we write programs. Writing concurrent programs is well known to be difficult task. Traditionally, the use of locks allowing code to execute in mutual exclusion has been the most widely used abstraction to write concurrent programs. Unfortunately, using locks it is difficult to write correct concurrent programs that perform efficiently. Additionally, locks present other problems such as scalability issues. Transactional memory has been proposed as a possible promising solution to these difficulties of writing concurrent programs. Transactions can be viewed as a high level abstraction or methodology for writing concurrent programs, allowing the programmer to be able to declare what sections of his code should be executed atomically, without having to worry about synchronization details. Unfortunately, although arguably easier to use then locks, transactional memory still suffers from performance and ease of use problems. In fact many concepts surrounding the usage and semantics of transactions have no widely agreed upon standards. This thesis specifically focuses on these ease of use problems by discussing how previous research has dealt with them and proposing new solutions putting ease of use first. The thesis starts with a chapter giving a brief overview of software transactional memory (STM) as well as a discussion of the problem of ease of use that is focused on in the later chapters. The research contributions are then divided into four main chapters, each looking at different approaches working towards making transactional memory easier to use

Les applications géodécisionnelles évoluent vers le temps réel et nécessitent un mécanisme de mise à jour rapide. Or, ce processus est complexe et très coûteux en temps de calcul à cause de la structure dénormalisée des données, stockées sous forme de cube. La méthode classique qui consistait à reconstruire entièrement le cube de données prend de plus en plus de temps au fur et à mesure que le cube grossit, et n'est plus envisageable. De nouvelles méthodes de mise à jour dites incrémentielles ont fait leurs preuves dans le domaine du Business Intelligence. Malheureusement, de telles méthodes n'ont jamais été transposées en géomatique décisionnelle, car les données géométriques nécessitent des traitements spécifiques et complexes. La mise à jour des cubes de données spatiales soulève des problèmes jusqu'alors inconnus dans les cubes de données classiques. En plus de cela, une large confusion règne autour de la notion de mise à jour dans les entrepôts de données. On remarque également que l'architecture des entrepôts de données suit la tendance actuelle d'évolution des architectures de systèmes informatiques vers une distribution des tâches et des ressources, au détriment des systèmes centralisés, et vers le développement de systèmes interopérables. Les architectures en émergence, dites orientées services deviennent dans ce sens très populaires. Cependant, les services dédiés à des tâches de mise à jour de cubes sont pour l'heure inexistants, même si ceux-ci représenteraient un apport indéniable pour permettre la prise de décision sur des données toujours à jour et cohérentes. Le but de ce mémoire est d'élaborer des méthodes de mise à jour incrémentielles pour les cubes spatiaux et d'inscrire le dispositif dans une architecture orientée services. La formulation de typologies pour la gestion de l'entrepôt de données et pour la mise à jour de cube a servi de base à la réflexion. Les méthodes de mise à jour incrémentielles existantes pour les cubes non spatiaux ont été passées en revue et ont permis d'imaginer de nouvelles méthodes incrémentielles adaptées aux cubes spatiaux. Pour finir, une architecture orientée services a été conçue, elle intègre tous les composants de l'entrepôt de données et contient le service web de mise à jour de cube, qui expose les différentes méthodes proposées.

Les systemes transactionnels reposent sur deux modeles de transaction ; le modele a effets differes (majd) et le modele a effets immediats (maji). Le travail presente met en evidence les consequences de l'utilisation des objets types, sur la concurrence et la tolerance aux fautes, dans chacun des modeles de transaction, en se focalisant plus particulierement sur le modele majd. Il precise et ameliore les differentes techniques de mise en uvre de ce modele. Le controle de concurrence y est approfondi en caracterisant et en exploitant differents types de dependances, de facon en particulier a pouvoir continuer l'execution, en cas de conflits d'acces, a condition de rester serialisable. Enfin, il tire partie des deux modeles pour accroitre la concurrence, en proposant une relation de commutativite, appelee commutativite avant-arriere, ainsi qu'une methode de controle de concurrence qui l'exploite, basee sur l'utilisation des objets biversions

Les approches actuelles de représentation des processus métiers s'appuient principalement sur les systèmes de workflow qui ordonnent les tâches selon une logique métier déterminée. Les systèmes de workflow, particulièrement nombreux sur le marché, souffrent, en revanche, de limites sérieuses dans l'évolution et la normalisation des processus métiers suite à leurs mises en exploitation. Par ce travail, nous contribuons à l'évolution et à la normalisation des processus métiers, à travers : - l'enrichissement du journal d'événements par des durées minimales et maximales. Notre philosophie est d'analyser le journal des événements avec le moins d'informations possibles (identité de l'instance, instant de fin, durée minimale, durée maximale, etc. ). - l'enrichissement de la description des processus métiers par des motifs de processus (diffusion (AND/XOR- split) et jointure AND/XOR-join)) et par des relations exceptionnelles (de continuité et de fin) entre les tâches, - la prise en compte des procédures de normalisation en cas d'échec de tâches, afm de fiabiliser au maximum les instances de processus. Nous ajoutons ainsi au niveau de représentation des processus, un niveau de représentation des relations exceptionnelles. La prise en compte à la fois de l'extraction des modèles de processus, enrichi des motifs de processus, et de la procédure de normalisation est un point important de notre travail de thèse. Les systèmes de workflow disponibles sur le marché ne supportent pas encore ce type de fonctionnalités. En effet, les méthodes traditionnelles de conception de processus se basent sur les perceptions des concepteurs, certainement expérimentées, mais n'impliquent pas les observations issues des usages réels. De plus, elles souffrent de l'absence de procédure d'évolution permettant d'optimiser la structure du workflow initialement conçue. La conception est globalement statique, alors qu'elle devrait être dynamique. En effet, il n'y a aucun intérêt de garder un modèle de processus qui ne répond pas aux besoins exprimés par les usages. Afin de répondre au besoin d'évolution et de normalisation des processus métiers, suite aux observations des usages ou tout simplement suite à de nouveaux besoins d'usages, nous avons spécifié une nouvelle étape d'évolution et de correction des processus par l'analyse du journal des événements.

Le contrôle des accès concurrents à des données partagées et manipulées simultanément par plusieurs utilisateurs, ainsi que la reprise lors de pannes, sont des composantes essentielles de tout système de gestion de données actuel, notamment des bases de données. Nous mettons en évidence les limites inhérentes au critère le plus important du domaine : la commutativité des opérations sur les types de données abstraits. Ces limites nous confortent dans l'utilisation de techniques relativement simples dans les deux travaux ultérieurs. Ensuite, nous proposons une technique de contrôle de concurrence adaptée aux bases de données à objets car s'appuyant sur le graphe d'héritage. Cette proposition s'avère être une généralisation de la seule méthode implémentée : le protocole d'ORION. Combinant les limites théoriques de la commutativité à la notion de méthodes, qui encapsulent le comportement des objets, nous proposons une technique simple, et dans une large mesure suffisante, pour déterminer la commutativité entre méthodes. Cette dernière proposition combine les avantages de la technique précédente à ceux obtenus, involontairement, par la décomposition en première forme normale dans les bases de données relationnelles.

Les SGBD temps réels (SGBDDTR) sont définis comme des systèmes qui doivent respecter à la fois les contraintes temporelles des transactions et des données comme les systèmes temps réel (STR) et les contraintes logiques comme les SGBD classiques. Pour un SGBD, il est difficile de respecter les contraintes temporelles en plus de garantir la cohérence logique de la base de données. De même, pour un STR, il est difficile de respecter la cohérence logique en présence de quantités importantes de données. Dans la majorité des travaux sur les SGBD temps réels, le modèle des transactions plates est utilisé et l'objectif est de respecter les deux types de contraintes. Dans ce modèle, une transaction est composée d'opérations primitives "lire" et "écrire". Si une opération échoue, toute la transaction doit être abandonnée et redémarrée éventuellement, la conduisant souvent à rater son échéance. On en déduit que ce modèle n'est pas approprié pour les SGBDTR. Dans ce travail, nous considérons un SGBDTR basé sur le modèle de transactions emboîtées. Notre contribution a consisté à développer des algorithmes de gestion des transactions emboîtées dans les deux contextes centralisé et distribué. Nous avons également proposé un protocole de contrôle de concurrence qui tient compte de l'urgence des transactions pour résoudre des conflits entre (sous-)transactions. Enfin, nous avons développé un protocole de validation uniforme des transactions distribuées basé sur la technique du calcul imprécis. Chacun de ces protocoles a été évalué et comparé à des protocoles proposés dans de précédent travaux
Real-time database systems (RTDBS) are defined as systems whose objective is not only to respect the transactions and data temporal constraints (as in real-time systems), but they also respect the logical consistency of the database (as in classical DBS). In a DBS, it is difficult to deal with real-time contraints in addition to the database logical consistency. On the other hand, real-time systems are not designed to meet transactions real-time constraints when there is a large amount of data. In the majority of previous works on RTBS, the systems are based on the flat transactions modle and the main aim is to respect the two kinds of constraints. In this model, a transaction is composed of two primitive operation : "read" and "write". If an operation fails, then the whole transaction is aborted and restarted, leading often the transaction to miss its deadline. Wa deduce from this that this model is not appropriate to RTDBS. Our contribution in this work has consisisted of developing protocols to manage the intra-transactions conflicts in both centralized and distributed environments. We've also developed an concurrency control protocol based on transaction urgency. Finally, we've proposed an hierarchical commit protocol which guarantees the uniform distributed transaction model based on imprecise computation. Each proposed protocol is evaluated and compared to the protocols proposed in the literature

Les besoins en ressources CPU dans l'automobile sont en constante augmentation. Le standard de développement logiciel AUTOSAR (AUTomotive Open System ARchitecture) - développé au sein d'un consortium regroupant des fabricants de véhicules et des sous-traitants - offre désormais la possibilité de s'orienter vers de nouvelles architectures : les microcontrôleurs multicœur. Leur introduction au sein des systèmes embarqués critiques apporte un lot de problèmes allant à l'encontre des objectifs de sûreté de fonctionnement ISO 26262. Par exemple, le parallélisme des cœurs impose de maîtriser l'ordonnancement pour respecter les contraintes de dépendance entre les tâches, et le partage des données intercœur doit être effectué en assurant leur cohérence. Notre approche s'articule en deux volets. Pour vérifier les contraintes de dépendance entre les tâches, les exigences sur les flots de données sont utilisées pour synthétiser des moniteurs à l'aide de l'outil Enforcer. Un service de vérification en ligne utilise ces moniteurs (injectés dans le noyau du système d'exploitation) pour vérifier le comportement du système. Enfin, pour maîtriser le partage des données intercœur, nous proposons une alternative aux protocoles bloquants. Le protocole wait-free STM-HRT (Software Transactional Memory for Hard Real-Time systems), est conçu sur les principes des mémoires transactionnelles afin d'améliorer la robustesse des systèmes.

Ma thèse se compose de deux parties indépendantes. La première traite decrypto-économie et la seconde d’économétrie théorique. Dans le premier chapitre, je présente un modèle qui prédit la puissance de calcul totale déployée par les mineurs en utilisant le taux de change bitcoin / dollar. Le deuxième chapitre s’appuie sur une version simplifiée du précédent modèle pour faire le constat de l’inefficacité du protocole Bitcoin actuel et proposer un moyen simple de réduire la consommation d’électricité engendrée par cette cryptomonnaie. Le troisième chapitre explique comment identifier et estimer les bornes exactes de la région d’identification de l’effet marginal moyen dans un modèle logit avec effets fixes sur données de panel
My dissertation concatenates two independent parts. The first one dealswith crypto-economics whereas the second one is about theoretical econometrics. In the first chapter, I present a model which predicts bitcoin miners’ total computing power using the bitcoin / dollar exchange rate. The second chapter builds on a simplified version of the preceeding model to show to which extent the current Bitcoin protocol is inefficient and suggest a simple solution to lower the cryptocurrency’s electricity consumption. The third chapter explains how to identify and estimate the sharp bounds of the average marginal effect’s identification region in a fixed effects logit model with panel data

Les logiciels adaptatifs sont une classe de logiciels qui peuvent modifier leur structure et comportement à l'exécution afin de s'adapter à des nouveaux contextes d'exécution. Le développement de logiciels adaptatifs a été un domaine de recherche très actif les dix dernières années. Plusieurs approches utilisent des techniques issues des lignes des produits afin de développer de tels logiciels. Ils proposent des outils, des frameworks, ou des langages pour construire des architectures logicielles adaptatives, mais ne guident pas les ingénieurs dans leur utilisation. De plus, ils supposent que tous les éléments spécifiés à la conception sont disponibles dans l'architecture pour l'adaptation, même s'ils ne seront jamais utilisés. Ces éléments inutiles peuvent être une cause de soucis lors du déploiement sur une cible dont l'espace mémoire est très contraint par exemple. Par ailleurs, le remplacement de composants à l'exécution reste une tâche complexe, elle doit assurer non seulement la validité de la nouvelle version, mais aussi préserver la terminaison correcte des transactions en cours. Pour faire face à ces problèmes, cette thèse propose un processus de développement de logiciels adaptatifs où les tâches, les rôles, et les artefacts associés sont explicites. En particulier, le processus vise la spécification d'informations nécessaires pour construire des architectures logicielles adaptatives. Le résultat d'un tel processus est une architecture logicielle adaptative qui contient seulement des éléments utiles pour l'adaptation. De plus, un mécanisme d'adaptation est proposé basé sur la gestion de transactions pour assurer une adaptation dynamique cohérente. Elle assure la terminaison correcte des transactions en cours. Nous proposons pour cela la notion de dépendance transactionnelle : dépendance entre des actions réalisées par des composants différents. Nous proposons la spécification de ces dépendances dans le modèle de variabilité, et de l'exploiter pour décider des fonctions de contrôle dans les composants de l'architecture, des fonctions qui assurent une adaptation cohérente à l'exécution
Adaptive software is a class of software which is able to modify its own internal structure and hence its behavior at runtime in response to changes in its operating environment. Adaptive software development has been an emerging research area of software engineering in the last decade. Many existing approaches use techniques issued from software product lines (SPLs) to develop adaptive software architectures. They propose tools, frameworks or languages to build adaptive software architectures but do not guide developers on the process of using them. Moreover, they suppose that all elements in the SPL specified are available in the architecture for adaptation. Therefore, the adaptive software architecture may embed unnecessary elements (components that will never be used) thus limiting the possible deployment targets. On the other hand, the components replacement at runtime remains a complex task since it must ensure the validity of the new version, in addition to preserving the correct completion of ongoing activities. To cope with these issues, this thesis proposes an adaptive software development process where tasks, roles, and associate artifacts are explicit. The process aims at specifying the necessary information for building adaptive software architectures. The result of such process is an adaptive software architecture that only contains necessary elements for adaptation. On the other hand, an adaptation mechanism is proposed based on transactions management for ensuring consistent dynamic adaptation. Such adaptation must guarantee the system state and ensure the correct completion of ongoing transactions. In particular, transactional dependencies are specified at design time in the variability model. Then, based on such dependencies, components in the architecture include the necessary mechanisms to manage transactions at runtime consistently

Ce manuscrit présente certains de mes travaux de recherche en matière de gestion de données, réalisés au sein de l'équipe bases de données STORM du laboratoire Logiciels, Systèmes, Réseaux de l'IMAG. Ils ont été effectués depuis 1995 (et jusqu'à 2003), année de ma prise de fonctions en tant que Maître de Conférences à l'Institut National Polytechnique (INP) de Grenoble, en poste à l'Ecole Nationale Supérieure d'Informatique et de Mathématiques Appliquées de Grenoble(ENSIMAG). Mes travaux concernent des aspects système --- gestion de cache et duplication de données, support transactionnels, parmi d'autres. Ils contribuent d'une part à l'extension des fonctions des SGBD et d'autre part à la conception de services séparés utilisables indépendamment d'un SGBD. Mon point de vue porte sur la diversification du panorama des architectures des systèmes de gestion de données. J'ai d'abord travaillé dans l'introduction de fonctions déductives et actives dans les SGBD pour ensuite m'orienter vers des solutions plus ouvertes, des intergiciels de gestion de données distribuées sur des unités fixes et mobiles.