FastQRE
Autor: | Laks V. S. Lakshmanan, Dmitri V. Kalashnikov, Divesh Srivastava |
---|---|
Rok vydání: | 2018 |
Předmět: |
Reverse engineering
SQL Theoretical computer science Computer science InformationSystems_DATABASEMANAGEMENT 02 engineering and technology Space (commercial competition) computer.software_genre Orders of magnitude (volume) Task (computing) Simple (abstract algebra) 020204 information systems 0202 electrical engineering electronic engineering information engineering Table (database) 020201 artificial intelligence & image processing State (computer science) computer computer.programming_language |
Zdroj: | SIGMOD Conference |
DOI: | 10.1145/3183713.3183727 |
Popis: | We study the problem of Query Reverse Engineering (QRE), where given a database and an output table, the task is to find a simple project-join SQL query that generates that table when applied on the database. This problem is known for its efficiency challenge due to mainly two reasons. First, the problem has a very large search space and its various variants are known to be NP-hard. Second, executing even a single candidate SQL query can be very computationally expensive. In this work we propose a novel approach for solving the QRE problem efficiently. Our solution outperforms the existing state of the art by 2-3 orders of magnitude for complex queries, resolving those queries in seconds rather than days, thus making our approach more practical in real-life settings. |
Databáze: | OpenAIRE |
Externí odkaz: |