Search

Pig Latin is a popular language which is widely used for parallel processing of massive data sets. Currently, subexpressions occurring repeatedly in Pig Latin scripts are executed as many times as they appear, and the current Pig Latin optimizer does not identify reuse opportunities.We present a novel optimization approach aiming at identifying and reusing repeated subexpressions in Pig Latin scripts. Our optimization algorithm, named PigReuse, operates on a particular algebraic representation of Pig Latin scripts. PigReuse identifies subexpression merging opportunities, selects the best ones to execute based on a cost function, and reuses their results as needed in order to compute exactly the same output as the original scripts. Our experiments demonstrate the effectiveness of our approach.

National audience; With the increasing amount of available data and transformations manipulating the data, it has become essential to analyze and debug data transformations. A sub-problem of data transformation analysis is to understand why some data are not part of the result of a relational query. One possibility to explain the lack of data in a query result is to identify where in the query data pertinent to the expected, but missing output is lost during query processing. A first approach to this so called why-not provenance has been recently proposed, but we show that this first approach has some shortcomings. To overcome these shortcomings, we propose an algorithm to explain non-existing data in a query result. This algorithm allows to compute the why-not provenance for rela- tional queries involving selection, projection, join and union. After providing necessary definitions, this paper contributes a detailed description of the algorithm. A comparative evaluation shows that it is both more efficient and effective than the state-of-the-art ap- proach.

The problem of answering Why-Not questions consists in explaining why the result of a querydoes not contain some expected data, i.e., missing answers. To solve this problem, we resort to identifyingwhere in the query, data relevant to the missing answer were lost. Existing algorithms producing suchquery-based explanations rely on a query tree representation, potentially leading to different or partialexplanations. This significantly impairs on the effectiveness of computed explanations. Here we present aneffective, query-tree independent representation of query-based explanations, for a wide class of Why-Notquestions, based on provenance polynomials. We further describe an algorithm that efficiently computes thecomplete set of these explanations. An experimental evaluation validates our statements

International audience; The European Union has created the European Institute of Technology (EIT), within which ICT Labs focuses on fostering exchange and new result creation in the sphere of Information and Communication Technology, across the areas of research, higher education, and industrial innovation. ''Digital Cities of the Future'' is an action line (or chapter) of EIT ICT Labs. Within this action line, we coordinated an activity called ''DataBridges: Data Integration for Digital cities'', whose aim is to produce, link, integrate and exploit open data in the Digital Cities data space, for the benefit of both citizens and administrations. In that context, DataBridges addresses many research challenges such as acquiring (or producing) Open City Data in RDF, data linking and integration, data provenance, and visualization. This position paper describes our efforts within DataBridges to integrate City Data. We provide a brief introduction to EIT ICT Labs, its goals and structures, and how DataBridges fits them. We then detail the activity and some selected results from 2011 - 2012, and plans for 2013. We conclude with some research challenges we plan to adress in the future.

National audience; Dans le contexte de développement de transformations complexes, les réponses à une question de type 'Why-Not' ont pour objectif d'expliquer au développeur les raisons de l'absence de certaines réponses dans le résultat d'une transformation. Plusieurs types d'explications ont été proposées et étudiées : des explications basées sur les données, des explications basées sur l'arbre de la requête, des expli-cations hybrides. Les explications qui s'appuient sur l'arbre de la requête, appelées explications 'query-based' (query-based explanations) peuvent être calculées plus efficacement et sont aussi plus faciles à interpréter par le développeur. Cependant, les algorithmes connus produisant des explications 'query-based' donnent des résultats (1) qui sont dépendants des arbres de requêtes considérés, (2) qui ne sont pas toujours complets. À l'évidence, cela pose un problème d'utilisation important, parce que le développeur doit interpréter les explications en fonction d'un arbre de requête perdant ainsi le bénéfice de l'utilisation d'un langage de requêtes déclaratif et savoir que ces explications sont insuffisantes pour expliquer l'absence de réponse. 1 Cet article propose de remédier à ce problème avec un algorithme appelé Ted, qui produit des explications 'query-based' complètes et équivalentes pour des ar-bres de requêtes conjonctives réordonnés.; Answering Why-Not questions consists in explaining to developers of complex data transformations or manipulations why their data transformation did not pro-duce some specific results, although they expected them to do so. Different types of explanations that serve as Why-Not answers have been proposed in the past and are either based on the available data, the query tree, or both. Solutions (partially) based on the query tree are generally more efficient and easier to interpret by de-velopers than solutions solely based on data. However, algorithms producing such query-based explanations so far may return different results for reordered conjunc-tive query trees, and even worse, these results may be incomplete. Clearly, this represents a significant usability problem, as the explanations developers get may be partial and developers have to worry about the query tree representation of their query, losing the advantage of using a declarative query language. As remedy to this problem, we propose the Ted algorithm that produces the same complete query-based explanations for reordered conjunctive query trees.

International audience; With the increasing amount of available data and transformations manipulating the data, it has become essential to analyze and debug data transformations. A sub-problem of data transformation analysis is to understand why some data are not part of the result of a relational query. One possibility to explain the lack of data in a query result is to identify where in the query we lost data pertinent to the expected outcome. A first approach to this so called why-not provenance has been recently proposed, but we show that this first approach has some shortcomings. To overcome these shortcomings, we propose \ned, an algorithm to explain data missing from a query result. NedExplain computes the why-not provenance for monotone relational queries with aggregation. After providing necessary definitions, this paper contributes a detailed description of the algorithm. A comparative evaluation shows that it is both more efficient and effective than the state-of-the-art approach.

International audience

International audience

National audience; Avec la multiplication des sources d'informations disponibles et l'accroissement des volumes et flux de données potentiellement accessibles, la qualité des données et, au sens large, la qualité des informations n'ont cessé de prendre une place de premier plan tant au niveau académique qu'au sein des entreprises. Si l'analyse des données, l'extraction de connaissances à partir des données et la prise de décision peuvent être réalisées sur des données inexactes, incomplètes, ambiguës et de qualité médiocre, on peut alors s'interroger sur le sens à donner aux résultats de ces analyses et remettre en cause, à juste titre, la qualité des connaissances ainsi " élaborées ", tout comme le bien-fondé des décisions prises. Aujourd'hui, il n'est donc plus question de négliger les données mais, bien au contraire, d'évaluer et de contrôler leur qualité dans les systèmes d'information, les bases et les entrepôts de données. Ainsi, ont été proposées de nombreuses mesures objectives, des méthodes et tout un outillage technique pour mener une expertise critique de la qualité des données dans ces systèmes, permettant aux utilisateurs de relativiser la confiance qu'ils pourraient accorder aux données et de leur permettre de mieux en adapter leur usage. L'impact et les coûts de la non-qualité des données (tout comme sa méconnaissance) retentissent à chaque étape d'un processus de traitement des données et de nombreuses techniques peuvent être combinées pour consolider et améliorer la qualité des données. L'objet de ce chapitre est de faire un tour d'horizon des méthodes et des techniques employées pour détecter deux des principaux problèmes de qualité des données que sont les doublons et les données aberrantes, en se concentrant sur les méthodes basées sur des mesures de distance. Nous passerons d'abord en revue les principales sources de problèmes de qualité des données ainsi que les solutions mises en œuvre communément dans la pratique. Ensuite, nous nous consacrerons à la définition des problèmes de détection de doublons et de détection de valeurs aberrantes et nous présenterons les mesures de distances pouvant leur être appliquées. Les approches de détection de doublons et de détection de valeurs aberrantes utilisant ces mesures sont présentées par la suite et elles seront illustrées par des exemples d'application réels.

International audience

Entity Resolution (ER) aims to identify different descriptions in various Knowledge Bases (KBs) that refer to the same entity. ER is challenged by the Variety, Volume and Veracity of entity descriptions published in the Web of Data. To address them, we propose the MinoanER framework that simultaneously fulfills full automation, support of highly heterogeneous entities, and massive parallelization of the ER process. MinoanER leverages a token-based similarity of entities to define a new metric that derives the similarity of neighboring entities from the most important relations, as they are indicated only by statistics. A composite blocking method is employed to capture different sources of matching evidence from the content, neighbors, or names of entities. The search space of candidate pairs for comparison is compactly abstracted by a novel disjunctive blocking graph and processed by a non-iterative, massively parallel matching algorithm that consists of four generic, schema-agnostic matching rules that are quite robust with respect to their internal configuration. We demonstrate that the effectiveness of MinoanER is comparable to existing ER tools over real KBs exhibiting low Variety, but it outperforms them significantly when matching KBs with high Variety., Comment: Presented at EDBT 20019

International audience; In analyzing and debugging data transformations, or more specifically relational queries, a subproblem is to understand why some data are not part of the query result. This problem has recently been addressed from different perspectives for various fragments of relational queries. The different perspectives yield different, yet complementary explanations of such missing-answers. This paper first aims at unifying the different approaches by defining a new type of explanation, called hybrid explanation, that encompasses the variety of previously defined types of explanations. This solution goes beyond simply forming the union of explanations produced by different algorithms and is shown to be able to explain a larger set of missing-answers. Second, we present Conseil, an algorithm to generate hybrid explanations. Conseil is also the first algorithm to handle non-monotonic queries. Experiments on efficiency and explanation quality show that Conseil is comparable to and even outperforms previous algorithms.

International audience; Duplicate detection determines different representations of real-world objects in a database. Recent research has considered the use of relationships among object representations to improve duplicate detection. In the general case where relationships form a graph, research has mainly focused on duplicate detection quality/effectiveness. Scalability has been neglected so far, even though it is crucial for large real-world duplicate detection tasks. We scale-up duplicate detection in graph data (ddg) to large amounts of data and pairwise comparisons, using the support of a relational database management system. To this end, we first present a framework that generalizes the ddg process. We then present algorithms to scale ddg in space (amount of data processed with bounded main memory) and in time. Finally, we extend our framework to allow batched and parallel ddg, thus further improving efficiency. Experiments on data of up to two orders of magnitude larger than data considered so far in ddg show that our methods achieve the goal of scaling ddg to large volumes of data.