Edinburgh Research Explorer

On Querying Incomplete Information in Databases under Bag Semantics

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

Related Edinburgh Organisations

Access status

Open

Documents

https://www.ijcai.org/proceedings/2017/0138.pdf
Original languageEnglish
Title of host publicationProceedings of the 26th International Joint Conference on Artificial Intelligence
PublisherIJCAI Inc
Pages993-999
Number of pages7
ISBN (Electronic)978-0-9992411-0-3
DOIs
StatePublished - Aug 2017
Event26th International Joint Conference on Artificial Intelligence - Melbourne, Australia

Conference

Conference26th International Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI 2017
CountryAustralia
CityMelbourne
Period19/08/1725/08/17

Abstract

Querying incomplete data is an important task both in data management, and in many AI applications that use query rewriting to take advantage of relational
database technology. Usually one looks for answers that are certain, i.e., true in every possible world represented by an incomplete database. For positive queries – expressed either in positive relational algebra or as unions of conjunctive queries – finding such answers can be done efficiently when
databases and query answers are sets. Real-life databases however use bag, rather than set, semantics. For bags, instead of saying that a tuple is certainly
in the answer, we have more detailed information in terms of the range of the numbers of occurrences of the tuple in query answers.We show that the behavior of positive queries is different under bag semantics: finding the minimum number of occurrences can still be done efficiently, but for maximum it becomes intractable. We use these results to investigate approximation schemes for computing certain answers to arbitrary first-order queries that have
been proposed for set semantics. One of them cannot be adapted to bags, as it relies on the intractable maxima of occurrences, but another scheme only
deals with minima, and we show how to adapt it to bag semantics without losing efficiency.

Event

26th International Joint Conference on Artificial Intelligence

19/08/1725/08/17

Melbourne, Australia

Event: Conference

ID: 36168819