This paper demonstrates RUBEN, an interactive tool for discovering minimal rules to explain the outputs of retrieval-augmented large language models (LLMs) in data-driven applications. We leverage novel pruning strategies to efficiently identify a minimal set of rules that subsume all others. We further demonstrate novel applications of these rules for LLM safety, specifically to test the resiliency of safety training and effectiveness of adversarial prompt injections.

The task of searching over large keyword graphs aims to identify a subgraph where the nodes collectively cover the input query keywords. Although finding an exact solution to this problem is NP-hard, we address it by proposing a novel graph neural network representation learning technique specifically tailored for graphs with missing information. We propose a novel keyword graph representation learning method that incorporates complementary aspects of graphs: global, local, adjusted, and feature semantics. Considering these multiple aspects, our approach remains robust and resilient to missing information. We adopt and fine-tune a transformer-based model to aggregate the various features of a graph to generate rich representations, recognizing the pivotal role of keywords in this task. We show through experiments on real-world data that our method outperforms the state-of-the-art approaches and is particularly robust in the face of missing values, underscoring its ability to effectively handle incomplete graphs.

Modern database systems such as IBM Db2 have many configurable parameters (“knobs”) which must be precisely adjusted (“tuned”) to ensure optimal workload performance. Manual tuning of these settings is challenging, even for seasoned experts. We introduce the design of, and a demonstration plan for, Db2une, an automated, query-aware tuning system employing deep-learning techniques to enhance performance while also conserving resources. We showcase how Db2une interactively tunes data systems to boost performance, and how its query representation model, QBERT, aids users in understanding the query plans generated from complex analytical workloads.

Modern database systems, such as IBM Db2, rely on cost-based optimizers to improve workload performance. However, their decision-making processes are difficult to interpret. Tuning them for specific workloads remains challenging due to their complexity and numerous configuration options. Automatic tuning tools often rely on black-box machine-learning models, which lack interpretability, hindering expert trust and debugging. We present GEX, a system that provides interpretable insights into database optimizer behavior using explainable AI techniques. By employing saliency maps generated from surrogate models, GEX guides experts in system tuning tasks such as statistical view creation, configuration parameter adjustment, and query rewrite. Our experimental results demonstrate that GEX enhances performance and ensures transparency, addressing key challenges in data systems tuning.

Expert search and team formation systems operate on collaboration networks, with nodes representing individuals, labeled with their skills, and edges denoting collaboration relationships. Given a keyword query corresponding to the desired skills, these systems identify experts that best match the query. However, state-of-the-art solutions to this problem lack trans-parency. To address this issue, we propose ExES, a tool designed to explain expert search and team formation systems using factual and counterfactual methods from the field of explainable artificial intelligence (XAI). ExES uses factual explanations to highlight important skills and collaborations, and counterfactual explanations to suggest new skills and collaborations to increase the likelihood of being identified as an expert. To speed up the explanation search, ExES implements a suite of pruning techniques. When tasked with explaining recent expert search and team formation systems, our pruning strategies can make ExES an order of magnitude faster than exhaustive explanation search, while still producing concise and actionable explanations.

Expert search systems operate on collaboration networks with nodes representing individuals, labeled with their skills, and edges denoting collaboration relationships. Given a query corresponding to a set of desired skills, these systems identify teams of experts that best match the query. However, state-of-the-art solutions to this problem lack transparency and interpretability. To address this issue, we demonstrate ExES, an interactive tool designed to explain expert search systems. Our system leverages saliency and counterfactual methods from the field of explainable artificial intelligence (XAI). Conference participants will use ExES to understand why individuals were or were not included in the query results and what individuals could do, in terms of perturbing skills or connections, to be included or excluded in the results.

This paper demonstrates RAGE, an interactive tool for explaining Large Language Models (LLMs) augmented with retrieval capabilities; i.e., able to query external sources and pull relevant information into their input context. Our explanations are counterfactual in the sense that they identify parts of the input context that, when removed, change the answer to the question posed to the LLM. RAGE includes pruning methods to navigate the vast space of possible explanations, allowing users to view the provenance of the produced answers.

In an era where artificial intelligence (AI) is re-shaping countless aspects of society, we present a forward-looking perspective for enhancing the explainability of large language models (LLMs), with a particular focus on the retrieval-augmented generation (RAG) prompting technique. We motivate the urgency for developing techniques to explain LLM decision-making behaviour, especially as these models are deployed in critical sectors. Central to this effort is RAGE, our novel explain-ability tool that can trace the provenance of an LLM's answer back to external knowledge sources provided via RAG. RAGE builds upon established explainability techniques to recover citations for LLM answers, identify context biases, and mine answer rules. Through our novel explainability formulations and practical use cases, we chart a course toward more transparent and trustworthy AI technologies.

Explainable AI methods have been proposed to help interpret complex models, e.g., by assigning importance scores to model features or perturbing the features in a way that changes the prediction. These methods apply to one model at a time, but in practice, engineers usually select from many candidate models and hyperparameters. To assist with this task, we demonstrate Camo:a tool that explains consensus among multiple models. Conference participants will interact with CAMO using a variety of models and datasets, to explore 1) consensus patterns, such as subsets of the test dataset or intervals within feature domains where models disagree, and 2) data perturbations that would make conflicting models agree (and consistent models disagree).

Deploying machine-learning (ML) models is difficult and fraught with peril. Replacing an old model with a new one may introduce new biases and weaknesses that were easily over-looked. Unlike software updates where we have best practices (unit tests and the like), such best practices for ML are only now evolving. The ML deployment pipeline suffers further from a fracture: on the one side, one has the “data-science” (DS) pipeline, in which one extracts, loads, transforms, and maintains the vast lakes of data the models need to be trained on; on the other side, one has the “ML” pipeline in which experts test and evaluate models, often comparing many, for fitness for the task. To progress ultimately, these two pipelines must be integrated into a single DS/ML pipeline. We posit that doing so rests on model explainability and comparison.

Modern database systems including IBM Db2 have numerous parameters, "knobs," that require precise configuration to achieve optimal workload performance. Even for experts, manually "tuning" these knobs is a challenging process. We present Db2une, an automatic query-aware tuning system that leverages deep learning to maximize performance while minimizing resource usage. Via a specialized transformer-based query-embedding pipeline we name QBERT, Db2une generates context-aware representations of query workloads to feed as input to a stability-oriented, on-policy deep reinforcement learning model. In Db2une, we introduce a multi-phased, database meta-data driven training approach---which incorporates cost estimates, interpolation of these costs, and database statistics---to efficiently discover optimal tuning configurations without the need to execute queries. Thus, our model can scale to very large workloads, for which executing queries would be prohibitively expensive. Through experimental evaluation, we demonstrate Db2une's efficiency and effectiveness over a variety of workloads. We compare it against the state-of-the-art query-aware tuning systems and show that the system provides recommendations that surpass those of IBM experts.

Team formation is concerned with the identification of a group of experts who have a high likelihood of effectively collaborating with each other to satisfy a collection of input skills. Solutions to this task have mainly adopted graph operations and at least have the following limitations: (1) they are computationally demanding, as they require finding shortest paths on large collaboration networks; (2) they use various types of heuristics to reduce the exploration space over the collaboration network to become practically feasible; therefore, their results are not necessarily optimal; and (3) they are not well-suited for collaboration network structures given the sparsity of these networks. Our work proposes a variational Bayesian neural network architecture that learns representations for teams whose members have collaborated with each other in the past. The learned representations allow our proposed approach to mine teams that have a past collaborative history and collectively cover the requested desirable set of skills. Through our experiments, we demonstrate that our approach shows stronger performance compared to a range of strong team formation techniques from both quantitative and qualitative perspectives.

In this demonstration paper, we describe iORDER, a tool that identifies implicit domain orders in data, such as Small Medium Large. iORDER extends the machinery of order dependency discovery to identify and rank interesting orders. Using real-world data, we showcase how implicit orders help users interpret the semantics of ordered data, how to interactively validate implicit orders to aid in the discovery process, and how to apply implicit orders to applications including data profiling, data mining and knowledge bases.

Nowadays, data systems, including IBM Db2 have dozens of knobs (configuration parameters). These knobs significantly affect the runtime of queries. We present the design of and a demonstration plan for a query-informed, efficient tuning system, BLUTune, which utilizes deep reinforcement learning to tune configurations. Using synthetic and real workloads, we demonstrate how BLUTune can help users to understand the semantics of analytical queries, including their execution plans, and interactively tune data systems to improve performance.

Towards better explainability in the field of information retrieval, we present CREDENCE, an interactive tool capable of generating counterfactual explanations for document rankers. Embracing the unique properties of the ranking problem, we present counterfactual explanations in terms of document perturbations, query perturbations, and even other documents. Additionally, users may build and test their own perturbations, and extract insights about their query, documents, and ranker.

Modern data systems such as IBM Db2 have hundreds of system configuration parameters, ''knobs", which heavily influence the performance of business queries. Manual configuration, ''tuning," by experts is painstaking and time consuming. We propose a query informed tuning system called BLUTune which uses machine learning (ML)-deep reinforcement learning based on advantage actor critic neural networks-to tune configurations within defined resource constraints. We translate high-dimensional query execution plans (QEPs) into a low-dimensional embedding space (QEP2Vec) for input into the ML models. To scale to complex and large workloads, we bootstrap the training process through transfer learning. We first train our model based on the estimated cost of queries; we then fine-tune it based on actual query execution times. We demonstrate by an experimental study over various synthetic and real-world workloads BLUTune's efficiency and effectiveness.

Most real-world data come with explicitly defined domain orders; e.g., lexicographic for strings, numeric for integers, and chronological for time. Our goal is to discover implicit domain orders that we do not already know; for instance, that the order of months in the Chinese Lunar calendar is Corner$<$Apricot$<$Peach. To do so, we enhance data profiling methods by discovering implicit domain orders in data through order dependencies. We enumerate tractable special cases and show that the general case is NP-complete but can be effectively handled by a SAT solver. We also devise an interestingness measure to rank the discovered implicit domain orders. Based on an extensive suite of experiments with real-world data, we establish the efficacy of our algorithms.

We present the design of and a demonstration plan for abcOD, a tool for efficiently discovering approximate band conditional order dependencies (abcODs) from data. abcOD utilizes a dynamic programming algorithm based on a longest monotonic band. Using real datasets, we demonstrate how the discovered abcODs can help users understand ordered data semantics, identify potential data quality problems, and interactively clean the data.

Real graphs often contain edge and node weights, representing, for instance, penalty, distance or uncertainty. We study the problem of keyword search over weighted node-labeled graphs, in which a query consists of a set of keywords and an answer is a subgraph whose nodes contain the keywords. We evaluate answers using three ranking strategies: optimizing edge weights, optimizing node weights, and a bi-objective combination of both node and edge weights. We prove that optimizing node weights and the bi-objective function are NP-hard. We propose an algorithm that optimizes edge weights and has an approximation ratio of two for the unique node enumeration paradigm. To optimize node weights and the bi-objective function, we propose transformations that distribute node weights onto the edges. We then prove that our transformations allow our algorithm to also optimize node weights and the bi-objective function with the same approximation ratio of two. Notably, the proposed transformations are compatible with existing algorithms that only optimize edge weights. We empirically show that in many natural examples, incorporating node weights (both keyword holders and middle nodes) produces more relevant answers than ranking methods based only on edge weights. Extensive experiments over real-life datasets verify the effectiveness and efficiency of our solution.

Query optimization has long been fundamental for database systems. There are cracks in the edifice, however, as the complexity of modern query workloads outpace what database systems can manage well. Automatic tools are needed for database vendors, such as IBM with Db2, to help customers troubleshoot their performance problems, as manual troubleshooting is painstaking. To manage complex and large workloads, we develop a distributed system called dGALO that learns recurring problem patterns in query plans over workloads. dGALO employs these problem patterns to build a RDF-based, SPARQL-queried knowledge-base of plan-rewrite remedies. We illustrate a distributed implementation of dGALO on Apache Spark with efficient partitioning strategies for load balancing. The system employs additional pruning strategies via clustering, which yields a fine-grained trade off between runtime and accuracy. dGALO uses its knowledge-base to re-optimize queries, often to dramatic effect, and is a valuable tool for the development team to refine the optimizer with new techniques. We demonstrate by an experimental study over the TPC-DS benchmark the efficiency and effectiveness of our techniques.

There is a growing need to find meaningful teams in expert networks such as DBLP and GitHub. However, existing team formation methods, such as those based on shortest paths between experts, may generate weakly-connected teams. We demonstrate RW-Team, a robust team formation framework based on a random walk with restart (RWR). We introduce a greedy algorithm to reduce the search space, and we use a Monte Carlo approximation of RWR to improve performance. To handle large graphs, we implement RW-Team in Apache Spark. The proposed demonstration will allow participants to form teams of researchers having various skill sets and explore connections among team members using several graph visualization techniques.

We present PyTFL, a library written in Python for the team formation task. In team formation task, the main objective is to form a team of experts given a set of skills. We demonstrate an efficient and well-structured open-source toolkit that can easily be imported into Python. Our toolkit incorporates state-of-the-art approaches for team formation, e.g., neural-based team formation, and supports team formation sub-tasks such as collaboration graph preparation, model training and validation, systematic evaluation based on qualitative and quantitative team metrics, and efficient team formation and prediction. While there are strong research papers on the team formation problem, PyTFL is the first toolkit to be publicly released for this purpose.

Order dependencies (ODs) capture relationships between ordered domains of attributes. Approximate ODs (AODs) capture such relationships even when there exist exceptions in the data. During automated discovery of ODs, validation is the process of verifying whether an OD holds. We present an algorithm for validating approximate ODs with significantly improved runtime performance over existing methods for AODs, and prove that it is correct and has optimal runtime. By replacing the validation step in a leading algorithm for approximate OD discovery with ours, we achieve orders-of-magnitude improvements in performance.

Real graphs contain edge and node weights, representing penalty, distance or cost. We study the problem of keyword search in weighted node-labeled graphs, in which a query consists of a set of keywords and an answer is a subgraph. We consider three ranking strategies for answer subgraphs: edge weights, node weights, and a bi-objective combination of both node and edge weights. We propose and experimentally evaluate algorithms that optimize these objectives with an approximation ratio of two.

Variational Autoencoders (VAEs) have shown to be effective for recommender systems with implicit feedback (e.g., browsing history, purchasing patterns, etc.). However, a little attention is given to ensembles of VAEs, that can learn user and item representations jointly. We introduce Joint Variational Autoencoder (JoVA), an ensemble of two VAEs, which jointly learns both user and item representations to predict user preferences. This design allows JoVA to capture user-user and item-item correlations simultaneously. We also introduce JoVA-Hinge, a JoVA's extension with a hinge-based pairwise loss function, to further specialize it in recommendation with implicit feedback. Our extensive experiments on four real-world datasets demonstrate that JoVA-Hinge outperforms a broad set of state-of-the-art methods under a variety of commonly-used metrics. Our empirical results also illustrate the effectiveness of JoVA-Hinge for handling users with limited training data.

Given a set of required skills, the objective of the team formation problem is to form a team of experts that cover the required skills. Most existing approaches are based on graph methods, such as minimum-cost spanning trees. These approaches, due to their limited view of the network, fail to capture complex interactions among experts and are computationally intractable. More recent approaches adopt neural architectures to learn a mapping between the skills and experts space. While they are more effective, these techniques face two main limitations: (1) they consider a fixed representation for both skills and experts, and (2) they overlook the significant amount of past collaboration network information. We learn dense representations for skills and experts based on previous collaborations and bootstrap the training process through transfer learning. We also propose to fine-tune the representation of skills and experts while learning the mapping function. Our experiments over the DBLP dataset verify that our proposed architecture is able to outperform the state-of-the-art graph and neural methods over both ranking and quality metrics.

We focus on the composition of teams of experts that collectively cover a set of required skills based on their historical collaboration network and expertise. Prior works are primarily based on the shortest path between experts on the expert collaboration network, and suffer from three major shortcomings: (1) they are computationally expensive due to the complexity of finding paths on large network structures; (2) they use a small portion of the entire historical collaboration network to reduce the search space; hence, may form sub-optimal teams; and, (3) they fall short in sparse networks where the majority of the experts have only participated in a few teams in the past. Instead of forming a large network of experts, we propose to learn relationships among experts and skills through a variational Bayes neural architecture wherein: i) we consider all past team compositions as training instances to predict future teams; ii) we bring scalability for large networks of experts due to the neural architecture; and, iii) we address sparsity by incorporating uncertainty on the neural network's parameters which yields a richer representation and more accurate team composition. We empirically demonstrate how our proposed model outperforms the state-of-the-art approaches in terms of effectiveness and efficiency based on a large DBLP dataset.

We introduce band ODs to model the semantics of attributes that are monotonically related with small variations without there being an intrinsic violation of semantics. To make band ODs relevant to real-world applications, we make them less strict to hold approximately with some exceptions. Since formulating integrity constraints manually is cumbersome, we study the problem of automatic approximate band OD discovery. We devise an algorithm that determines the optimal solution in polynomial time. We perform a thorough experimental evaluation of our techniques over real-world and synthetic datasets.

Query performance problem determination is usually performed manually in consultation with experts through the analysis of query plans. However, this is an excessively time consuming, human error-prone, and costly process. GALO is a novel system that automates this process. The tool automatically learns recurring problem patterns in query plans over workloads in an offline learning phase to build a knowledge base of plan rewrite remedies. GALO's knowledge base is built on RDF and SPARQL, which is well-suited for manipulating and querying over SQL query plans, which are graphs themselves. It then uses the knowledge base online to re-optimize queries queued for execution to improve performance, often quite dramatically.

Query optimization is a hallmark of database systems. When an SQL query runs more expensively than is viable or warranted, determination of the performance issues is usually performed manually in consultation with experts through the analysis of query's execution plan (QEP). However, this is an excessively time consuming, human error-prone, and costly process. GALO is a novel system that automates this process. The tool automatically learns recurring problem patterns in query plans over workloads in an offline learning phase, to build a knowledge base of plan-rewrite remedies. It then uses the knowledge base online to re-optimize queries often quite drastically. GALO's knowledge base is built on RDF and SPARQL, W3C graph database standards, which is well suited for manipulating and querying over SQL query plans, which are graphs themselves. GALO acts as a third-tier of re-optimization, after query rewrite and cost-based optimization, as a query plan rewrite . For generality, the context of knowledge base problem patterns, including table and column names, is abstracted with canonical symbol labels. Since the knowledge base is not tied to the context of supplied QEPs, table and column names are matched automatically during the re-optimization phase. Thus, problem patterns learned over a particular query workload can be applied in other query workloads. GALO's knowledge base is also an invaluable tool for database experts to debug query performance issues by tracking to known issues and solutions as well as refining the optimizer with new tuned techniques by the development team. We demonstrate an experimental study of the effectiveness of our techniques over synthetic TPC-DS and real IBM client query workloads.

We present the design of and a demonstration plan for FASTOD, a tool for efficiently discovering (approximate) order dependencies (ODs) from data. FASTOD converts ODs to a novel canonical form which makes it orders of magnitude faster than existing techniques. Using real datasets, we demonstrate how the discovered ODs can help users understand data semantics, identify potential data quality problems, and interactively clean the data. We also demonstrate the effectiveness of our system.

Functional Dependencies (FDs) define attribute relationships based on syntactic equality, and, when used in data cleaning, they erroneously label syntactically different but semantically equivalent values as errors. We enhance dependency-based data cleaning with Ontology Functional Dependencies (OFDs), which express semantic attribute relationships such as synonyms and is-a hierarchies defined by an ontology. Our technical contributions are twofold: 1) theoretical foundations for OFDs, including a set of sound and complete axioms and a linear-time inference procedure, and 2) an algorithm for discovering OFDs (exact ones and ones that hold with some exceptions) from data that uses the axioms to prune the exponential search space in the number of attributes. We demonstrate the efficiency of our techniques on real datasets, and we show that OFDs can significantly reduce the number of false positive errors in data cleaning techniques that rely on traditional FDs.

Integrity constraints (ICs) are useful for query optimization and for expressing and enforcing application semantics. However, formulating constraints manually requires domain expertise, is prone to human errors, and may be excessively time consuming, especially on large datasets. Hence, proposals for automatic discovery have been made for some classes of ICs, such as functional dependencies (FDs), and recently, order dependencies (ODs). ODs properly subsume FDs, as they can additionally express business rules involving order; e.g., an employee never has a higher salary while paying lower taxes than another employee. We present a new OD discovery algorithm enabled by a novel polynomial mapping to a canonical form of ODs, and a sound and complete set of axioms (inference rules) for canonical ODs. Our algorithm has exponential worst-case time complexity, O (2 | R | ), in the number of attributes | R | and linear complexity in the number of tuples. We prove that it produces a complete and minimal set of ODs. Using real and synthetic datasets, we experimentally show orders-of-magnitude performance improvements over the prior state-of-the-art.

When working with a high volume relational database, is it possible to effectively provide a compact visualization of the tuples in that database? Data visualization techniques very often scale poorly with input volume, hindering attempts at providing a responsive, full picture of the relationships within data. We introduce a method of efficiently visualizing millions of tuples in a two-dimensional constrained space, providing a method for data to be visually analyzed at the tuple level. We achieve this by applying a physics simulation on an embedded network, positioning tuples according to their representative node.

In a node-labeled graph, keyword search finds subtrees of the graph whose nodes contain all of the query keywords. This provides a way to query graph databases that neither requires mastery of a query language such as SPARQL, nor a deep knowledge of the database schema. We demonstrate eGraphSearch, a new system for effective keyword search in graph databases. Previous work ranks answer trees using combinations of structural and content-based metrics, such as path length between keywords or relevance of the labels in the answer tree to the query keywords. However, different nodes in the graph might have different importance, which affects the utility of the answer. In the proposed system, we implemented two new ways to rank keyword search results over graphs: the first one takes node importance into account while the second one is a bi-objective optimization of edge weights and node importance. In the demonstration, participants will execute keyword queries against several popular graph datasets.

query performance problem determination is often performed by analyzing query execution plans (QEPs) in addition to other performance data. As the query workloads that organizations run have become larger and more complex, analyzing QEPs manually even by experts has become a very time consuming and cumbersome task. Most performance diagnostic tools help with identifying problematic queries and most query tuning tools address a limited number of known problems and recommendations. We present the OptImatch system that offers a way to (a) look for varied user defined problem patterns in QEPs and (b) automatically get recommendations from an expert provided and user customizable knowledge base. Existing approaches do not provide the ability to perform workload analysis with flexible user defined patterns, as they lack the ability to impose a proper structure on QEPs. We introduce a novel semantic web system that allows a relatively naive user to search for arbitrary patterns and to get solution recommendations stored in a knowledge base. Our methodology includes transforming a QEP into an RDF graph and transforming a GUI based user-defined pattern into a SPARQL query through handlers. The SPARQL query is matched against the abstracted RDF graph, and any matched portion of the abstracted RDF graph is relayed back to the user. With the knowledge base, the OptImatch system automatically scans and matches interesting stored patterns in a statistical way as appropriate and returns the corresponding recommendations. Although the knowledge base patterns and solution recommendations are not in the context of the user supplied QEPs, the context is adapted automatically through the handler tagging interface. We test the performance and scalability of our framework to demonstrate its efficiency using a real query workload. We also perform a user study to quantify the benefits of the approach in terms of precision and time compared to manually searching for patterns.

Query performance problem determination is usually performed by analyzing query execution plans (QEPs). Analyzing complex QEPs is excessively time consuming and existing automatic problem determination tools do not provide ability to perform analysis with flexible user-defined problem patterns. We present the novel OptImatch system that allows a relatively naive user to search for patterns in QEPs and get recommendations from an expert and user customizable knowledge base. Our system transforms a QEP into an RDF graph. We provide a web graphical interface for the user to describe a pattern that is transformed with handlers into a SPARQL query. The SPARQL query is matched against the abstracted RDF graph and any matched parts of the graph are relayed back to the user. With the knowledge base the system automatically matches stored patterns to the QEPs by adapting dynamic context through developed tagging language and ranks recommendations using statistical correlation analysis.

Keyword search over relational databases offers an alternative way to SQL to query and explore databases that is effective for lay users who may not be well versed in SQL or the database schema. This becomes more pertinent for databases with large and complex schemas. An answer in this context is a join tree spanning tuples containing the query's keywords. As there are potentially many answers to the query, and the user is often only interested in seeing the top-k answers, how to rank the answers based on their relevance is of paramount importance. We focus on the relevance of join as the fundamental means to rank answers. We devise means to measure relevance of relations and foreign keys in the schema over the information content of the database. This can be done offline with no need for external models. We compare the proposed measures against a gold standard we derive from a real workload over TPC-E and evaluate the effectiveness of our methods. Finally, we test the performance of our measures against existing techniques to demonstrate a marked improvement, and perform a user study to establish naturalness of the ranking of the answers.

Quantitative data cleaning relies on the use of statistical methods to identify and repair data quality problems while logical data cleaning tackles the same problems using various forms of logical reasoning over declarative dependencies. Each of these approaches has its strengths: the logical approach is able to capture subtle data quality problems using sophisticated dependencies, while the quantitative approach excels at ensuring that the repaired data has desired statistical properties. We propose a novel framework within which these two approaches can be used synergistically to combine their respective strengths. We instantiate our framework using (i) metric functional dependencies, a type of dependency that generalizes functional dependencies (FDs) to identify inconsistencies in domains where only large differences in metric data are considered to be a data quality problem, and (ii) repairs that modify the inconsistent data so as to minimize statistical distortion, measured using the Earth Mover's Distance. We show that the problem of computing a statistical distortion minimal repair is NP-hard. Given this complexity, we present an efficient algorithm for finding a minimal repair that has a small statistical distortion using EMD computation over semantically related attributes. To identify semantically related attributes, we present a sound and complete axiomatization and an efficient algorithm for testing implication of metric FDs. While the complexity of inference for some other FD extensions is co-NP complete, we show that the inference problem for metric FDs remains linear, as in traditional FDs. We prove that every instance that can be generated by our repair algorithm is set-minimal (with no unnecessary changes). Our experimental evaluation demonstrates that our techniques obtain a considerably lower statistical distortion than existing repair techniques, while achieving similar levels of efficiency.

Business-intelligence queries often involve SQL functions and algebraic expressions. There can be clear semantic relationships between a column’s values and the values of a function over that column. A common property is monotonicity: as the column’s values ascend, so do the function’s values. This we call an order dependency (OD). Queries can be evaluated more efficiently when the query optimizer uses order dependencies. They can be run even faster when the optimizer can also reason over known ODs to infer new ones. Order dependencies can be declared as integrity constraints, and they can be detected automatically for many types of SQL functions and algebraic expressions. We present optimization techniques using ODs for queries that involve join, order by, group by, partition by, and distinct. Essentially, ODs can further exploit interesting orders to eliminate or simplify potentially expensive sorts in the query plan. We evaluate these techniques over our implementation in IBM R ° DB2 R ° V10 using the TPC-DS R ° benchmark schema and some IBM customer inspired queries. Our experimental results demonstrate a significant performance gain. We additionally devise an algorithm for testing logical implication for ODs which is polynomial over the size of the set of given ODs. We show that the inference algorithm which we have implemented in DB2 is sound and complete over sets of ODs over natural domains. This enables the optimizer to infer useful ODs from known ODs.

In declarative data cleaning, data semantics are encoded as constraints and errors arise when the data violates the constraints. Various forms of statistical and logical inference can be used to reason about and repair inconsistencies (errors) in data. Recently, unified approaches that repair both errors in data and errors in semantics (the constraints) have been proposed. However, both data-only approaches and unified approaches are by and large static in that they apply cleaning to a single snapshot of the data and constraints. We introduce a continuous data cleaning framework that can be applied to dynamic data and constraint environments. Our approach permits both the data and its semantics to evolve and suggests repairs based on the accumulated evidence to date. Importantly, our approach uses not only the data and constraints as evidence, but also considers the past repairs chosen and applied by a user (user repair preferences). We introduce a repair classifier that predicts the type of repair needed to resolve an inconsistency, and that learns from past user repair preferences to recommend more accurate repairs in the future. Our evaluation shows that our techniques achieve high prediction accuracy and generate high quality repairs. Of independent interest, our work makes use of a set of data statistics that are shown to be sensitive to predicting particular repair types.

Keyword search in relational databases was introduced in the last decade to assist users who are not familiar with a query language, the schema of the database, or the content of the data. An answer is a join tree of tuples that contains the query keywords. When searching a database with a complex schema, there are potentially many answers to the query. Therefore, ranking answers based on their relevance is crucial in this context. Prior work has addressed relevance based on the size of the answer or the IR scores of the tuples. However, this is not sufficient when searching a complex schema. We demonstrate MeanKS, a new system for meaningful keyword search over relational databases. The system first captures the user's interest by determining the roles of the keywords. Then, it uses schema-based ranking to rank join trees that cover the keyword roles. This uses the relevance of relations and foreign-key relationships in the schema over the information content of the database. In the demonstration, attendees can execute queries against the TPC-E warehouse and compare the proposed measures against a gold standard derived from a real workload over TPC-E to test the effectiveness of our methods.

Dependencies play an important role in databases. We study order dependencies (ODs)--and unidirectional order dependencies (UODs), a proper sub-class of ODs--which describe the relationships among lexicographical orderings of sets of tuples. We consider lexicographical ordering, as by the order-by operator in SQL, because this is the notion of order used in SQL and within query optimization. Our main goal is to investigate the inference problem for ODs, both in theory and in practice. We show the usefulness of ODs in query optimization. We establish the following theoretical results: (i) a hierarchy of order dependency classes; (ii) a proof of co-NP-completeness of the inference problem for the subclass of UODs (and ODs); (iii) a proof of co-NP-completeness of the inference problem of functional dependencies (FDs) from ODs in general, but demonstrate linear time complexity for the inference of FDs from UODs; (iv) a sound and complete elimination procedure for inference over ODs; and (v) a sound and complete polynomial inference algorithm for sets of UODs over restricted domains.

Dependencies have played a significant role in database design for many years. They have also been shown to be useful in query optimization. In this paper, we discuss dependencies between lexicographically ordered sets of tuples. We introduce formally the concept of order dependency and present a set of axioms (inference rules) for them. We show how query rewrites based on these axioms can be used for query optimization. We present several interesting theorems that can be derived using the inference rules. We prove that functional dependencies are subsumed by order dependencies and that our set of axioms for order dependencies is sound and complete.

Data warehouses are repositories of electronically stored data which are designed to support reporting and analysis. The analysis of historical data often involves aggregation over time. Thus, time is critical in the design of a data warehouse. We describe novel techniques for storing date information and optimization of queries that reference the date dimension. We show how to embed intelligence into the date key and how to exploit monotonic dependencies. We present the value of these techniques for the improvement of performance when combined with partitioning and indexes. We evaluate these techniques on our prototype implemented in IBM® DB2® V9.7 over the current draft version of the TPC-DS benchmark.