35 citations · 160 across the 33 of their papers we have counts for
46 papers
Optimal Convergence of Iterative Methods for Datalogo
Simon Frisk, Sungjin Im, Paraschos Koutris +4
has been introduced as an extension to Datalog that increases expressiveness, yet retains simple least fixpoint semantics and admits optimization technique…
Conjunctive Queries with Negation: Beyond Signed-Acyclicity
Simon Frisk, Paraschos Koutris
We study constant-delay enumeration for conjunctive queries with negation (). It is known that queries can be enumerated with constant…
FlowLog: Re-thinking Datalog for Fast and Extensible Static Analysis
Zhenghong Yu, Hangdong Zhao, Wanzhu Hou +1
Datalog is widely used to build static analyzers, yet existing engines often force a tradeoff between efficiency and extensibility. In practice, static analyses are not run once an…
K-Join: Combining Vertex Covers for Parallel Joins
Simon Frisk, Austen Fan, Paraschos Koutris
Significant research effort has been devoted to improving the performance of join processing in the massively parallel computation model, where the goal is to evaluate a query with…
Database Theory in Action: Yannakakis' Algorithm
Paraschos Koutris, Stijn Vansummeren, Qichen Wang +2
Yannakakis' seminal algorithm is optimal for acyclic joins, yet it has not been widely adopted due to its poor performance in practice. This paper briefly surveys recent advancemen…
FlowLog: Efficient and Extensible Datalog via Incrementality
Hangdong Zhao, Zhenghong Yu, Srinag Rao +3
Datalog-based languages are regaining popularity as a powerful abstraction for expressing recursive computations in domains such as program analysis and graph processing. However,…
One Join Order Does Not Fit All: Reducing Intermediate Results with Per-Split Query Plans
Yujun He, Hangdong Zhao, Simon Frisk +4
Minimizing intermediate results is critical for efficient multi-join query processing. Although the seminal Yannakakis algorithm offers strong guarantees for acyclic queries, cycli…
Circuits and Formulas for Datalog over Semirings
Austen Z. Fan, Paraschos Koutris, Sudeepa Roy
In this paper, we study circuits and formulas for provenance polynomials of Datalog programs. We ask the following question: given an absorptive semiring and a fact of a Datalog pr…
Debunking the Myth of Join Ordering: Toward Robust SQL Analytics
Junyi Zhao, Kai Su, Yifei Yang +3
Join order optimization is critical in achieving good query performance. Despite decades of research and practice, modern query optimizers could still generate inferior join plans…
The Free Termination Property of Queries Over Time
Conor Power, Paraschos Koutris, Joseph M Hellerstein
Building on prior work on distributed databases and the CALM Theorem, we define and study the question of free termination: in the absence of distributed coordination, what query p…
Parallel Query Processing with Heterogeneous Machines
Simon Frisk, Paraschos Koutris
We study the problem of computing a full Conjunctive Query in parallel using heterogeneous machines. Our computational model is similar to the MPC model, but each machine has i…
Output-sensitive Conjunctive Query Evaluation
Shaleen Deep, Hangdong Zhao, Austen Z. Fan +1
Join evaluation is one of the most fundamental operations performed by database systems and arguably the most well-studied problem in the Database community. A staggering number of…
Evaluating Datalog over Semirings: A Grounding-based Approach
Hangdong Zhao, Shaleen Deep, Paraschos Koutris +2
Datalog is a powerful yet elegant language that allows expressing recursive computation. Although Datalog evaluation has been extensively studied in the literature, so far, only lo…
Consistent Query Answering for Primary Keys on Rooted Tree Queries
Paraschos Koutris, Xiating Ouyang, Jef Wijsen
We study the data complexity of consistent query answering (CQA) on databases that may violate the primary key constraints. A repair is a maximal subset of the database satisfying…
Conjunctive Queries with Negation and Aggregation: A Linear Time Characterization
Hangdong Zhao, Austen Z. Fan, Xiating Ouyang +1
In this paper, we study the complexity of evaluating Conjunctive Queries with negation (\cqneg). First, we present an algorithm with linear preprocessing time and constant delay en…
Consistent Query Answering for Primary Keys on Path Queries
Paraschos Koutris, Xiating Ouyang, Jef Wijsen
We study the data complexity of consistent query answering (CQA) on databases that may violate the primary key constraints. A repair is a maximal consistent subset of the database.…
The Fine-Grained Complexity of CFL Reachability
Paraschos Koutris, Shaleen Deep
Many problems in static program analysis can be modeled as the context-free language (CFL) reachability problem on directed labeled graphs. The CFL reachability problem can be gene…
Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries
Yifei Yang, Hangdong Zhao, Xiangyao Yu +1
This paper presents predicate transfer, a novel method that optimizes join performance by pre-filtering tables to reduce the join input sizes. Predicate transfer generalizes Bloom…
The Fine-Grained Complexity of Boolean Conjunctive Queries and Sum-Product Problems
Austen Z. Fan, Paraschos Koutris, Hangdong Zhao
We study the fine-grained complexity of evaluating Boolean Conjunctive Queries and their generalization to sum-of-product problems over an arbitrary semiring. For these problems, w…
Space-Time Tradeoffs for Conjunctive Queries with Access Patterns
Hangdong Zhao, Shaleen Deep, Paraschos Koutris
In this paper, we investigate space-time tradeoffs for answering conjunctive queries with access patterns (CQAPs). The goal is to create a space-efficient data structure in an init…
Naive Bayes Classifiers over Missing Data: Decision and Poisoning
Song Bian, Xiating Ouyang, Zhiwei Fan +1
We study the certifiable robustness of ML classifiers on dirty datasets that could contain missing values. A test point is certifiably robust for an ML classifier if the classifier…
LinCQA: Faster Consistent Query Answering with Linear Time Guarantees
Zhiwei Fan, Paraschos Koutris, Xiating Ouyang +1
Most data analytical pipelines often encounter the problem of querying inconsistent data that violate pre-determined integrity constraints. Data cleaning is an extensively studied…
Ranked Enumeration of Join Queries with Projections
Shaleen Deep, Xiao Hu, Paraschos Koutris
Join query evaluation with ordering is a fundamental data processing task in relational database management systems. SQL and custom graph query languages such as Cypher offer this…
Certifiable Robustness for Nearest Neighbor Classifiers
Austen Z. Fan, Paraschos Koutris
ML models are typically trained using large datasets of high quality. However, training datasets often contain inconsistent or incomplete data. To tackle this issue, one solution i…