Full Citation

Title: PSALM: Accurate Sampling for Cardinality Estimation in a Multi-user Environment

Citation Type: Miscellaneous

Publication Year: 2007

ISBN:

ISSN:

DOI:

NSFID:

PMCID:

PMID:

Abstract: In database systems that support ne-grained access controls, eachuser has access rights that determine which tuples are accessible and whichare inaccessible. Queries are answered as if the inaccessible tuples are notpresent in the database. Thus, users with dierent access rights may getdierent answers to a given query. To process queries eciently in thepresence of ne-grained access controls, the database system needs accu-rate estimates of the number of tuples that are both accessible accordingto the access rights of the submitting user and relevant according to theselection predicates in the query. In this paper we present sampling-basedcardinality estimation techniques for use in the presence of ne-grainedaccess controls. These techniques exploit the fact that access rights arerelatively static and are common to all queries that are evaluated on behalfof a particular user. We show that the proposed techniques provide moreaccurate estimates than simpler techniques that do not exploit knowledgeof access rights. We quantify these improvements analytically and throughsimulations.

User Submitted?: No

Authors: Zhang, Huaxin; Salem, Kenneth; Ilyas, Ihab F.

Publisher: University of Waterloo

Data Collections: IPUMS USA

Topics: Methodology and Data Collection

Countries: