Semantic Complexity of Classes of Relational Queries and Query Independent Data Partitioning
Summary: Defines a VC-style semantic complexity for classes of selection queries to lift uniform-convergence bounds from single queries to whole classes, enabling one-sample selectivity estimation and small representative samples. Shows finite-complexity classes admit query-independent horizontal partitions that evenly balance workload; common hash families satisfy the combinatorial constraint. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Shaibal Roy
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,253 | The Power of Sampling in Knowledge Discovery | 1994 | PODS | 6.323083e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 3 of 3 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 628 | A Benchmark of NonStop SQL on the Debit Credit Transaction | 1988 | SIGMOD | 0.00018947564 |
| 1,701 | Optimal File Distribution For Partial Match Retrieval | 1988 | SIGMOD | 0.00010856554 |
| 3,043 | Declustering Using Error Correcting Codes | 1989 | PODS | 7.6679843e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,172 | The Power of Methods With Parallel Semantics | 1991 | VLDB | 4.5684406e-05 |
| 12,956 | Partition Semantics For Incomplete Information In Relational Databases | 1988 | SIGMOD | 4.1945683e-05 |
| 92 | Practical Selectivity Estimation through Adaptive Sampling | 1990 | SIGMOD | 0.00051315959 |
| 46 | Simple Random Sampling from Relational Databases | 1986 | VLDB | 0.00070894702 |
| 372 | Selectivity Estimation using Probabilistic Models | 2001 | SIGMOD | 0.00025354779 |
| 12,941 | Evaluating the Size of Queries on Relational Databases with non Uniform Distribution and Stochastic Dependence | 1989 | SIGMOD | 4.1945683e-05 |
| 915 | The Complexity of Evaluating Relational Queries | 1983 | PODS | 0.0001538509 |
| 571 | The Complexity of Query Reliability | 1998 | PODS | 0.00019910719 |
| 3,929 | Maximally Joining Probabilistic Data | 2007 | PODS | 6.6248763e-05 |
| 2,243 | The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints | 2015 | PODS | 9.2166927e-05 |