1 Search Results for "Lang, Willis"

Document

DOI: 10.4230/LIPIcs.ICDT.2017.21

m-tables: Representing Missing Data

Authors: Bruhathi Sundarmurthy, Paraschos Koutris, Willis Lang, Jeffrey Naughton, and Val Tannen

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

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.

Cite as

Bruhathi Sundarmurthy, Paraschos Koutris, Willis Lang, Jeffrey Naughton, and Val Tannen. m-tables: Representing Missing Data. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{sundarmurthy_et_al:LIPIcs.ICDT.2017.21,
  author =	{Sundarmurthy, Bruhathi and Koutris, Paraschos and Lang, Willis and Naughton, Jeffrey and Tannen, Val},
  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 =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.21},
  URN =		{urn:nbn:de:0030-drops-70618},
  doi =		{10.4230/LIPIcs.ICDT.2017.21},
  annote =	{Keywords: missing values, incomplete data, c tables, representation systems}
}

Refine by Author
1 Koutris, Paraschos
1 Lang, Willis
1 Naughton, Jeffrey
1 Sundarmurthy, Bruhathi
1 Tannen, Val

Refine by Classification

Refine by Keyword
1 c tables
1 incomplete data
1 missing values
1 representation systems

Refine by Type
1 document

Refine by Publication Year
1 2017

1 Search Results for "Lang, Willis"

m-tables: Representing Missing Data

Abstract

Cite as

Thanks for your feedback!

Could not send message