The Experts below are selected from a list of 3828 Experts worldwide ranked by ideXlab platform
Georges Gardarin - One of the best experts on this subject based on the ideXlab platform.
-
A rule-based Query optimizer with multiple search strategies
Data & Knowledge Engineering, 1994Co-Authors: Béatrice Finance, Georges GardarinAbstract:Abstract This paper describes a rule-based Query optimizer. The originality of the approach is through a uniform high-level rule language used to model both Query rewriting and planning, as well as search strategies. Rules are given to specify operation permutation, Recursive Query optimization, integrity constraint addition, to model join ordering and access path selection. Therefore, meta-rules are presented to model multiple search strategies, including enumerative and randomized search. To illustrate these ideas, we describe a Query optimizer for an extensible database server that supports abstract data types, complex objects, deductive capabilities and integrity constraints. A prototype of the Query optimizer proposed in this paper is operational and has been demonstrated at the 1991 ESPRIT week in the EDS project.
Lawal Muideen - One of the best experts on this subject based on the ideXlab platform.
-
Sur l'estimation des coûts pour l'algèbre relationnelle récursive
HAL CCSD, 2021Co-Authors: Lawal MuideenAbstract: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 includes 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 the 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 popularité 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 proposé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 donné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
-
On Cost Estimation for the Recursive Relational Algebra
2021Co-Authors: Lawal MuideenAbstract:La récursivité devient un élément clé des systèmes analytiques, grâce à la popularité 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 proposé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 donné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.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 includes 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 the 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
-
A Cost Estimation Technique for Recursive Relational Algebra
'Association for Computing Machinery (ACM)', 2020Co-Authors: Lawal Muideen, Genevès Pierre, Layaïda NabilAbstract:International audienceWith the increasing popularity of data structures such as graphs, re-cursion is becoming a key ingredient of Query languages in analytic systems. Recursive Query evaluation involves an iterative application of a function or operation until some condition is satisfied. It is particularly useful for retrieving nodes reachable along deep paths in a graph. The optimization of Recursive queries has remained a challenge for decades. Recently, extensions of Codd's classical relational algebra to support Recursive terms and their optimisation gained renewed interest [10]. Query optimization crucially relies on enumeration of Query evaluation plans and on cost estimation techniques. Cost estimation for Recursive terms is far from trivial, and received less attention. In this paper, we propose a new cost estimation technique for Recursive terms of the extended relational algebra. This technique allows to select an estimated cheapest Query plan, in terms of computing resources usage e.g. memory footprint, CPU and I/O and evaluation time. 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, including Yago: a graph with more than 62 millions edges and 42 million nodes. Experiments show that our cost estimation technique improves the performance of Recursive Query evaluation on popular relational database engines such as PostgreSQL
Martin Abadi - One of the best experts on this subject based on the ideXlab platform.
-
Unified declarative platform for secure networked information systems
Proceedings - International Conference on Data Engineering, 2009Co-Authors: Wenchao Zhou, Boon Thau Loo, Yun Mao, Martin AbadiAbstract:We present a unified declarative platform for specifying, implementing, and analyzing secure networked information systems. Our work builds upon techniques from logic-based trust management systems, declarative networking, and data analysis via provenance. We make the following contributions. First, we propose the secure network datalog (SeNDlog) language that unifies Binder, a logic-based language for access control in distributed systems, and Network Datalog, a distributed Recursive Query language for declarative networks. SeNDlog enables network routing, information systems, and their security policies to be specified and implemented within a common declarative framework. Second, we extend existing distributed Recursive Query processing techniques to execute SeNDlog programs that incorporate authenticated communication among untrusted nodes. Third, we demonstrate that distributed network provenance can be supported naturally within our declarative framework for network security analysis and diagnostics. Finally, using a local cluster and the PlanetLab testbed, we perform a detailed performance study of a variety of secure networked systems implemented using our platform.
Boon Thau Loo - One of the best experts on this subject based on the ideXlab platform.
-
Datalog and Emerging Applications: An Interactive
2016Co-Authors: Shan Shan Huang, Logicbox Inc, Todd J. Green, Boon Thau LooAbstract:We are witnessing an exciting revival of interest in Recursive Datalog queries in a variety of emerging application domains such as data integration, information extraction, networking, program analysis, security, and cloud computing. This tutorial brie y reviews the Datalog language and Recursive Query processing and optimization techniques, then discusses applications of Datalog in three application domains: data integration, declarative networking, and program analysis. Throughout the tutorial, we use LogicBlox, a commercial Datalog engine for enterprise software systems, to allow the audience to walk through code examples presented in the tutorial
-
Unified declarative platform for secure networked information systems
Proceedings - International Conference on Data Engineering, 2009Co-Authors: Wenchao Zhou, Boon Thau Loo, Yun Mao, Martin AbadiAbstract:We present a unified declarative platform for specifying, implementing, and analyzing secure networked information systems. Our work builds upon techniques from logic-based trust management systems, declarative networking, and data analysis via provenance. We make the following contributions. First, we propose the secure network datalog (SeNDlog) language that unifies Binder, a logic-based language for access control in distributed systems, and Network Datalog, a distributed Recursive Query language for declarative networks. SeNDlog enables network routing, information systems, and their security policies to be specified and implemented within a common declarative framework. Second, we extend existing distributed Recursive Query processing techniques to execute SeNDlog programs that incorporate authenticated communication among untrusted nodes. Third, we demonstrate that distributed network provenance can be supported naturally within our declarative framework for network security analysis and diagnostics. Finally, using a local cluster and the PlanetLab testbed, we perform a detailed performance study of a variety of secure networked systems implemented using our platform.
Carlo Zaniolo - One of the best experts on this subject based on the ideXlab platform.
-
a case for stale synchronous distributed model for declarative Recursive computation
Theory and Practice of Logic Programming, 2019Co-Authors: Ariyam Das, Carlo ZanioloAbstract:A large class of traditional graph and data mining algorithms can be concisely expressed in Datalog, and other Logic-based languages, once aggregates are allowed in recursion. In fact, for most BigData algorithms, the difficult semantic issues raised by the use of non-monotonic aggregates in recursion are solved by Pre-Mappability ( reM), a property that assures that for a program with aggregates in recursion there is an equivalent aggregate-stratified program. In this paper we show that, by bringing together the formal abstract semantics of stratified programs with the efficient operational one of unstratified programs, reM can also facilitate and improve their parallel execution. We prove that reM-optimized lock-free and decomposable parallel semi-naive evaluations produce the same results as the single executor programs. Therefore, reM can be assimilated into the data-parallel computation plans of different distributed systems, irrespective of whether these follow bulk synchronous parallel (BSP) or asynchronous computing models. In addition, we show that non-linear Recursive queries can be evaluated using a hybrid stale synchronous parallel (SSP) model on distributed environments. After providing a formal correctness proof for the Recursive Query evaluation with reM under this relaxed synchronization model, we present experimental evidence of its benefits.
-
a case for stale synchronous distributed model for declarative Recursive computation
arXiv: Programming Languages, 2019Co-Authors: Carlo ZanioloAbstract:A large class of traditional graph and data mining algorithms can be concisely expressed in Datalog, and other Logic-based languages, once aggregates are allowed in recursion. In fact, for most BigData algorithms, the difficult semantic issues raised by the use of non-monotonic aggregates in recursion are solved by Pre-Mappability (PreM), a property that assures that for a program with aggregates in recursion there is an equivalent aggregate-stratified program. In this paper we show that, by bringing together the formal abstract semantics of stratified programs with the efficient operational one of unstratified programs, PreM can also facilitate and improve their parallel execution. We prove that PreM-optimized lock-free and decomposable parallel semi-naive evaluations produce the same results as the single executor programs. Therefore, PreM can be assimilated into the data-parallel computation plans of different distributed systems, irrespective of whether these follow bulk synchronous parallel (BSP) or asynchronous computing models. In addition, we show that non-linear Recursive queries can be evaluated using a hybrid stale synchronous parallel (SSP) model on distributed environments. After providing a formal correctness proof for the Recursive Query evaluation with PreM under this relaxed synchronization model, we present experimental evidence of its benefits. This paper is under consideration for acceptance in Theory and Practice of Logic Programming (TPLP).