Edinburgh Research Explorer

On the tractability of certain answers for SQL nulls in relational algebra with inequalities

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

Related Edinburgh Organisations

Open Access permissions

Open

Original languageEnglish
Title of host publicationProceedings of the 12th Alberto Mendelzon International Workshop on Foundations of Data Management
Place of PublicationCali, Colombia
PublisherCEUR-WS.org
Number of pages5
Volume2100
Publication statusPublished - 2018
Event12th Alberto Mendelzon International Workshop on Foundations of Data Management - Cali, Colombia
Duration: 21 May 201825 May 2018
http://www.amw2018.co/

Workshop

Workshop12th Alberto Mendelzon International Workshop on Foundations of Data Management
Abbreviated titleAMW 2018
CountryColombia
CityCali
Period21/05/1825/05/18
Internet address

Abstract

Missing values in theoretical models of incomplete database are often represented with marked nulls, while in SQL databases missing values are all denoted by the same syntactic NULL object. Even practical algorithm to approximate certain answers (answers which are true regardless of how incomplete information is interpreted) are often developed in the model with marked nulls. However computing certain answers for marked nulls is co-NP complete even for the most simple queries when inequalities are allowed. In this short paper we study the tractability of certain answers for SQL nulls in a fragment of relational algebra where selection with inequalities is permitted. We define the fragment and present an algorithm to compute certain answers. We also show that if we add even small features to the fragment, computing certain answers becomes intractable. This study emphasises the necessity of a specific certain answers approximation scheme for SQL nulls and offers ideas to design it.

Event

ID: 68385132