Article

Free access

Statistical estimators for relational algebra expressions

Authors:

Wen-Chi Hou,

Gultekin Ozsoyoglu,

Baldeo K. TanejaAuthors Info & Claims

PODS '88: Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

Pages 276 - 287

https://doi.org/10.1145/308386.308455

Published: 01 March 1988 Publication History

PDF eReader

Abstract

Present database systems process all the data related to a query before giving out responses. As a result, the size of the data to be processed becomes excessive for real-time/time-constrained environments. A new methodology is needed to cut down systematically the time to process the data involved in processing the query. To this end, we propose to use data samples and construct an approximate synthetic response to a given query.

In this paper, we consider only COUNT(E) type queries, where E is an arbitrary relational algebra expression. We make no assumptions about the distribution of attribute values and ordering of tuples in the input relations, and propose consistent and unbiased estimators for arbitrary COUNT(E) type queries. We design a sampling plan based on the cluster sampling method to improve the utilization of sampled data and to reduce the cost of sampling. We also evaluate the performance of the proposed estimators.

References

[1]

Cochmn. w o, "~g T~que,". T~rd ~d John Wdey & Sons, 1977

Google Scholar

[2]

Chnstodoulakas, S. "Estunaung Record SelecuvtJes", Informaucm Systems, Vol 8, 1983

Google Scholar

[3]

Devote, J L, "Probabthty & Staumcs for Eng, neermg and Sclences", Brook/Cole, 1984

Google Scholar

[4]

Datta, A, Fourmer, B. Hc~. W-C, and Ozsoyoglu, G, "The Implementat~n of SSDB". Proc Thml Internauonal Workshop oa Stausucal Databam Management", July 1986.

Google Scholar

[5]

Goodman, LA., "On the Esamauon of the N~ of Classes m a Populaum", Ann Math Sta., 1949

Google Scholar

[6]

Hou, W-C, Ozsoyoglu, G, and Taneja, B k., "Sta- U~cal Emmators for RelalLtonal Algebra Expres. mons", Tech Rpt. CES-87-15, CWRU, 1987

Google Scholar

[7]

Lm, C L, "Intmdu~m to Ccxnbmatonal Mathematics", McGraw-Hall, 196&

Google Scholar

[8]

Morgenstem, J P, "Compmer Based Management lnfommtton Systems Embodymg Answer Accuracy As a User Parameter", Ph D Thems, Umv of Cahfornm, Berkeley, 1981

Digital Library

Google Scholar

[9]

Olken, F, "Phymcal Database Support for Sc~enufic and Statlmcal Databases", Third Int. Scsenttfic and Statlmcal Databases Workshop, 1986

Digital Library

Google Scholar

[10]

Olken, F and Rotem, D, "Ssmple Random Samphng from Relational Databases", VLDB Conf 1986

Digital Library

Google Scholar

[11]

Ross, S M, "lntroductloa to Probabshty Models", 2nd Ed., Acndenac Press, 1980

Google Scholar

[12]

Rowe, N C, "Antlsamphn8 for Emmattom An overvsew", IEE Trans on Software Eng., Oct 1985

Digital Library

Google Scholar

[13]

Scheaffer, MendenhaH, and Ott, "Elementary Survey Samphn8", 3rd Ed, Duxbury press, 1986

Google Scholar

[14]

Sukhatme, P V, etc, "Samphng ~ry of Surveys Apphcauon", 3rd Ed, New Delhi, Indm and Iowa State Umv Press, 1984

Google Scholar

Cited By

View all

Li JLei RWang SWei ZDing B(2024)Learning-based Property Estimation with PolynomialsProceedings of the ACM on Management of Data10.1145/36549942:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654994
Stach CBehringer MBräcker JGritti CMitschang B(2022)SMARTEN—A Sample-Based Approach towards Privacy-Friendly Data RefinementJournal of Cybersecurity and Privacy10.3390/jcp20300312:3(606-628)Online publication date: 15-Aug-2022
https://doi.org/10.3390/jcp2030031
Li JWei ZDing BDai XLu LZhou JZhang ARangwala H(2022)Sampling-based Estimation of the Number of Distinct Values in Distributed EnvironmentProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3534678.3539390(893-903)Online publication date: 14-Aug-2022
https://dl.acm.org/doi/10.1145/3534678.3539390
Show More Cited By

Recommendations

Statistical estimators for aggregate relational algebra queries
Induction of relational algebra expressions
ILP'09: Proceedings of the 19th international conference on Inductive logic programming

We study the problemof inducing relational databases queries expressing quantification. Such queries express interesting multi-relational patterns in a database in a concise manner. Queries on relational databases can be expressed as Datalog programs. ...
Translating SQL Into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries

In this paper, we present a translator from a relevant subset of SQL into relational algebra. The translation is syntax-directed, with translation rules associated with grammar productions; each production corresponds to a particular type of SQL ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODS '88: Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

March 1988

352 pages

ISBN:0897912632

DOI:10.1145/308386

Chairmen:
Chris Edmondson-Yurkanan
Univ. of Texas at Austin, Austin
,
Mihalis Yannakakis
AT&T Bell Labs

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 1988

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS05

Sponsor:

SIGMOD/PODS05: International Conference on Management of Data and Symposium on Principles Database and Systems

Texas, Austin, USA

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

93
Total Citations
View Citations
699
Total Downloads

Downloads (Last 12 months)73
Downloads (Last 6 weeks)5

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Li JLei RWang SWei ZDing B(2024)Learning-based Property Estimation with PolynomialsProceedings of the ACM on Management of Data10.1145/36549942:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654994
Stach CBehringer MBräcker JGritti CMitschang B(2022)SMARTEN—A Sample-Based Approach towards Privacy-Friendly Data RefinementJournal of Cybersecurity and Privacy10.3390/jcp20300312:3(606-628)Online publication date: 15-Aug-2022
https://doi.org/10.3390/jcp2030031
Li JWei ZDing BDai XLu LZhou JZhang ARangwala H(2022)Sampling-based Estimation of the Number of Distinct Values in Distributed EnvironmentProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3534678.3539390(893-903)Online publication date: 14-Aug-2022
https://dl.acm.org/doi/10.1145/3534678.3539390
Macke SAliakbarpour MDiakonikolas IParameswaran ARubinfeld R(2021)Rapid Approximate Aggregation with Distribution-Sensitive Interval Guarantees2021 IEEE 37th International Conference on Data Engineering (ICDE)10.1109/ICDE51399.2021.00150(1703-1714)Online publication date: Apr-2021
https://doi.org/10.1109/ICDE51399.2021.00150
Chen LHuang HChen D(2021)Join cardinality estimation by combining operator-level deep neural networksInformation Sciences10.1016/j.ins.2020.09.065546(1047-1062)Online publication date: Feb-2021
https://doi.org/10.1016/j.ins.2020.09.065
Rahman SAliakbarpour MKong HBlais EKarahalios KParameswaran ARubinfield R(2017)I've seen "enough"Proceedings of the VLDB Endowment10.14778/3137628.313763710:11(1262-1273)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.14778/3137628.3137637
Kim ABlais EParameswaran AIndyk PMadden SRubinfeld R(2015)Rapid sampling for visualizations with ordering guaranteesProceedings of the VLDB Endowment10.14778/2735479.27354858:5(521-532)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.14778/2735479.2735485
Inoue TKrishna AGopalan R(2015)Multidimensional Cluster Sampling View on Large Databases for Approximate Query ProcessingProceedings of the 2015 IEEE 19th International Enterprise Distributed Object Computing Conference10.1109/EDOC.2015.24(104-111)Online publication date: 21-Sep-2015
https://dl.acm.org/doi/10.1109/EDOC.2015.24
Wu WWu XHacigümüş HNaughton J(2014)Uncertainty aware query execution time predictionProceedings of the VLDB Endowment10.14778/2733085.27330927:14(1857-1868)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.14778/2733085.2733092
Yu FHou WLuo CChe DZhu MRoss KSrivastava DPapadias D(2013)CS2Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data10.1145/2463676.2463701(469-480)Online publication date: 22-Jun-2013
https://dl.acm.org/doi/10.1145/2463676.2463701
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Recommendations

Statistical estimators for aggregate relational algebra queries

Induction of relational algebra expressions

Translating SQL Into Relational Algebra: Optimization, Semantics, and Equivalence of SQL Queries