2026-07-22T06:32:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7061 2024-03-06T10:39:26Z ddc:004 open_access

m-tables: Representing Missing Data Sundarmurthy, Bruhathi Koutris, Paraschos Lang, Willis Naughton, Jeffrey Tannen, Val missing values incomplete data c tables representation systems Representation systems have been widely used to capture different forms of incomplete data in various settings. However, existing representation systems are not expressive enough to handle the more complex scenarios of missing data that can occur in practice: these could vary from missing attribute values, missing a known number of tuples, or even missing an unknown number of tuples. In this work, we propose a new representation system called m-tables, that can represent many different types of missing data. We show that m-tables form a closed, complete and strong representation system under both set and bag semantics and are strictly more expressive than conditional tables under both the closed and open world assumptions. We further study the complexity of computing certain and possible answers in m-tables. Finally, we discuss how to "interpret" m-tables through a novel labeling scheme that marks a type of generalized tuples as certain or possible. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bruhathi Sundarmurthy and Paraschos Koutris and Willis Lang and Jeffrey Naughton and Val Tannen 2017 Is Part Of LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2017.21 urn:nbn:de:0030-drops-70618 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.21 eng https://creativecommons.org/licenses/by/3.0/legalcode