research
∙
06/25/2023
From Shapley Value to Model Counting and Back
In this paper we investigate the problem of quantifying the contribution...
share
research
∙
06/24/2023
Join Size Bounds using Lp-Norms on Degree Sequences
Estimating the output size of a join query is a fundamental yet longstan...
research
∙
06/16/2023
CHORUS: Foundation Models for Unified Data Discovery and Exploration
We explore the application of foundation models to data discovery and ex...
research
∙
04/24/2023
Applications of Information Inequalities to Database Theory Problems
The paper describes several applications of information inequalities to ...
research
∙
01/25/2023
Free Join: Unifying Worst-Case Optimal and Traditional Joins
Over the last decade, worst-case optimal join (WCOJ) algorithms have eme...
research
∙
11/21/2022
Quasi-stable Coloring for Graph Compression: Approximating Max-Flow, Linear Programs, and Centrality
We propose quasi-stable coloring, an approximate version of stable color...
research
∙
11/17/2022
SafeBound: A Practical System for Generating Cardinality Bounds
Recent work has reemphasized the importance of cardinality estimates for...
research
∙
10/31/2022
Computing Rule-Based Explanations by Leveraging Counterfactuals
Sophisticated machine models are increasingly used for high-stakes decis...
research
∙
10/12/2022
Optimizing Tensor Programs on Flexible Storage
Tensor programs often need to process large tensors (vectors, matrices, ...
research
∙
02/21/2022
Optimizing Recursive Queries with Program Synthesis
Most work on query optimization has concentrated on loop-free queries. H...
research
∙
01/11/2022
Degree Sequence Bound For Join Cardinality Estimation
Recent work has demonstrated the catastrophic effects of poor cardinalit...
research
∙
05/30/2021
Convergence of Datalog over (Pre-) Semirings
Recursive queries have been traditionally studied in the framework of da...
research
∙
01/05/2021
GeCo: Quality Counterfactual Explanations in Real Time
Machine learning is increasingly applied in high-stakes decision making ...
research
∙
11/30/2020
A Near-Optimal Parallel Algorithm for Joining Binary Relations
We present a constant-round algorithm in the massively parallel computat...
research
∙
09/18/2020
On the Tractability of SHAP Explanations
SHAP explanations are a popular feature-attribution mechanism for explai...
research
∙
08/03/2020
A Dichotomy for the Generalized Model Counting Problem for Unions of Conjunctive Queries
We study the generalized model counting problem, defined as follows: giv...
research
∙
04/19/2020
Decision Problems in Information Theory
Constraints on entropies are considered to be the laws of information th...
research
∙
04/07/2020
Causal Relational Learning
Causal inference is at the heart of empirical research in natural and so...
research
∙
03/15/2020
Causality-based Explanation of Classification Outcomes
We propose a simple definition of an explanation for the outcome of a cl...
research
∙
02/23/2020
Sample Debiasing in the Themis Open World Database System (Extended Version)
Open world database management systems assume tuples not in the database...
research
∙
02/19/2020
SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra
Machine learning algorithms are commonly specified in linear algebra (LA...
research
∙
12/17/2019
Mosaic: A Sample-Based Database System for Open World Query Processing
Data scientists have relied on samples to analyze populations of interes...
research
∙
11/29/2019
Mining Approximate Acyclic Schemes from Relations
Acyclic schemes have numerous applications in databases and in machine l...
research
∙
11/09/2019
EntropyDB: A Probabilistic Approach to Approximate Query Processing
We present EntropyDB, an interactive data exploration system that uses a...
research
∙
08/20/2019
Data Management for Causal Algorithmic Fairness
Fairness is increasingly recognized as a critical component of machine l...
research
∙
06/24/2019
Bag Query Containment and Information Theory
The query containment problem is a fundamental algorithmic problem in da...
research
∙
02/21/2019
Capuchin: Causal Database Repair for Algorithmic Fairness
Fairness is increasingly recognized as a critical component of machine l...
research
∙
12/24/2018
Integrity Constraints Revisited: From Exact to Approximate Implication
Integrity constraints such as functional dependences (FD), and multi-val...
research
∙
10/03/2018
Improving High Contention OLTP Performance via Transaction Scheduling
Research in transaction processing has made significant progress in impr...
research
∙
04/02/2018
A Note on the Hardness of the Critical Tuple Problem
The notion of critical tuple was introduced by Miklau and Suciu (Gerome ...
research
∙
03/12/2018
Bias in OLAP Queries: Detection, Explanation, and Removal
On line analytical processing (OLAP) is an essential element of decision...
research
∙
03/12/2018
HypDB: Detect, Explain And Resolve Bias in OLAP
On line analytical processing (OLAP) is an essential element of decision...
research
∙
02/06/2018
Axiomatic Foundations and Algorithms for Deciding Semantic Equivalences of SQL Queries
Deciding the equivalence of SQL queries is a fundamental problem in data...
research
∙
12/20/2017
Boolean Tensor Decomposition for Conjunctive Queries with Negation
We propose an algorithm for answering conjunctive queries with negation,...
research
∙
09/12/2016
ZaliQL: A SQL-Based Framework for Drawing Causal Inference from Big Data
Causal inference from observational data is a subject of active research...
research
∙
12/03/2014
Symmetric Weighted First-Order Model Counting
The FO Model Counting problem (FOMC) is the following: given a sentence ...
research
∙
12/02/2014
Approximate Lifted Inference with Probabilistic Databases
This paper proposes a new approach for approximate evaluation of #P-hard...
research
∙
09/21/2014
Oblivious Bounds on the Probability of Boolean Functions
This paper develops upper and lower bounds for the probability of Boolea...
research
∙
05/13/2014
Understanding the Complexity of Lifted Inference and Asymmetric Weighted Model Counting
In this paper we study lifted inference for the Weighted First-Order Mod...
research
∙
09/26/2013
Lower Bounds for Exact Model Counting and Applications in Probabilistic Databases
The best current methods for exactly computing the number of satisfying ...
research
∙
05/13/2011
Optimal Upper and Lower Bounds for Boolean Expressions by Dissociation
This paper develops upper and lower bounds for the probability of Boolea...
research
∙
12/15/2010
Data Conflict Resolution Using Trust Mappings
In massively collaborative projects such as scientific or community data...
research
∙
09/10/2010
The Complexity of Causality and Responsibility for Query Answers and non-Answers
An answer to a query has a well-defined lineage expression (alternativel...
research
∙
12/30/2009
Believe It or Not: Adding Belief Annotations to Databases
We propose a database model that allows users to annotate data with beli...
research
∙
12/29/2009