Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Efficient, Locally-Enforceable Querier Privacy for Distributed Database Systems

Farnan, Nicholas L (2015) Efficient, Locally-Enforceable Querier Privacy for Distributed Database Systems. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

Primary Text

Download (1MB)


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.


Social Networking:
Share |


Item Type: University of Pittsburgh ETD
Status: Unpublished
CreatorsEmailPitt UsernameORCID
Farnan, Nicholas Lnlf4@pitt.eduNLF4
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairLee, Adam Jadamlee@cs.pitt.eduADAMLEE
Committee MemberChrysanthis, Panos Kpanos@cs.pitt.eduPANOS
Committee MemberMossé, Danielmosse@cs.pitt.eduMOSSE
Committee MemberYu,
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


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item