Predictive approach for schema evolution

In today's companies and organizations, databases are omnipresent. They are the means to represent and store information. Therefore, they must evolve whenever the information architecture (semantic and structure) changes. Databases are subject to evolution for several reasons that include the changes to the real-world or the emergence of new database user requirements. We may also consider non representational and non-functional aspects such as the technology and performance requirements. Those can also compel the database designer or administrator to change the database in order to be more optimal and adapted to those requirements. This thesis proposes to address the schema evolution problem by anticipating the potential changes for the evolution of the schema. The approach adopts the a priori perspective i.e. to plan in advance for a possible solution that makes a schema evolve over time. Such a solution works with both a set of assumptions and techniques. The elaborated approach is based on different components: • First, we propose to develop a schema repository which contains a wide number of heterogeneous schemas and their historical versions. This repository serves in a series of operations that are important for the study of the schemas such as selecting the pertinent schemas, building the change matrices and performing the data-mining process. • Second, we propose to develop a requirements ontology, meaning to say a domain ontology that describes the current concepts of a database as well as the concepts that represent the potential future requirements that could be part of the evolution. The method of construction of this ontology includes several phases such as the preparation of the data for this ontology, the establishment of the data-dictionary besides change perspectives that store the concepts that are associated to other concepts by relationships resulting from the application of the data-mining process, the evaluation of the domain ontology using a graph structure and finally the construction of the ontology using a set of procedures. • Third, we propose to develop a predicted schema which is a database schema that contains two types of metadata. The metadata, that represents current entities of the database and the metadata that represents potential future entities. The predicted schema has two methods of representation: the multi-representation strategy and the predicted design repository schemas strategy. The schemas with the multi-representation strategy are particular versions of schemas whereas the schemas with the predicted design repository schemas are particular repositories of schemas. • Finally, we propose a case study and an analysis of the approach. The case study to better understand how this approach works and the analysis to show its feasibility, the positive as well as negative aspects.

Leveraging User-Generated Content for Information Discovery on the Web

Adriana Budura

The large-scale adoption of the Web 2.0 paradigm has revolutionized the way we interact with the Web today. End-users, so far mainly passive consumers of information are now becoming active information producers, creating, uploading, and commenting on all types of digital content. As a consequence, the Web has evolved from a collection of static HTML pages to a highly interactive system, where information is being published and consumed at high rates. This has tremendously increased the amount of data available on the Web today, which brings about new challenges in terms of information management. At the same time, the increased user participation represents a new and extremely valuable source of data. While interacting with different Web 2.0 portals, users freely provide all types of information, such as annotations describing the shared resources, friendship links connecting similar users, etc., which can be exploited in order to improve the methods designed to manage online content. A particularly interesting example of user-generated data are the so-called social annotations, that users attach to resources in the context of collaborative tagging systems. This kind of meta-information opens up new opportunities for improved content search, new means to organize personal data, and ways of mining user profiles based on their annotations. Virtual friendship connections between users, as we can observe in social networks, are another rich source of information as they often group users with similar interests together, give means to study information diffusion and open ground to enhanced expert finding tasks. In this thesis, we leverage information extracted from user-generated data, in order to solve current information management problems, such as data retrieval, mining and integration. We explore different scenarios, where online content is enriched with user-defined meta-information and we identify specific problems, which we solve by leveraging this information. We start by addressing the problem of context-based information discovery in collaborative tagging systems, where we take advantage of user-defined entity graphs – such as a citation graph of publications or a friendship graph of users. In this setting, effective search solutions require a certain amount of annotations, however, content is often poorly annotated. We therefore propose a method that exploits the context-related information embedded in the graph structure, in order to automatically infer new annotations. Our approach propagates tags along the edges of the graph, based on the assumption that the neighborhood of a resource holds additional information about the resource itself. We see a similar graph structure in social communities, where users are connected via friendship links and where the neighborhood of a user reflects her community of interest. We adopt the hypothesis that users mainly annotate resources of interest to them and interpret the annotations (i.e., tags) as an interest profile. Hence, we propose a novel framework for tag-based community detection in collaborative tagging systems, that considers both the tagging behavior of users, as well as their friendship graph. Based on a set of tags, our method returns a closely connected community of users, whose tags jointly cover the initial set. In order to further investigate the issue of generating user profiles based on their annotations, we switch our attention from the open Web to an enterprise setting. Social software, such as collaborative tagging systems, has also been included in the enterprise space, where it opens up new opportunities to address the problem of expert search. We take advantage of the data extracted from two enterprise-internal portals and explore correlations between the users‚ tagging behavior and their corresponding areas of expertise. Based on these correlations, we devise a method that derives expertise profiles for users. Finally, we investigate how user-generated meta-information can be exploited in the domain of structured data on the Web, i.e., data that is organized according to the relational model and complies to application-specific schemas. In order to enable transparent search solutions on such data, schema heterogeneity needs to be overcome by means of data integration techniques. We explore how such techniques can benefit from the user-generated meta-information in the form of links between similar entries in different databases. Based on these links, we devise a method to create mappings between the elements of different schemas from a real-world collection of online bioinformatic databases.

EPFL2010

Predictive Approach for Database Schema Evolution

Hassina Bounif

Information systems, including their core databases need to meet changing user requirements and adhere to evolving business strategies. Traditional database evolution techniques focus on reacting to change to smoothly perform schema evolution operations and to propagate corresponding updates to the data as effectively as possible. Adopting such posterior solutions to such changes generates high costs in human resources and financial support. We advocate an alternate solution: a predictive approach to database evolution. In this approach, we anticipate future changes during the standard requirements analysis phase of schema development. Our approach enables potential future requirements to be planned for, as well as the standard, determining what data is to be stored and what access is required. This preparation contributes significantly in the ability of the database schema to adapt to future changes and to estimate their relative costs.

Idea Group2006

Graph Representation Learning with Optimal Transport: Analysis and Applications

Effrosyni Simou

In several machine learning settings, the data of interest are well described by graphs. Examples include data pertaining to transportation networks or social networks. Further, biological data, such as proteins or molecules, lend themselves well to graph-structured descriptions. In such settings, it is desirable to design representation learning algorithms that can take into account the information captured by the underlying structure. This thesis focuses on providing new methods to ingrain geometrical information in end-to-end deep learning architectures for graphs through the use of elements from Optimal Transport theory.First, we consider the setting where the data can be described by a fixed graph. In this setting, each datapoint corresponds to a node of the graph and the edges among nodes signify their pairwise relations. We propose an autoencoder architecture that consists of a linear layer in the encoder and a novel Wasserstein barycentric layer at the decoder. Our proposed barycentric layer takes into account the underlying geometry through the diffusion distance of the graph and provides a way to obtain structure-aware, non-linear interpolations, which lead to directly interpretable node embeddings that are stable to perturbations of the graph structure. Further, the embeddings obtained with our proposed autoencoder achieve competitive or superior results compared to state-of-the-art methods in node classification tasks.Second, we consider the setting where the data consist of multiple graphs. In that setting, the graphs can be of varying size and, therefore, a global pooling operation is needed in order to obtain representations of fixed size and enable end-to-end learning with deep networks. We propose a global pooling operation that optimally preserves the statistical properties of the representations. In order to do so, we take into account the geometry of the representation space and introduce a global pooling layer that minimizes the Wasserstein distance between a graph representation and its pooled counterpart, of fixed size. This is achieved by performing a Wasserstein gradient flow with respect to the pooled representation. Our proposed method demonstrates promising results in the task of graph classification.Overall, in this thesis we provide new methods for incorporating geometrical information in end-to-end deep learning architectures for graph structured data. We believe that our proposals will contribute to the development of algorithms that learn meaningful representations and that take fully into account the geometry of the data under consideration.