HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Conference Papers >

Please use this identifier to cite or link to this item:
Title: Authenticated join processing in outsourced databases
Authors: Yang, Yin
Papadias, Dimitris
Papadopoulos, Stavros
Kalnis, Panos
Keywords: Database outsourcing
Join algorithms
Query authentication
Issue Date: 2009
Citation: To appear in the Proceedings of the ACM Conference on the Management of Data (SIGMOD), Providence, Rhode Island, U.S.A., June 29-July 2, 2009
Abstract: Database outsourcing requires that a query server constructs a proof of result correctness, which can be verified by the client using the data owner’s signature. Previous authentication techniques deal with range queries on a single relation using an authenticated data structure (ADS). On the other hand, authenticated join processing is inherently more complex than ranges since only the base relations (but not their combination) are signed by the owner. In this paper, we present three novel join algorithms depending on the ADS availability: (i) Authenticated Indexed Sort Merge Join (AISM), which utilizes a single ADS on the join attribute, (ii) Authenticated Index Merge Join (AIM) that requires an ADS (on the join attribute) for both relations, and (iii) Authenticated Sort Merge Join (ASM), which does not rely on any ADS. We experimentally demonstrate that the proposed methods outperform two benchmark algorithms, often by several orders of magnitude, on all performance metrics, and effectively shift the workload to the outsourcing service. Finally, we extend our techniques to complex queries that combine multi-way joins with selections and projections.
Rights: © ACM, 2009. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version will be published in Proceedings of the ACM Conference on the Management of Data (SIGMOD), Providence, Rhode Island, U.S.A., June 29-July 2, 2009.
Appears in Collections:CSE Conference Papers

Files in This Item:

File Description SizeFormat
SIGMOD09-AJ.pdf395KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.