L'archéologie est une discipline des sciences humaines dont l'objet d'étude est l'ensemble des vestiges matériels laissés par l'Homme (objets, bâtiments, infrastructures, paysages...). Une technique précise, la fouille, est employée afin de tirer toutes les informations possibles des sols et structures fouillés en tenant compte de la localisation exacte des objets découverts, de l'étude de la succession des différentes couches de terrain déblayé afin de pouvoir procéder à une datation stratigraphique. L'analyse d'une fouille archéologique demande souvent beaucoup d'efforts pour l'archéologue car, à ce jour, aucun système informatique n'a permis de clairement les aider dans l'analyse de leurs données. Ainsi, pour exploiter des données issues d'une fouille archéologique, nous avons identifié trois critères : la rapidité et la facilité d'utilisation, la possibilité de faire évoluer les données dans le système (les interprétations de l'archéologue suivant des heuristiques qui ne peuvent pas toujours être formalisées de façon absolue) et la visualisation tridimensionnelle. L'outil d'analyse en ligne de type SOLAP est optimisé pour une analyse interactive dite multidimensionnelle où les requêtes, même celles de types agrégatives sont simples et leurs réponses sont rapides. Reste donc à l'optimiser sur les deux autres critères retenus pour exploiter les données issues d'une fouille archéologique et qui marquent les principales faiblesses de l'outil : l'évolution des données pendant la phase d'analyse et l'intégration de la 3e dimension. Ce projet de maîtrise vise à apporter des nouveaux concepts permettant à un utilisateur de réviser ces données pendant sa phase d'analyse. Par la suite, un prototype appliqué à l'archéologie a été élaboré afin de vérifier simplement si les efforts pour réviser des données pouvaient être compatibles avec les efforts d'un outil d'analyse en ligne en conservant la fluidité d'exploration interactive. D'autre part, ce projet de maîtrise a permis d'étudier la faisabilité d'un SOLAP 3D et de soulever une interrogation sur la nécessité d'introduire la 3e dimension à un outil d'analyse en ligne.

Les unités linguistiques sous-lexicales (p.ex., la syllabe, le phonème ou le phone) jouent un rôle crucial dans le traitement langagier. En particulier, le traitement langagier est profondément influencé par la distribution de ces unités. Par exemple, les syllabes les plus fréquentes sont articulées plus rapidement. Il est donc important d’avoir accès à des outils permettant de créer du matériel expérimental ou clinique pour l’étude du langage normal ou pathologique qui soit représentatif de l’utilisation des syllabes et des phones dans la langue orale. L’accès à ce type d’outil permet également de comparer des stimuli langagiers en fonction de leurs statistiques distributionnelles, ou encore d’étudier l’impact de ces statistiques sur le traitement langagier dans différentes populations. Pourtant, jusqu’à ce jour, aucun outil n’était disponible sur l’utilisation des unités linguistiques sous-lexicales du français oral québécois. Afin de combler cette lacune, un vaste corpus du français québécois oral spontané a été élaboré à partir d’enregistrements de 184 locuteurs québécois. Une base de données de syllabes et une base de données de phones ont ensuite été construites à partir de ce corpus, offrant une foule d’informations sur la structure des unités et sur leurs statistiques distributionnelles. Le fruit de ce projet, intitulé SyllabO +, sera rendu disponible en ligne en accès libre via le site web http://speechneurolab.ca/fr/syllabo dès la publication de l’article le décrivant. Cet outil incomparable sera d’une grande utilité dans plusieurs domaines, tels que les neurosciences cognitives, la psycholinguistique, la psychologie expérimentale, la phonétique, la phonologie, l’orthophonie et l’étude de l’acquisition des langues. / Linguistic sublexical units (e.g., syllables, phonemes or phones) have a crucial role in language processing. More specifically, language processing is greatly influenced by the distribution of these units in a language. For example, frequent syllables are produced more rapidly. It is thus important to have access to tools enabling the creation of experimental or clinical material that is representative of syllable and phoneme/phone use in language. Access to such tools also allows the comparison of language stimuli according to their distributional statistics, as well as the study of the impact of these statistics on language processing in different populations. However, to this day, there was no tool available on syllable and phone use for Quebec oral French. To circumvent this problem, a vast corpus of oral spontaneous French was elaborated from the recordings of 184 Quebec speakers. A syllable database and a phone database were then built from this corpus, offering a wealth of information on the structure and distributional statistics of syllables and phones. The project, named SyllabO +, will be made available online (open-access), via this website: http://speechneurolab.ca/en/syllabo as soon as the article describing it is published. We believe SyllabO + will prove immensely useful in many fields, such as cognitive neurosciences, psycholinguistics, experimental psychology, phonetics, phonology, speech therapy and the study of language acquisition.

Pour pallier le manque de connaissances sur la biogéographie des diatomées nordiques, le recueil d'un maximum d'informations est encouragé. Rassembler les données paléolimnologiques régionales permet d'effectuer des analyses écologiques et environnementales dans un contexte géographique plus large. La Circumpolar Diatom Database (CDD), un projet initié en 1997 par le Laboratoire de Paléoécologie Aquatique (LPA), tente de répondre à ces besoins. Toutefois, cette première version de la CDD comporte certaines lacunes, dont l'insertion de données de type « Z » (niveau de carottage) et l'implantation dans un système d'information géographique (SIG). L'objectif principal de cette étude est de développer une nouvelle structure de base de données relationnelle particulièrement adaptée aux données paléolimnologiques favorisant l'archivage, la consultation et la représentation cartographique des données à l'échelle circumpolaire. En second lieu, ce projet vise à tester le potentiel d'implantation de la CDD dans un SIG et d'entrevoir sa diffusion au sein de la communauté scientifique. Les étapes méthodologiques de développement d'un système d'information ont mené à la création d'un modèle de base de données relationnel composé par langage SQL. Une liste de références taxonomiques a été réalisée par l'unification de plusieurs listes existantes. Une interface utilisateur a été développée sous forme de formulaires MS Access facilitant la consultation des résultats. L'utilisation de la CDD a été testée dans ArcGIS par une connexion OLE DB et par conversion en « Personal Geodatabase ». La collecte de données a permis de tripler le volume d'informations de la nouvelle CDD. Elle renferme maintenant quelque 572 sites d'échantillonnage, 39 350 données d'occurrence et 15 000 données limnologiques. Sa couverture s'étale sur huit régions circumpolaires arctiques réparties sur trois continents : Amérique du Nord, Europe et Asie. Jusqu'à maintenant, la couverture spatiale de la CDD permet difficilement d'effectuer des analyses sur une vaste échelle. Il est donc primordial d'encourager la communauté paléolimnologique à contribuer davantage au projet. Ce projet a généré un système d'information exploitable, et les phases d'implantation et de distribution pourront être entreprises en fonction de l'avenir souhaité pour la CDD et des ressources disponibles.

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 DTD. / The 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.

Cette thèse se concentre autour du problème de l'évaluation des requêtes. Étant donné une requête q et une base de données D, l'objectif est de calculer l'ensemble q(D) des uplets résultant de l'évaluation de q sur D. Toutefois, l'ensemble q(D) peut être plus grand que la base de données elle-même car elle peut avoir une taille de la forme n^l où n est la taille de la base de données et l est l'arité de la requête. Calculer entièrement q(D) peut donc nécessiter plus que les ressources disponibles. L'objectif principal de cette thèse est une solution particulière à ce problème: une énumération de q(D) avec un délai constant. Intuitivement, cela signifie qu'il existe un algorithme avec deux phases: une phase de pré-traitement qui fonctionne en temps linéaire dans la taille de la base de données, suivie d'une phase d'énumération produisant un à un tous les éléments de q(D) avec un délai constant (indépendant de la taille de la base de données) entre deux éléments consécutifs. En outre, quatre autres problèmes sont considérés: le model-checking (où la requête q est un booléen), le comptage (où on veut calculer la taille |q(D)|), les tests (où on s'intéresse à un test efficace pour savoir si un uplet donné appartient au résultat de la requête) et la j-ième solution (où on veut accéder directement au j-ième élément de q(D)). Les résultats présentés dans cette thèse portent sur les problèmes ci-dessus concernant: - les requêtes du premier ordre sur les classes de structures de degré borné, - les requêtes du second ordre monadique sur les classes de structures de largeur d'arborescente bornée, - les requêtes du premier ordre sur les classes de structures avec expansion bornée. / This thesis is concentrated around the problem of query evaluation. Given a query q and a database D it is to compute the set q(D) of all tuples in the output of q on D. However, the set q(D) may be larger than the database itself as it can have a size of the form n^l where n is the size of the database and l the arity of the query. It can therefore require too many of the available resources to compute it entirely. The main focus of this thesis is a particular solution to this problem: a scenario where in stead of just computing, we are interested in enumerating q(D) with constant delay. Intuitively, this means that there is a two-phase algorithm working as follows: a preprocessing phase that works in time linear in the size of the database, followed by an enumeration phase outputting one by one all the elements of q(D) with a constant delay (which is independent from the size of the database) between any two consecutive outputs. Additionally, four more problems related to enumeration are also considered in the thesis. These are model-checking (where the query q is boolean), counting (where one wants to compute just the size |q(D)| of the output set), testing (where one is interested in an efficient test for whether a given tuple belongs to the output of the query or not) and j-th solution (where, one wants to be able to directly access the j-th element of q(D)). The results presented in the thesis address the above problems with respect to: - first-order queries over the classes of structures with bounded degree, - monadic second-order queries over the classes of structures with bounded treewidth, - first-order queries over the classes of structures with bounded expansion.

Cette thèse porte sur l'historisation des données dans les bases de données graphes. La problématique des données en graphes existe depuis longtemps mais leur exploitation par des moteurs de système de gestion de bases de données, principalement dans les moteurs NoSQL, est récente. Cette apparition est notamment liée à l'émergence des thématiques Big Data dont les propriétés intrinsèques, souvent décrites à l'aide des propriétés 3V (variété, volume, vélocité), ont révélé les limites des bases de données relationnelles classiques. L'historisation quant à elle, est un enjeu majeur des SI qui a été longtemps abordé seulement pour des raisons techniques de sauvegarde, de maintenance ou plus récemment pour des raisons décisionnelles (suites applicatives de Business Intelligence). Cependant, cet aspect s'avère maintenant prendre une place prédominante dans les applications de gestion. Dans ce contexte, les bases de données graphes qui sont de plus en plus utilisées n'ont que très peu bénéficié des apports récents de l'historisation. La première contribution consiste à étudier le nouveau poids des données historisées dans les SI de gestion. Cette analyse repose sur l'hypothèse selon laquelle les applications de gestion intègrent de plus en plus en leur sein les enjeux d'historisation. Nous discutons ce positionnement au regard de l'analyse de l'évolution des SI par rapport à cette problématique. La deuxième contribution vise, au-delà de l'étude de l'évolution des sytèmes d'information, à proposer un modèle innovant de gestion de l'historisation dans les bases de données NoSQL en graphes. Cette proposition consiste d'une part en l'élaboration d'un système unique et générique de représentation de l'historique au sein des BD NoSQL en graphes et d'autre part à proposer des modes d'interrogation (requêtes). Nous montrons qu'il est possible d'utiliser ce système aussi bien pour des requêtes simples (c'est-à-dire correspondant à ce que l'on attend en première intention d'un système d'historisation~: récupérer les précédentes versions d'une donnée) mais aussi de requêtes plus complexes qui permettent de tirer parti aussi bien de la notion d'historisation que des possibilités offertes par les bases de données graphes (par exemple, la reconnaissance de motifs dans le temps). / This thesis deals with data historization in the context of graphs. Graph data have been dealt with for many years but their exploitation in information systems, especially in NoSQL engines, is recent. The emerging Big Data and 3V contexts (Variety, Volume, Velocity) have revealed the limits of classical relational databases. Historization, on its side, has been considered for a long time as only linked with technical and backups issues, and more recently with decisional reasons (Business Intelligence). However, historization is now taking more and more importance in management applications.In this framework, graph databases that are often used have received little attention regarding historization. Our first contribution consists in studying the impact of historized data in management information systems. This analysis relies on the hypothesis that historization is taking more and more importance. Our second contribution aims at proposing an original model for managing historization in NoSQL graph databases.This proposition consists on the one hand in elaborating a unique and generic system for representing the history and on the other hand in proposing query features.We show that the system can support both simple and complex queries.Our contributions have been implemented and tested over synthetic and real databases.

Sécurisation du Contrôle d'Accès dans les Bases de Données

Les récents progrès réalisés en matière de communication (réseaux hauts débits, normalisation des protocoles et des architectures à objets répartis, explosion de l'internet) conduisent à l'apparition de systèmes de gestion de données et services largement répartis. Les données sont produites à la demande ou de manière continue au travers de divers dispositifs statiques ou mobiles. Cette thèse présente une approche pour l'évaluation de requêtes dites hybrides car intégrant différents aspects des données mobiles, continues, cachées rencontrées dans des environnements dynamiques. Notre approche consiste à représenter une telle requête comme une coordination de services comprenant des services de données et de calcul. Une telle coordination est définie par le flux de la requête et ceux d'opérateurs sur les données (e.g. join, select, union). Un flux de requête représente une expression construite avec les opérateurs de notre modèle de données. Ce flux est construit par un algorithme de ré-écriture à partir de la requête spécifiée dans notre langage de requête HSQL Les flux dit opérateurs composent des services de calcul afin de permettre l'évaluation d'un opérateur particulier. Le processeur de requêtes basées sur les services hybrides que nous avons développé met en mise en œuvre et valide nos propositions.

Les services informatiques, et particulièrement les services sur le Web, permettent le traitement ou l'échange d'informations. Leur composition ainsi que la construction de workflows à partir de services permettent la réalisation de tâches complexes. Toutefois, seules des informations utiles à leur gestion informatique (stockage, exécution, etc.) sont spécifiées dans les langages de description de services ou de compositions de services tels que WSDL, BPEL ou XPDL. Ces descriptions, essentiellement syntaxiques, ne sont pas suffisamment riches pour permettre une gestion complexe supportant la découverte, l'interopérabilité ou l'adaptativité de services au niveau sémantique. En effet, ces descriptions ne permettent pas de lier explicitement les services informatiques et les compositions qu'elles définissent aux fonctions et aux processus implémentés ainsi qu'aux concepts manipulés. Dans les domaines de l'ingénierie par exemple, l'activité de composition de services informatiques reste traditionnellement à la charge des ingénieurs. L'absence de sémantique explicite rend les services et workflows informatiques difficilement compréhensibles, réutilisables et composables pour les ingénieurs du domaine d'intérêt qui n'ont pas contribué à leur conception et ayant des connaissances techniques et informatiques en général limitées. Ces ingénieurs restent ainsi dépendants des développeurs de logiciels pour l'utilisation ou la composition de services informatiques. Pour apporter une solution aux problèmes évoqués, de récentes approches ont été proposées. Cependant, leurs mécanismes d'enrichissement sémantique ne séparent pas la partie syntaxique, utile au stockage ou à l'exécution, de la partie sémantique, utile à la découverte ou à la composition. En outre, ces mécanismes ne fournissent aucune classification hiérarchique ou relationnelle selon la sémantique des services informatiques. Pour remédier à ces limitations, nous proposons une approche basée sur la définition d'ontologies de services (conceptualisations partagées) et d'indexations sémantiques. Notre proposition s'appuie sur une architecture de persistance centrée autour des bases de données à base ontologique pour stocker et indexer les différents services ainsi que leurs compositions. La mise en oeuvre de notre approche consiste en un prototype logiciel implantant les concepts de service et de workflow sémantiques permettant de stocker, de rechercher, de remplacer, de réutiliser les services et les workflows informatiques existants et d'en construire de nouveaux de manière incrémentale. Ces travaux sont validés en étant appliqués au domaine de la modélisation géologique et de l'ingénierie pétrolière et plus particulièrement à l'interprétation sismique.

Les règles d'association révèlent des régularités non triviales et potentiellement utiles pour l'aide a la décision, dans les bases de données. Leur validité est évaluée par le biais de mesures de qualités dont les plus utilisées sont le support et la confiance. Pour une base de données transactionnelles d'un supermarché, elles sont du type "90% des clients ayant acheté du vin et du fromage ont également acheté du pain, sachant que 75% des clients ont acheté ces articles". Dans ce travail, nous spécifions une classe de mesures de qualité normalisées en ce sens qu'elles reflètent les situations de référence comme l'incompatibilité, la dépendance négative, l'indépendance, la dépendance positive, et l'implication logique entre la prémisse et le conséquent. Nous caractérisons les mesures de qualité normalisables, donnons les formules de normalisation et montrons que la plupart de celles qui sont normalisables ont la même normalisée, à savoir la mesure de qualité Mgk introduite dans Guillaume (2000). De plus, nous caractérisons des bases pour les règles positives et les règles négatives valides au sens de Mgk, et proposons des algorithmes de génération de ces bases