Farnan, Nicholas L
(2015)
Efficient, Locally-Enforceable Querier Privacy for Distributed Database Systems.
Doctoral Dissertation, University of Pittsburgh.
(Unpublished)
Abstract
Traditionally, the declarative nature of SQL is viewed as a major strength. It allows database users to simply describe what they want to retrieve without worrying about how the answer to their question is actually computed. However, in a decentralized setting, two different approaches to evaluating the same query may reveal vastly different information about the query being asked (and, hence, about the user) to participating servers. In the case that a user's query contains sensitive or private information, this is clearly problematic.
In this dissertation, we address the problem of protecting query issuer privacy. We hypothesize that by extending SQL to allow for declarative specification of constraints on the attributes of query evaluation plans and accounting for such constraints during query optimization, users can produce efficient query evaluation plans that protect the private intensional regions of their queries without explicit server-side support. Towards supporting this hypothesis, we formalize a notion of intensional query privacy that we call (I, A)-privacy, and present PASQL, a set of extensions to SQL that allows users to specify (I, A)-privacy constraints to a query optimizer. We explore tradeoffs between the expressiveness of several PASQL variants, optimization time requirements, and the optimality of plans produced. We present two algorithms for optimizing queries with attached (I, A)-privacy constraints and formally establish their time and space complexities. We prove that one is capable of producing optimal results, though at the cost of greatly increased time and space requirements. We use the other as the basis of PAQO, our implementation of an (I, A)-privacy-aware query optimizer. We present an extensive experimental evaluation of PAQO to show that is is capable of efficiently generating plans to evaluate PASQL queries, and to confirm the results of our formal complexity analysis.
Share
| Citation/Export: |
|
| Social Networking: |
|
Details
| Item Type: |
University of Pittsburgh ETD
|
| Status: |
Unpublished |
| Creators/Authors: |
| Creators | Email | Pitt Username | ORCID  |
|---|
| Farnan, Nicholas L | nlf4@pitt.edu | NLF4 | |
|
| ETD Committee: |
|
| Date: |
13 January 2015 |
| Date Type: |
Publication |
| Defense Date: |
21 November 2014 |
| Approval Date: |
13 January 2015 |
| Submission Date: |
18 November 2014 |
| Access Restriction: |
No restriction; Release the ETD for access worldwide immediately. |
| Number of Pages: |
130 |
| Institution: |
University of Pittsburgh |
| Schools and Programs: |
Dietrich School of Arts and Sciences > Computer Science |
| Degree: |
PhD - Doctor of Philosophy |
| Thesis Type: |
Doctoral Dissertation |
| Refereed: |
Yes |
| Uncontrolled Keywords: |
Preference-aware Query Optimization, Private Query Processing |
| Date Deposited: |
13 Jan 2015 15:28 |
| Last Modified: |
15 Nov 2016 14:25 |
| URI: |
http://d-scholarship.pitt.edu/id/eprint/23532 |
Metrics
Monthly Views for the past 3 years
Plum Analytics
Actions (login required)
 |
View Item |
![[img]](https://d-scholarship.pitt.edu/style/images/fileicons/application_pdf.png)
![[feed]](/images/feed-icon-32x32.png){kind=icon}