License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2017.21
URN: urn:nbn:de:0030-drops-70618
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7061/
Go to the corresponding LIPIcs Volume Portal

Sundarmurthy, Bruhathi ; Koutris, Paraschos ; Lang, Willis ; Naughton, Jeffrey ; Tannen, Val

m-tables: Representing Missing Data

pdf-format:
LIPIcs-ICDT-2017-21.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{sundarmurthy_et_al:LIPIcs:2017:7061,
  author =	{Bruhathi Sundarmurthy and Paraschos Koutris and Willis Lang and Jeffrey Naughton and Val Tannen},
  title =	{{m-tables: Representing Missing Data}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{21:1--21:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Michael Benedikt and Giorgio Orsi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7061},
  URN =		{urn:nbn:de:0030-drops-70618},
  doi =		{10.4230/LIPIcs.ICDT.2017.21},
  annote =	{Keywords: missing values, incomplete data, c tables, representation systems}
}

Keywords: missing values, incomplete data, c tables, representation systems
Collection: 20th International Conference on Database Theory (ICDT 2017)
Issue Date: 2017
Date of publication: 17.03.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI