Querying Shared Data with Security Heterogeneity

Yang Cao, Wenfei Fan, Yanghao Wang, Ke Yi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

There has been increasing need for secure data sharing. In practice a group of data owners often adopt a heterogeneous security scheme under which each pair of parties decide their own protocol to share data with diverse levels of trust. The scheme also keeps track of how the data is used.

This paper studies distributed SQL query answering in the heterogeneous security setting. We define query plans by incorporating toll functions determined by data sharing agreements and reflected in the use of various security facilities. We formalize query answering as a bi-criteria optimization problem, to minimize both data sharing toll and parallel query evaluation cost. We show that this problem is PSPACE-hard for SQL and Σp3-hard for SPC, and it is in NEXPTIME. Despite the hardness, we develop a set of approximate algorithms to generate distributed query plans that minimize data sharing toll and reduce parallel evaluation cost. Using real-life and synthetic data, we empirically verify the effectiveness, scalability and efficiency of our algorithms.
Original languageEnglish
Title of host publicationProceedings of the International Conference on Management of Data 2020 (SIGMOD '20)
PublisherAssociation for Computing Machinery (ACM)
Number of pages11
ISBN (Print)978-1-4503-6735-6
Publication statusPublished - 11 Jun 2020
Event2020 ACM SIGMOD/PODS International Conference on Management of Data - Portland, United States
Duration: 14 Jun 202019 Jun 2020


Conference2020 ACM SIGMOD/PODS International Conference on Management of Data
Abbreviated titleSIGMOD/PODS 2020
Country/TerritoryUnited States
Internet address


Dive into the research topics of 'Querying Shared Data with Security Heterogeneity'. Together they form a unique fingerprint.

Cite this