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,250 | The Power of Sampling in Knowledge Discovery | 1994 | PODS | 6.3162039e-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 |
|---|---|---|---|---|
| 629 | A Benchmark of NonStop SQL on the Debit Credit Transaction | 1988 | SIGMOD | 0.00018951974 |
| 1,718 | Optimal File Distribution For Partial Match Retrieval | 1988 | SIGMOD | 0.00010766698 |
| 3,094 | Declustering Using Error Correcting Codes | 1989 | PODS | 7.5788007e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,173 | The Power of Methods With Parallel Semantics | 1991 | VLDB | 4.5640563e-05 |
| 12,966 | Partition Semantics For Incomplete Information In Relational Databases | 1988 | SIGMOD | 4.1905499e-05 |
| 92 | Practical Selectivity Estimation through Adaptive Sampling | 1990 | SIGMOD | 0.00051431888 |
| 46 | Simple Random Sampling from Relational Databases | 1986 | VLDB | 0.00071588702 |
| 373 | Selectivity Estimation using Probabilistic Models | 2001 | SIGMOD | 0.00025354685 |
| 12,951 | Evaluating the Size of Queries on Relational Databases with non Uniform Distribution and Stochastic Dependence | 1989 | SIGMOD | 4.1905499e-05 |
| 912 | The Complexity of Evaluating Relational Queries | 1983 | PODS | 0.00015374685 |
| 572 | The Complexity of Query Reliability | 1998 | PODS | 0.00019888988 |
| 3,929 | Maximally Joining Probabilistic Data | 2007 | PODS | 6.620459e-05 |
| 2,246 | The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints | 2015 | PODS | 9.2039096e-05 |