6 citations · 12 across the 7 of their papers we have counts for
7 papers
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…
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…