Date of Award

Fall 2014

Degree Type


Degree Name

Doctor of Philosophy (PhD)


Computer Science

First Advisor

Sunil Prabhakar

Committee Chair

Sunil Prabhakar

Committee Member 1

Mikhail J Atallah

Committee Member 2

Walid G Aref

Committee Member 3

Dongyan Xu


Increasingly, data are subjected to environments which can result in invalid (malicious or inadvertent) modifications to the data. For example, when we host the database on a third party server, or when there is a threat of insider attack or hacker attack. Ensuring the trustworthiness of data retrieved from a database is of utmost importance to users. In this dissertation, we address the question of whether a data owner can be assured that the data retrieved from an untrusted server are trustworthy. In particular, we reduce the level of trust necessary in order to establish the trustworthiness of data. Earlier work in this domain is limited to situations where there are no updates to the database, or all updates are authorized and vetted by a central trusted entity. This is an unreasonable assumption for a truly dynamic database, as would be expected in many business applications, where multiple users can access (read or write) the data without being vetted by a central server. The legitimacy of data stored in a database is defined by the faithful execution of only valid (authorized) operations. Decades of database research has resulted in solutions that ensure the integrity and consistency of data through principles such as transactions, concurrency, ACID properties, and access control rules. These solutions have been developed under the assumption that the threats arise due to failures (computer crashes, disk failures, etc), limitations of hardware, and the need to enforce access control rules. However, the semantics of these principles assumes complete trust on the database server. Considering the lack of trust that arises due to the untrusted environments that databases are subjected to, we need mechanisms to ensure that the database operations are executed following these principles. In this dissertation, we revisit some of these principles to understand what we should expect when a transaction execution follows those principles. We propose mechanisms to verify that the principles were indeed followed by the untrusted server while executing the transactions.