<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T06:33:37Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/3702" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/3702</identifier><datestamp>2017-03-21T21:25:06Z</datestamp><setSpec>com_10012_9924</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9930</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="7033948d-08f6-42a8-a791-91ff05bab93e" confidence="600">Zhang, Huaxin</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2008-05-20T19:27:05Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2008-05-20T19:27:05Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2008-05-20T19:27:05Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2008</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/3702</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Access controls are mechanisms to enhance security by protecting&#xd;
data from unauthorized accesses. In contrast to traditional access&#xd;
controls that grant access rights at the granularity of the whole&#xd;
tables or views, fine-grained access controls specify access&#xd;
controls at finer granularity, e.g., individual nodes in XML&#xd;
databases and individual tuples in relational databases.&#xd;
&#xd;
While there is a voluminous literature on specifying and modeling&#xd;
fine-grained access controls, less work has been done to address&#xd;
the performance issues of database systems with fine-grained&#xd;
access controls. This thesis addresses the performance issues of&#xd;
fine-grained access controls and proposes corresponding solutions.&#xd;
In particular, the following issues are addressed: effective&#xd;
storage of massive access controls, efficient query planning for&#xd;
secure query evaluation, and accurate cardinality estimation for&#xd;
access controlled data.&#xd;
&#xd;
Because fine-grained access controls specify access rights from&#xd;
each user to each piece of data in the system, they are&#xd;
effectively a massive matrix of the size as the product of the&#xd;
number of users and the size of data. Therefore, fine-grained&#xd;
access controls require a very compact encoding to be feasible.&#xd;
The proposed storage system in this thesis achieves an&#xd;
unprecedented level of compactness by leveraging the high&#xd;
correlation of access controls found in real system data. This&#xd;
correlation comes from two sides: the structural similarity of&#xd;
access rights between data, and the similarity of access patterns&#xd;
from different users. This encoding can be embedded into a&#xd;
linearized representation of XML data such that a query evaluation&#xd;
framework is able to compute the answer to the access controlled&#xd;
query with minimal disk I/O to the access controls.&#xd;
&#xd;
Query optimization is a crucial component for database systems.&#xd;
This thesis proposes an intelligent query plan caching mechanism&#xd;
that has lower amortized cost for query planning in the presence&#xd;
of fine-grained access controls. The rationale behind this query&#xd;
plan caching mechanism is that the queries, customized by&#xd;
different access controls from different users, may share common&#xd;
upper-level join trees in their optimal query plans. Since join&#xd;
plan generation is an expensive step in query optimization,&#xd;
reusing the upper-level join trees will reduce query optimization&#xd;
significantly. The proposed caching mechanism is able to match&#xd;
efficient query plans to access controlled query plans with&#xd;
minimal runtime cost.&#xd;
&#xd;
In case of a query plan cache miss, the optimizer needs to&#xd;
optimize an access controlled query from scratch. This depends on&#xd;
accurate cardinality estimation on the size of the intermediate&#xd;
query results. This thesis proposes a novel sampling scheme that&#xd;
has better accuracy than traditional cardinality estimation&#xd;
techniques.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">query</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">access control</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Computer Science</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">Query Evaluation in the Presence of Fine-grained Access Control</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">School of Computer Science</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>