Title: Efficient Query Reverse Engineering using Table Fragments
Authors: Meiying Li and Chee-Yong Chan
Abstract: Given an output table T that is the result of some unknown query on a databaseD, Query Reverse Engineering(QRE) computes one or more target query Q such that the result of Q on D is T. A fundamental challenge in QRE is how to efficiently compute target queries given its large search space. In this paper, we focus on the QRE problem for PJ+ queries, which is a more expressive class of queries than projectjoin queries by supporting antijoins as well as inner joins. To enhance efficiency, we propose a novel query-centric approach consisting of table partitioning, precomputation, and indexing techniques. Our experimental study demonstrates that our approach significantly outperforms the state-of-the-art solution by an average improvement factor of 120.
