Evaluation Of The Size Of A Query Expressed In Relational Algebra

Summary: Probabilistic model to estimate sizes of relational algebra results. Assumes independence among union-compatible domains and among tuples; derives query cardinalities from expected sizes of projections for select, project, union, intersection, theta-join. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2216
Venue: SIGMOD
Year: 1981
Pagerank: 6.5160873e-05
Overall Rank: 4,770 | 67.28%
DOI: 10.1145/582318.582343

Incoming Non-self Citations Over Time

Authors

1. Philippe Richard (INRIA)

BibTeX Citation

@inproceedings{richard_sigmod81,
        title = {{EVALUATION OF THE SIZE OF A QUERY EXPRESSED IN RELATIONAL ALGEBRA}},
        author = {Richard, Philippe},
        series = {{SIGMOD} '81},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/582318.582343},
        url = {https://dl.acm.org/doi/10.1145/582318.582343},
        year = {1981}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,894	The Size of Projections of Relations Satisfying a Functional Dependency	1982	VLDB	7.9838534e-05
13,136	Evaluating the Size of Queries on Relational Databases with non Uniform Distribution and Stochastic Dependence	1989	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
386	Distributed Query Processing In A Relational Data Base System	1978	SIGMOD	0.00019451022
1,510	A Methodology For Interpreting Tree Queries Into Optimal Semi-Join Expressions	1980	SIGMOD	0.00010539169

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	14,482	EFFICIENT PROCESSING OF RELATIONAL CALCULUS EXPRESSIONS USING RANGE QUERY THEORY (Extended Abstract)	1984	SIGMOD
2	1,172	An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment	1993	SIGMOD
3	55	Statistical Estimators for Relational Algebra Expressions	1988	PODS
4	2,984	Multiple Join Size Estimation by Virtual Domains (extended abstract)	1993	PODS
5	76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD
6	89	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD
7	992	Query Size Estimation by Adaptive Sampling (Extended Abstract)	1990	PODS
8	280	Selectivity Estimation using Probabilistic Models	2001	SIGMOD
9	1,467	The Complexity of Evaluating Relational Queries	1983	PODS
10	13,136	Evaluating the Size of Queries on Relational Databases with non Uniform Distribution and Stochastic Dependence	1989	SIGMOD