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)

Paper ID: 942
Venue: PODS
Year: 1991
Pagerank: 5.7554494e-05
Overall Rank: 6,847 | 53.03%
DOI: 10.1145/113413.113437

Incoming Non-self Citations Over Time

Authors

1. Shaibal Roy (Stanford University)

BibTeX Citation

@inproceedings{roy_pods91,
        address = {New York, NY, USA},
        series = {{PODS} '91},
        title = {{Semantic Complexity of Classes of Relational Queries and Query Independent Data Partitioning}},
        url = {https://dl.acm.org/doi/10.1145/113413.113437},
        doi = {10.1145/113413.113437},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Roy, Shaibal},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,584	The Power of Sampling in Knowledge Discovery	1994	PODS	6.6181342e-05

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
951	A Benchmark of NonStop SQL on the Debit Credit Transaction	1988	SIGMOD	0.00013021781
1,918	Optimal File Distribution For Partial Match Retrieval	1988	SIGMOD	9.4857996e-05
3,403	Declustering Using Error Correcting Codes	1989	PODS	7.4414918e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,151	Partition Semantics For Incomplete Information In Relational Databases	1988	SIGMOD
2	10,169	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS
3	76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
4	173	Simple Random Sampling from Relational Databases	1986	VLDB
5	280	Selectivity Estimation using Probabilistic Models	2001	SIGMOD
6	13,136	Evaluating the Size of Queries on Relational Databases with non Uniform Distribution and Stochastic Dependence	1989	SIGMOD
7	644	The Complexity of Query Reliability	1998	PODS
8	1,467	The Complexity of Evaluating Relational Queries	1983	PODS
9	4,187	Maximally Joining Probabilistic Data	2007	PODS
10	1,707	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS