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: h54d936cfd145cef0
Venue: PODS
Year: 1991
Pagerank: 5.6266148e-05
Overall Rank: 6,994 | 52.98%
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,679	The Power of Sampling in Knowledge Discovery	1994	PODS	6.4726631e-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
973	A Benchmark of NonStop SQL on the Debit Credit Transaction	1988	SIGMOD	0.00012757586
1,974	Optimal File Distribution For Partial Match Retrieval	1988	SIGMOD	9.2808092e-05
3,471	Declustering Using Error Correcting Codes	1989	PODS	7.274712e-05

Semantically Similar Papers

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