Edinburgh Research Explorer

Making SQL Queries Correct on Incomplete Databases: A Feasibility Study

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

Related Edinburgh Organisations

Open Access permissions



Original languageEnglish
Title of host publicationPODS '16 Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Place of PublicationSan Francisco, USA
Number of pages13
ISBN (Print)978-1-4503-4191-2
Publication statusPublished - 15 Jun 2016
Event35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems - San Francisco, United States
Duration: 26 Jun 20161 Jul 2016


Conference35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Abbreviated titleSIGMOD PODS 2016
CountryUnited States
CitySan Francisco
Internet address


Multiple issues with SQL’s handling of nulls have been well documented. Having efficiency as its key goal, evaluation of SQL queries disregards the standard notion of correctness on incomplete databases – certain answers – due to its high complexity. As a result, it may produce answers that are just plain wrong. It was recently shown that SQL evaluation can be modified, at least for first-order queries, to return only correct answers. But while these modifications came with good theoretical complexity bounds, they have not been tested in practice. The goals of this proof-of-concept paper are to understand whether wrong answers can be produced by SQL queries in real-world scenarios, and whether proposed techniques for avoiding them can be made practically feasible. We use the TPC-H benchmark, and show that for some typical queries involving negation, wrong answers are very common. On the other hand, existing solutions for fixing the problem do not work in practice at all. By analyzing the reasons for this, we come up with a new modified way of rewriting SQL queries that restores correctness. We conduct experiments which show the feasibility of our solution: the small price tag it imposes can be often tolerated to ensure correct results, and we do not miss correct answers that the usual SQL evaluation produces. The overall conclusion is that correct evaluation can be realistically achieved in the presence of nulls, at least for the SQL fragment that corresponds to first-order queries.


35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems


San Francisco, United States

Event: Conference

Download statistics

No data available

ID: 25440349