Publications (21)
Comprehensive and Efficient Workload Compression
Shaleen Deep, Anja Gruenheid, Paraschos Koutris +2
This work studies the problem of constructing a representative workload from a given input analytical query workload where the former serves as an approximation with guarantees of…
Rapidash: Efficient Constraint Discovery via Rapid Verification
Zifan Liu, Shaleen Deep, Anna Fariha +3
Denial Constraint (DC) is a well-established formalism that captures a wide range of integrity constraints commonly encountered, including candidate keys, functional dependencies,…
General Space-Time Tradeoffs via Relational Queries
Shaleen Deep, Xiao Hu, Paraschos Koutris
In this paper, we investigate space-time tradeoffs for answering Boolean conjunctive queries. The goal is to create a data structure in an initial preprocessing phase and use it fo…
Tracing Agentic Failure from the Flow of Success
Samuel Yeh, Yiwen Zhu, Shaleen Deep +1
The paper introduces OAT, a lightweight unsupervised method that learns from successful LLM agent trajectories and detects error steps in failed runs by scoring deviations using ne…
From Words to Code: Harnessing Data for Program Synthesis from Natural Language
Anirudh Khatry, Joyce Cahoon, Jordan Henkel +9
Creating programs to correctly manipulate data is a difficult task, as the underlying programming languages and APIs can be challenging to learn for many users who are not skilled…
Compressed Representations of Conjunctive Query Results
Shaleen Deep, Paraschos Koutris
Relational queries, and in particular join queries, often generate large output results when executed over a huge dataset. In such cases, it is often infeasible to store the whole…
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…
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…
ReAcTable: Enhancing ReAct for Table Question Answering
Yunjia Zhang, Jordan Henkel, Avrilia Floratou +3
Table Question Answering (TQA) presents a substantial challenge at the intersection of natural language processing and data analytics. This task involves answering natural language…
Holistic Cube Analysis: A Query Framework for Data Insights
Xi Wu, Shaleen Deep, Joe Benassi +11
Many data insight questions can be viewed as searching in a large space of tables and finding important ones, where the notion of importance is defined in some adhoc user defined m…
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…
Fast Join Project Query Evaluation using Matrix Multiplication
Shaleen Deep, Xiao Hu, Paraschos Koutris
In the last few years, much effort has been devoted to developing join algorithms in order to achieve worst-case optimality for join queries over relational databases. Towards this…
An Evaluation of N-Gram Selection Strategies for Regular Expression Indexing in Contemporary Text Analysis Tasks. Extended Version
Ling Zhang, Shaleen Deep, Jignesh M. Patel +1
Efficient evaluation of regular expressions (regex, for short) is crucial for text analysis, and n-gram indexes are fundamental to achieving fast regex evaluation performance. Howe…
Revenue Maximization for Query Pricing
Shuchi Chawla, Shaleen Deep, Paraschos Koutris +1
Buying and selling of data online has increased substantially over the last few years. Several frameworks have already been proposed that study query pricing in theory and practice…
Nexus: Inferring Join Graphs from Metadata Alone via Iterative Low-Rank Matrix Completion
Tianji Cong, Yuanyuan Tian, Andreas Mueller +5
Automatically inferring join relationships is a critical task for effective data discovery, integration, querying and reuse. However, accurately and efficiently identifying these r…
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…
Enumeration Algorithms for Conjunctive Queries with Projection
Shaleen Deep, Xiao Hu, Paraschos Koutris
We investigate the enumeration of query results for an important subset of CQs with projections, namely star and path queries. The task is to design data structures and algorithms…
Ranked Enumeration of Conjunctive Query Results
Shaleen Deep, Paraschos Koutris
We study the problem of enumerating answers of Conjunctive Queries ranked according to a given ranking function. Our main contribution is a novel algorithm with small preprocessing…
The Design of Arbitrage-Free Data Pricing Schemes
Shaleen Deep, Paraschos Koutris
Motivated by a growing market that involves buying and selling data over the web, we study pricing schemes that assign value to queries issued over a database. Previous work studie…
Regular Expression Indexing for Log Analysis. Extended Version
Ling Zhang, Shaleen Deep, Jignesh M. Patel +1
In this paper, we present the design and architecture of REI, a novel system for indexing log data for regular expression queries. Our main contribution is an -gram-based indexi…
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…