Successful data-driven science requires complex data engineering pipelines to clean, transform, and alter data in preparation for machine learning, and robust results can only be achieved when each step in the pipeline can be justified, and its effect on the data explained. In this framework, we aim at providing data scientists with facilities to gain an in-depth understanding of how each step in the pipeline affects the data, from the raw input to training sets ready to be used for learning. Starting from an extensible set of data preparation operators commonly used within a data science setting, in this work we present a provenance management infrastructure for generating, storing, and querying very granular accounts of data transformations, at the level of individual elements within datasets whenever possible. Then, from the formal definition of a core set of data science preprocessing operators, we derive a provenance semantics embodied by a collection of templates expressed in PROV, a standard model for data provenance. Using those templates as a reference, our provenance generation algorithm generalises to any operator with observable input/output pairs. We provide a prototype implementation of an application-level provenance capture library to produce, in a semi-automatic way, complete provenance documents that account for the entire pipeline. We report on the ability of that reference implementation to capture provenance in real ML benchmark pipelines and over TCP-DI synthetic data. We finally show how the collected provenance can be used to answer a suite of provenance benchmark queries that underpin some common pipeline inspection questions, as expressed on the Data Science Stack Exchange.

Successful data-driven science requires a complex combination of data engineering pipelines and data modelling techniques. Robust and defensible results can only be achieved when each step in the pipeline that is designed to clean, transform and alter data in preparation for data modelling can be justified, and its effect on the data explained. The DPDS toolkit presented in this paper is designed to make such justification and explanation process an integral part of data science practice, adding value while remaining as un-intrusive as possible to the analyst. Catering to the broad community of python/pandas data engineers, DPDS implements an observer pattern that is able to capture the fine-grained provenance associated with each individual element of a dataframe, across multiple transformation steps. The resulting provenance graph is stored in Neo4j and queried through a UI, with the goal of helping engineers and analysts to justify and explain their choice of data operations, from raw data to model training, by highlighting the details of the changes through each transformation.

Abstract We focus on the automatic detection of communities in large networks, a challenging problem in many disciplines (such as sociology, biology, and computer science). Humans tend to associate to form families, villages, and nations. Similarly, the elements of real-world networks naturally tend to form highly connected groups. A popular model to represent such structures is the clique, that is, a set of fully interconnected nodes. However, it has been observed that cliques are too strict to represent communities in practice. The k-plex relaxes the notion of clique, by allowing each node to miss up to k connections. Although k-plexes are more flexible than cliques, finding them is more challenging as their number is greater. In addition, most of them are small and not significant. In this paper we tackle the problem of finding only large k-plexes (i.e., comparable in size to the largest clique) and design a meta-algorithm that can be used on top of known enumeration algorithms to return only significant k-plexes in a fraction of the time. Our approach relies on: (1) methods for strongly reducing the search space and (2) decomposition techniques based on the efficient computation of maximal cliques. We demonstrate experimentally that known enumeration algorithms equipped with our approach can run orders of magnitude faster than full enumeration.

When composing multiple preferences characterizing the most suitable results for a user, several issues may arise. Indeed, preferences can be partially contradictory, suffer from a mismatch with the level of detail of the actual data, and even lack natural properties such as transitivity. In this paper we formally investigate the problem of retrieving the best results complying with multiple preferences expressed in a logic-based language. Data are stored in relational tables with taxonomic domains, which allow the specification of preferences also over values that are more generic than those in the database. In this framework, we introduce two operators that rewrite preferences for enforcing the important properties of transitivity, which guarantees soundness of the result, and specificity, which solves all conflicts among preferences. Although, as we show, these two properties cannot be fully achieved together, we use our operators to identify the only two alternatives that ensure transitivity and minimize the residual conflicts. Building on this finding, we devise a technique, based on an original heuristics, for selecting the best results according to the two possible alternatives. We finally show, with a number of experiments over both synthetic and real-world datasets, the effectiveness and practical feasibility of the overall approach.

Data processing pipelines that are designed to clean, transform and alter data in preparation for learning predictive models, have an impact on those models' accuracy and performance, as well on other properties, such as model fairness. It is therefore important to provide developers with the means to gain an in-depth understanding of how the pipeline steps affect the data, from the raw input to training sets ready to be used for learning. While other efforts track creation and changes of pipelines of relational operators, in this work we analyze the typical operations of data preparation within a machine learning process, and provide infrastructure for generating very granular provenance records from it, at the level of individual elements within a dataset. Our contributions include: (i) the formal definition of a core set of preprocessing operators, and the definition of provenance patterns for each of them, and (ii) a prototype implementation of an application-level provenance capture library that works alongside Python. We report on provenance processing and storage overhead and scalability experiments, carried out over both real ML benchmark pipelines and over TCP-DI, and show how the resulting provenance can be used to answer a suite of provenance benchmark queries that underpin some of the developers' debugging questions, as expressed on the Data Science Stack Exchange.

We present a novel approach for the detection of 2-plexes, a popular relaxation of cliques used for modeling network communities. Specifically, with the purpose of identifying theoretically sound methods for community detection on a large scale, we introduce the first shared-nothing distributed algorithm for this problem. This result opens a new research direction for scalable community detection. Our proposal has three main ingredients: (i) we reduce the problem of finding 2-plexes to that of finding cliques; (ii) we leverage known algorithms for fast computation of cliques; (iii) we exploit a decomposition technique for a distributed shared-nothing computation. Preliminary experiments on a 10-nodes cluster running Spark confirm the effectiveness of our approach.

The definition of mappings between heterogeneous schemas is a critical activity of any database application. Existing tools provide high level interfaces for the discovery of correspondences between elements of schemas, but schema mappings need to be manually specified every time from scratch, even if the scenario at hand is similar to one that has already been addressed. The problem is that schema mappings are precisely defined over a pair of schemas and cannot directly be reused on different scenarios. We tackle this challenge by generalizing schema mappings as meta-mappings: formalisms that describe transformations between generic data structures called meta-schemas. We formally characterize schema mapping reuse and explain how meta-mappings are able to: (i) capture enterprise knowledge from previously defined schema mappings and (ii) use this knowledge to suggest new mappings. We develop techniques to infer meta-mappings from existing mappings, to organize them into a searchable repository, and to leverage the repository to propose to users mappings suitable for their needs. We study effectiveness and efficiency in an extensive evaluation over real-world scenarios and show that our system can infer, store, and search millions of meta-mappings in seconds.

The huge diversity of database technologies in use inside organizations pose today new challenges of data management and integration. Polystores provide a solution to this scenario based on a loosely coupled integration of data sources and the direct access, with the local language, to each storage engine for exploiting its distinctive features. However, given the absence of a global schema, it is hard to know if a query to one system can be satisfied with data stored elsewhere in the polystore. We address this issue by introducing query augmentation, a data manipulation operator for polystores based on the automatic enrichment of the answer to a local query with related data in the rest of the polystore. Augmentation can be used to implement two effective methods for data access in polystores: augmented search and augmented exploration. We show that they provide effective tools for information discovery in polystores that avoid middleware layers, abstract query languages, and shared data models. We also illustrate the design of QUEPA, a system that fully implements our approach in an efficient way. A comprehensive campaign of experiments done with QUEPA shows that our approach is feasible and, unlike other approaches, scales nicely as the polystore grows in the number of stores and size of databases.

K-plexes are a formal yet flexible way of defining communities in networks. They generalize the notion of cliques and are more appropriate in most real cases: while a node of a clique C is connected to all other nodes of C, a node of a k-plex may miss up to k connections. Unfortunately, computing all maximal k-plexes is a gruesome task and state-of-the-art algorithms can only process small-size networks. In this paper we propose a new approach for enumerating large k-plexes in networks that speeds up the search by several orders of magnitude, leveraging on (i) methods for strongly reducing the search space and (ii) efficient techniques for the computation of maximal cliques. Several experiments show that our strategy is effective and is able to increase the size of the networks for which the computation of large k-plexes is feasible from a few hundred to several hundred thousand nodes.

Paddling in a data lake is strenuous for a data scientist. Being a loosely-structured collection of raw data with little or no meta-information available, the difficulties of extracting insights from a data lake start from the initial phases of data analysis. Indeed, data preparation, which involves many complex operations (such as source and feature selection, exploratory analysis, data profiling, and data curation), is a long and involved activity for navigating the lake before getting precious insights at the finish line. In this framework, we demonstrate KAYAK, a framework that supports data preparation in a data lake with ad-hoc primitives and allows data scientists to cross the finish line sooner. KAYAK takes into account the tolerance of the user in waiting for the primitives' results and it uses incremental execution strategies to produce informative previews of these results. The framework is based on a wise management of metadata and on features that limit human intervention, thus scaling smoothly when the data lake evolves.

The detection of communities in social networks is a challenging task. A rigorous way to model communities considers maximal cliques, that is, maximal subgraphs in which each pair of nodes is connected by an edge. State-of-the-art strategies for finding maximal cliques in very large networks decompose the network in blocks and then perform a distributed computation. These approaches exhibit a trade-off between efficiency and completeness: decreasing the size of the blocks has been shown to improve efficiency but some cliques may remain undetected since high-degree nodes, also called hubs, may not fit with all their neighborhood into a small block. In this paper, we present a distributed approach that, by suitably handling hub nodes, is able to detect maximal cliques in large networks meeting both completeness and efficiency. The approach relies on a two-level decomposition process. The first level aims at recursively identifying and isolating tractable portions of the network. The second level further decomposes the tractable portions into small blocks. We demonstrate that this process is able to correctly detect all maximal cliques, provided that the sparsity of the network is bounded, as it is the case of real-world social networks. An extensive campaign of experiments confirms the effectiveness, efficiency, and scalability of our solution and shows that, if hub nodes were neglected, significant cliques would be undetected.

Polystore systems (or simply polystores) have been recently proposed to support a common scenario in which enterprise data are stored in a variety of database technologies relying on different data models and languages. Polystores provide a loosely coupled integration of data sources and support the direct access, with the local language, to each specific storage engine to exploit its distinctive features. Given the absence of a global schema, new challenges for accessing data arise in these environments. In fact, it is usually hard to know in advance if a query to a specific data store can be satisfied with data stored elsewhere in the polystore. QUEPA addresses these issues by introducing augmented search and augmented exploration in a polystore, two access methods based on the automatic enrichment of the result of a query over a storage system with related data in the rest of the polystore. These features do not impact on the applications running on top of the polystore and are compatible with the most common database systems. QUEPA implements in this way a lightweight mechanism for data integration in the polystore and operates in a plug-and-play mode, thus reducing the need for ad-hoc configurations and for middleware layers involving standard APIs, unified query languages or shared data models. In our demonstration audience can experience with the augmentation construct by using the native query languages of the database systems available in the polystore.

We present NYAYA, a flexible system for the management of large-scale semantic data which couples a general-purpose storage mechanism with efficient ontological query answering. NYAYA rapidly imports semantic data expressed in different formalisms into semantic data kiosks. Each kiosk exposes the native ontological constraints in a uniform fashion using data log±, a very general rule-based language for the representation of ontological constraints. A group of kiosks forms a semantic data market where the data in each kiosk can be uniformly accessed using conjunctive queries and where users can specify user-defined constraints over the data. NYAYA is easily extensible and robust to updates of both data and meta-data in the kiosk and can readily adapt to different logical organizations of the persistent storage. In the demonstration, we will show the capabilities of NYAYA over real-world case studies and demonstrate its efficiency over well-known benchmarks.

We present Nyaya, a system for the management of Semantic-Web data which couples a general-purpose and extensible storage mechanism with efficient ontology reasoning and querying capabilities. Nyaya processes large Semantic-Web datasets, expressed in multiple formalisms, by transforming them into a collection of Semantic Data Kiosks. Nyaya uniformly exposes the native meta-data of each kiosk using the datalog+- language, a powerful rule-based modelling language for ontological databases. The kiosks form a Semantic Data Market where the data in each kiosk can be uniformly accessed using conjunctive queries and where users can specify user-defined constraints over the data. Nyaya is easily extensible and robust to updates of both data and meta-data in the kiosk and can readily adapt to different logical organization of the persistent storage. The approach has been experimented using well-known benchmarks, and compared to state-of-the-art research prototypes and commercial systems.

Radio Frequency Identification (RFID) technology plays a key role in supply chains and a challenging problem is the effective and efficient management of the enormous volume of data generated by such systems. In this paper, we propose a new framework for storing and querying a large amount of RFID data. The approach is based on a compression technique that allows a significant saving of space according to a suitable notion of aggregates over RFID data and a logical representation of these aggregates. We also propose an indexing technique for aggregates of RFID data that guarantees the efficient execution of an important class of queries. We finally present the architecture of a tool implementing our approach and demonstrate, with a number of experimental results made with this tool, the feasibility and effectiveness of the underlying techniques.

Context-awareness is considered today a desirable facility of modern Web information systems, given the large variety of non-traditional client devices used to access such applications. In this scenario, a fundamental requirement is the ability to capture and manipulate, in a flexible way, diverse context information, such as, among many others, the device capabilities, the preferences of the user, the network QoS, and the location. In this paper we propose a general framework supporting the representation and management of a large variety of context information. To this end, we first introduce a general data model that embeds the basic constructs commonly used to represent context information. We then define a number of basic primitives for the manipulation of context data. We finally describe how this framework can be profitably used to support different well-known applications where context management can provide an important add-on.

DaWaII (Data Warehouse IntegratIon) is a tool supporting the various activities related to the integration of multidimensional data. This problem arises in common scenarios where there is the need to combine independently developed data warehouses. Actually, a today common practice for building a data warehouse is to develop a collection of integrated data marts, each of which provide a dimensional view of a single business process. These data marts should be based on shared dimensions but very often, even within the same company, designers develop their data marts independently and it turns out that their integration is a difficult task. Indeed, the problem arises in other common cases. For instance, when different companies get involved in a federated project or when there is the need to combine a proprietary data warehouse with external information, for instance, with multidimensional data wrapped from the Web.

In this paper we propose a comprehensive framework for therepresentation and translation of context information in adaptiveWeb based applications.We consider the various formats used today to express context data (HTTPheader, XML files over specific DTD's, RDF, CC/PP, and so on) and show thatthe primitives adopted by all of them can be classified into a ratherlimited set of basic types. We then define, building on these basic types,a general formalism for context information called GPM that embeds theseheterogeneous formats. It turns out that GPM can be used to model a varietyof contexts in a uniform way and therefore provides a powerful toolsupporting the design and analysis of context aware applications.We also address the problem of translating context information from onerepresentation into another. This is achieved by using GPM as anintermediate representation level. Finally, we describe architecture andfunctionality of a prototype implementing the translation process andillustrate experimental results supporting the effectiveness of the overallapproach.

In this paper, we present a rule-based approach supporting the automatic adaptation in Web Information Systems. The approach relies on the general notions of profile and configuration. Special rules are used to specify, in a declarative way, how to build a configuration that satisfies the requirements of adaptation for a profile. The rule evaluation technique guarantees that different contexts and orthogonal requirements of adaptation, possibly not fixed in advance, can be taken into account in the adaptation process.

We propose a comprehensive framework for the management and the exchange of (semi) structured Web data, described according to a variety of formats and models. We consider various schema definition languages for XML (DTD, XML Schema and XDR) a model for semistructured data (OEM) and a model used to store Web data (the relational model) and show that the primitives adopted by all of them can be classified into a rather limited set of basic types. We then define, building on these basic types, a notion of "meta-formalism" that can be used to describe, in a uniform way, these heterogeneous representations of Web data. In this framework, the translation of schemes and instances between different models are based on the translations of the involved primitives. Complex translations can be then obtained by simply combining a number of predefined operations, which implement standard translations between primitives. Moreover we show that, for translating between any pair of models, it is sufficient to define a number of translations which is linear in the number of models. These results can be used to support a number of involved Web-related activities like: information exchange between different organizations, integration of data coming from heterogeneous information sources, storage of native XML data in a DBMS and publishing of existing structured (relational) data in XML.

We report on the design of a novel architecture for data warehousing based on the introduction of an explicit "logical" layer to the traditional data warehousing framework. This layer serves to guarantee a complete independence of OLAP applications from the physical storage structure of the data warehouse and thus allows users and applications to manipulate multidimensional data ignoring implementation details. For example, it makes possible the modification of the data warehouse organization (e.g. MOLAP or ROLAP implementation, star scheme or snowflake scheme structure) without influencing the high level description of multidimensional data and programs that use the data. Also, it supports the integration of multidimensional data stored in heterogeneous OLAP servers. We propose [Formula: see text], a simple data model for multidimensional databases, as the reference for the logical layer. [Formula: see text] provides an abstract formalism to describe the basic concepts that can be found in any OLAP system (fact, dimension, level of aggregation, and measure). We show that [Formula: see text] databases can be implemented in both relational and multidimensional storage systems. We also show that [Formula: see text] can be profitably used in OLAP applications as front-end. We finally describe the design of a practical system that supports the above logical architecture; this system is used to show in practice how the architecture we propose can hide implementation details and provides a support for interoperability between different and possibly heterogeneous data warehouse applications.

We address the issue of designing effective query languages for OLAP databases. The basis of our investigation is MD, a new data model for multidimensional databases that, unlike other multidimensional models, is independent of any specific implementation and as such provides a clear separation between practical and conceptual aspects. In this framework, we present and compare two query languages, based on different paradigms, for OLAP databases. The first language is algebraic and provides an effective way to manipulate multidimensional data in a procedural fashion. Although this language is clean and powerful, it is clearly not suited for final users. We therefore propose a high-level graphical language that allows the user to specify analytical queries in a natural and intuitive way. It turns out that the two languages have the same expressive power.

MDM is a tool that enables the users to define schemes of different data models and to perform translations of schemes from one model to another. These functionalities can be at the basis of a customizable and integrated CASE environment supporting the analysis and design of information systems. MDM has two main components: the Model Manager and the Schema Manager. The Model Manager supports a specialized user, the model engineer, in the definition of a variety of models, on the basis of a limited set of metaconstructs covering almost all known conceptual models. The Schema Manager allows designers to create and modify schemes over the defined models, and to generate at each time a translation of a scheme into any of the data models currently available. Translations between models are automatically derived, at definition time, by combining a predefined set of elementary transformations, which implement the standard translations between simple combinations of constructs.

The authors address the problem of providing a homogeneous framework for integrating, in a database environment, active rules, which allow the specification of actions to be executed whenever certain events take place, and deductive rules, which allow the specification of deductions in a logic programming style. Actually, it is widely recognized that both kinds of rules enhance the capabilities of database systems since they provide very natural mechanisms for the management of various important activities (e.g., knowledge representation, complex data manipulation, integrity constraint enforcement, view maintenance). However, in spite of their strong relationship, little work has been done on the unification of these powerful paradigms. They present a rule-based language with an event-driven semantics that allows programmers to express both active and deductive computations. The language is based on a new notion of production rules whose effect is both a change of state and an answer to a query. By using several examples, they show that this simple language schema allows one to uniformly define different computations on data, including complex data manipulations, deductive evaluations, and active rule processing. They define the semantics of the language and then describe the architecture of a preliminary implementation of the language. Finally, they report on the application and experience of using the language.

Describes operational aspects of a novel approach to active rule processing based on a transaction transformation technique. A user-defined transaction, which is viewed as a sequence of atomic database updates forming a semantic unit, is translated by means of active rules into a new transaction that explicitly includes the additional updates due to active rule processing. It follows that the execution of the new transaction in a passive environment corresponds to the execution of the original transaction within the active environment defined by the given rules. Both immediate and deferred execution models are considered. The approach presents two main features. First, it relies on a well known formal basis that allow us to derive solid results on equivalence, confluence and optimization issues. Second, it is easy to implement as it does not require any specific run-time support.>

The problem of updating databases through interfaces based on the weak instance model is studied, thus extending previous proposals that considered them only from the query point of view. Insertions and deletions of tuples are considered. As a preliminary tool, a lattice on states is defined, based on the information content of the various states. Potential results of an insertion are states that contain at least the information in the original state and that in the new tuple. Sometimes there is no potential result, and in the other cases there may be many of them. We argue that the insertion is deterministic if the state that contains the information common to all the potential results (the greatest lower bound, in the lattice framework) is a potential result itself. Effective characterizations for the various cases exist. A symmetric approach is followed for deletions, with fewer cases, since there are always potential results; determinism is characterized as a consequence.

The weak instance model is a framework to consider the relations in a database as a whole, regardless of the way attributes are grouped in the individual relations. Queries and updates can be performed involving any set of attributes. The management of updates is based on a lattice structure on the set of legal states, and inconsistencies and ambiguities can arise

Database updates have recently received much more attention than in the past. In this trend, a solid foundation is provided to the problem of updating databases through interfaces based on the weak instance model. Insertions and deletions of tuples are considered.