On Querying Incomplete Information in Databases under Bag Semantics

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


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.
Original languageEnglish
Title of host publicationProceedings of the 26th International Joint Conference on Artificial Intelligence
PublisherIJCAI Inc
Number of pages7
ISBN (Electronic)978-0-9992411-0-3
Publication statusPublished - 25 Aug 2017
Event26th International Joint Conference on Artificial Intelligence - Melbourne, Australia
Duration: 19 Aug 201725 Aug 2017


Conference26th International Joint Conference on Artificial Intelligence
Abbreviated titleIJCAI 2017
Internet address


Dive into the research topics of 'On Querying Incomplete Information in Databases under Bag Semantics'. Together they form a unique fingerprint.

Cite this