Search

Recursion is becoming a key construct in analytic systems, thanks to the increasing popularity of data structures such as graphs and growth in data over the internet. This resurgence has seen different optimization techniques proposed for recursive queries. Recursive queries are particularly useful for retrieving nodes reachable along deep paths in a graph. Their evaluation involves an iterative application of a function or operation until some condition is satisfied. Cost models remain an essential component of a query optimizer, most important for estimating the cost of query plans and quality plans selection by the optimizer. For recursive queries, however, cost estimation is far from trivial and has received less attention.One of the challenges encountered in costing a recursive query operator or plan include determining the convergence rate of the recursive. Many systems ignore convergence rate in the data statistics, implementation algorithm and other factors that determine a good cost estimation for recursive query execution. The lack of cost estimation framework support for recursive queries and a validation framework in general for cost model are the main motivation for this work.In this thesis, we propose a cost estimation technique for recursive terms of the extended relational algebra. This technique uses data statistics and information about the maximum iterative steps needed for recursive evaluation to converge, to estimate the cost of query plans and select an estimated cheapest query plan, in terms of computing resources usage e.g. memory footprint, CPU and I/O, and evaluation time. We also present a cost validation framework where we define a set of metrics and standard specifications for cost model, and the conditions for query plan optimality. These set of metrics and specifications are then used for assessing the efficacy and consistency of plan-selection function of a cost model and they can also serve as a guide for developing advanced cost models. We evaluate the effectiveness of our cost estimation technique on a set of recursive graph queries on both generated and real datasets of significant size. Experiments show that our cost estimation technique improves the performance of recursive query evaluation on popular relational database engines.; La récursivité devient un élément clé des systèmes analytiques, grâce à la popula- rité croissante des structures de données telles que les graphes et à l’augmentation des données sur Internet. Cette résurgence a vu différentes techniques d’optimisation propo- sées pour cette classe de requêtes. Les requêtes récursives sont particulièrement utiles pour récupérer les nœuds accessibles le long de chemins profonds dans un graphe. Leur évaluation implique une application itérative d’une fonction ou d’une opération jusqu’à ce qu’une condition soit satisfaite. Le modèle de coût reste une composante essentielle d’un optimiseur de requêtes, surtout pour l’estimation du coût des plans de requête et la sélection des plans de qualité par l’optimiseur. Pour les termes récursifs, cependant, l’estimation des coûts est loin d’être triviale et a reçu moins d’attention.L’une des difficultés rencontrées dans le calcul du coût d’un opérateur ou d’un plan d’interrogation récursif consiste à déterminer le taux de convergence du récursif. De nombreux systèmes ignorent le taux de convergence dans les statistiques de données, l’algorithme de mise en œuvre et d’autres facteurs qui déterminent une bonne estimation du coût de l’exécution d’une requête récursive. L’absence d’un cadre d’estimation des coûts pour les requêtes récursives et d’un cadre de validation en général pour le modèle de coût sont la principale motivation de ce travail.Dans cette thèse, nous proposons une technique d’estimation des coûts pour les termes récursifs de l’algèbre relationnelle étendue. Cette technique utilise des statistiques de don- nées et des informations sur les étapes itératives maximales nécessaires à la convergence de l’évaluation récursive, pour estimer le coût des plans de requête et sélectionner un plan de requête estimé le moins cher, en termes d’utilisation des ressources informatiques, par exemple l’empreinte mémoire, le CPU et les E/S, et le temps d’évaluation. Nous présentons également un cadre de validation des coûts dans lequel nous définissons un ensemble de mesures et de spécifications standard pour le modèle de coût, et la condition d’optimalité du plan de requête. Cet ensemble de mesures et de spécifications est ensuite utilisé pour évaluer l’efficacité et la cohérence de la fonction de sélection du plan d’un modèle de coût et peut également servir de guide pour l’élaboration de modèles de coût efficaces. Nous évaluons l’efficacité de notre technique d’estimation des coûts sur un ensemble de requêtes de graphes récursives sur des ensembles de données générées et réelles de taille significative, notamment. Les expériences montrent que notre technique d’estimation des coûts améliore la performance de l’évaluation des requêtes récursives sur les moteurs de bases de données relationnelles les plus populaires.

Databases, and in particular relational databases, are a common paradigm for storing and querying data. Data is stored in relations which are linked with each other. Users may interrogate the database by issuing queries via a declarative query language. One of the challenges for a relational database management system (RDBMS) is to evaluate each query as quickly possible. However, as it turns out, there are many ways in which a query can be executed. The RDBMS delegates the choice of the query execution plan to a query optimiser. In turn, the query optimiser tasks a cost model with the responsibility of estimating the cost of each execution plan considered by the optimiser. The cost estimation therefore has a large influence on the quality of the execution plans, which in turns affects the running time that the user perceives. The most important input in the cost model is the selectivity, which is the amount of data that is expected to flow in and out of each operator in a plan. From a statistical point of view, this is a case of density estimation, where the goal is to determine the amount of data that verifies certain conditions. It is common practice to use density estimation models that make strong simplifying assumptions, in large part for efficiency reasons. For instance, it is usually assumed that attributes are independent with each other. Alas, in practice, these assumptions are more often that not unverified, which leads to large estimation errors. The goal of this PhD is thus to propose models that offer a better compromise between selectivity estimation accuracy and computational cost. First of all, we propose a methodology based on Bayesian networks, where we constrain each network to have a tree topology, therefore allowing a linear computational complexity. Secondly, we train online machine learning models to correct an existing selectivity estimation model, whilst adapting to concept drift. Our experimental results, which are based on the TPC-DS and JOB benchmarks, are very encouraging with respect to both of our lines of work., Les bases de données relationnelles sont couramment utilisées pour stocker et interroger des données. Les données y sont stockées dans des relations qui sont liées entre elles. Un utilisateur interroge ces données via des requêtes exprimées dans un langage déclaratif. Un des défis pour le Système de Gestion de Bases de Données Relationnelles (SGBDR) est d’évaluer les requêtes le plus rapidement possible. Pour cette évaluation, il existe un large choix de plans d’exécution associé à une requête donnée. Le SGBDR délègue le choix du plan d’exécution le plus efficace à un optimiseur. Dans ce processus, le modèle de coûts, quand à lui, a la responsabilité d’estimer le temps de calcul de chaque plan d’exécution considéré par l’optimiseur. Par conséquent, le modèle de coûts influe sur la qualité des plans d’exécution produit par l’optimiseur, et donc sur le temps de réponse perçu par l’utilisateur.Le paramètre le plus influant dans le modèle de coûts est la sélectivité, qui permet d’estimer la quantité de données qui transite entre chaque opérateur d’un plan d’exécution. D’un point de vue statistique, ceci correspond à de l’estimation de densité, qui consiste à déterminer la quantité de données qui vérifie un ensemble de conditions. Il est d’usage courant d’utiliser des modèles avec des hypothèses simplificatrices pour des raisons de performances. Par exemple, il est souvent supposés qu’il n’existe pas de dépendances de valeurs entre différents attributs de relations. Dans la majeure partie des applications cette hypothèse se révèle non vérifiée et conduit à de grandes erreurs d’estimation. Le but de cette thèse est donc de proposer des modèles plus réalistes qui offrent un meilleur compromis entre la précision des estimations et la complexité calculatoire requise. Premièrement, nous proposons une méthode s’appuyant sur les réseaux Bayésiens dont la représentation sous forme d’arbre nous permet d’améliorer la précision des estimations avec une complexité linéaire. Par la suite, nous explorons l’usage de modèles d’apprentissage en ligne pour corriger un modèle d’estimation existant tout en s’adaptant à l’évolution des données. Nos résultats expérimentaux basés sur les bechmaks JOB et TPC-DS montrent des résultats très encourageants.

Dans ce chapitre, les auteurs décrivent le projet national de gestion du cycle de vie des données (DLCM), constitué par les équipes de bibliothèques, informatiques et services de recherche de huit institutions partenaires. Lancé officiellement en août 2015 et financé par le programme swissuniversities SUC P-2/ P-5, le projet vise à mettre en place des services destinés principalement aux chercheurs au niveau suisse pour leurs besoins les plus importants dans la gestion de leurs données. L'identification de ces besoins s'est basée sur une étude d'envergure de documents, ainsi que des entretiens semi-structurés, ce qui a conduit à répertorier des ‚use cases‘ principaux ainsi que des services de base, tels que : un point d'accès et de contact pour obtenir des informations, de la formation, et conseils personnalisés, ainsi que des solutions de gestion actives des données, y inclus des options de stockage de conservation à long terme, et leur publication selon des normes internationales. Un accent particulier a en outre été mis sur la pérénité des services en appliquant des méthodologies de modèles d'affaire inspirés des ‚lean startups‘ et en établissant des modèles de coûts.

This paper investigates the link between farm investment and farm performance considering two types of farms that may have a different investment strategy: farms that are intensive in capital, and farms that have a low capital intensity. Panel data on specialized dairy farms of one sub-region of French Brittany (Ille-et-Vilaine) for the period 2005-2014 were used. Results from adjustment cost models indicate that farms tend to smooth their investments to limit adjustment costs and that farm performance has a negative impact on investment.

International audience; La métrologie productive assure non seulement la satisfaction du client final et la maitrise des dérives du process mais également se fonde sur des arguments économiques comme générateur de valeur. Cet article propose un modèle de cout afin d'évaluer l'apport économique des opérations d'inspection (contrôle de conformité et suivi de fabrication), qui est basé sur l'approche Activity Based Costing, les performances des activités en terme de taux de rebut ou non-conformité, et les occurrences des activités impactées par les variations. Une application industrielle illustre l'utilisation d'un tel indicateur de performance pour la sélection du meilleur processus d'inspection.

In contrast to the traditional data, semi-structured data are irregular:data may be missed, different data types may be for the similar concepts,and if any the structure may not be well-known. One lacks actuallypredefined schemas to describe the data of the real world. It makes itdifficult to integrate the data from different sources.We propose a mediator architecture entirely based on XML. The objective ofthe mediator architecture is to federate distributed and heterogeneousdata sources. It relies on XQuery, the functional language that isdesigned to query across XML documents. The mediator parses the XQueryrequest, dispatch it to sources for evaluation and recompose results withadditional query evaluation.Query evaluation must be done by making best use of data specificity tocarry out an efficient optimization. We present the algebraXAlgebra based on the operators designed for XML. This algebra aims toconstruct execution plans for the evaluation of XQuery and processestuples of tree structure.These execution plans must be evaluated by a cost model andone of them with the minimal cost will be selected. In this thesis,we define a cost model for semi-structured data that is designed forour algebra.Since the data sources (DBMS, Web server, search engine, etc.) may be veryheterogeneous, they can have different capabilities of processing data,and their cost models may also be defined with different precision. So,in order to integrate such information in the mediation architecture, wehave to know how to communicate the information between the mediator andthe sources and to integrate them. To do this, we use XML-based languagessuch as XML-schema and MathML to export the metadata, cost formula andthe definitions of source capabilities. The exported information istransferred by an application interface called XML/DBC.Finally, diverse optimizations specific to this mediator architecturemust be considered. For this, we introduce a semantic cache based onthe DBMS prototype that store natively and efficiently XML data., Contrairement aux données traditionnelles, les données semi-structuréessont irrégulières : des données peuvent manquer, des conceptssimilaires peuvent être représentés par différents types de données,et les structures même peuvent être mal connues. Cette absence de schéma prédéfini, permettant de tenir compte de toutes les donnéesdu monde extérieur, présente l'inconvénient de complexifier lesalgorithmes d'intégration des données de différentes sources.Nous proposons une architecture de médiation basée entièrement sur XML.L'objectif de cette architecture de médiation est de fédérer des sources dedonnées distribuées de différents types.Elle s'appuie sur le langage XQuery, un langage fonctionnelconçu pour formuler des requêtes sur des documents XML. Le médiateur analyseles requêtes exprimées en XQuery et répartit l'exécution de la requêtesur les différentes sources avant de recomposer les résultats.L'évaluation des requêtes doit se faire en exploitant au maximum lesspécificités des données et permettre une optimisation efficace.Nous décrivons l'algèbre XAlgebre à base d'opérateurs conçuspour XML. Cette algèbre a pour but de construire des plans d'exécution pourl'évaluation de requêtes XQuery et traiter des tuples d'arbres XML.Ces plans d'exécution doivent pouvoir être modélisés par un modèlede coût et celui de coût minimum sera sélectionné pour l'exécution. Dans cette thèse, nous définissons un modèle de coût pour les donnéessemi-structurées adapté à notre algèbre.Les sources de données (SGBD, serveurs Web, moteur de recherche)peuvent être très hétérogènes, elles peuvent avoir descapacités de traitement de données très différentes, mais aussi avoirdes modèles de coût plus ou moins définis. Pour intégrer ces différentes informations dansl'architecture de médiation, nous devons déterminer comment communiquerces informations entre le médiateur et les sources, et comment les intégrer.Pour cela, nous utilisons des langages basés sur XML comme XML-Schema et MathMLpour exporter les informations de métadonnées, de formules de coûtset de capacité de sources.Ces informations exportées sont communiquées par l'intermédiaire d'une interfaceapplicative nommée XML/DBC.Enfin, des optimisations diverses spécifiques à l'architecture de médiationdoivent être considérées. Nous introduisons pour cela un cache sémantiquebasé sur un prototype de SGBD stockant efficacement des données XMLen natif.

International audience; The control of the costs, as soon as possible of the product life cycle, became a major asset in the competitiveness of the companies confronted with the universalization of competition. After having proposed the problems related this control difficulties, we will present an approach defining a concept of cost entity related to the activities of the product to be designed and realized. We will then try to apply this approach to the fields of the sand casting. This work will highlight the hierarchisation difficulties with the entities composing the models created as well as the limits of a generic approach.