Synthesizing view definitions from data

Anish Das Sarma, Aditya Parameswaran, Hector Garcia-Molina, Jennifer Widom

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

Abstract

Given a database instance and a corresponding view instance, we address the view definitions problem (VDP): Find the most succinct and accurate view definition, when the view query is restricted to a specific family of queries. We study the tradeoffs among succintness, level of approximation, and the family of queries through algorithms and complexity results. For each family of queries, we address three variants of the VDP: (1) Does there exist an exact view definition, and if so find it. (2) Find the best view definition, i.e., one as close to the input view instance as possible, and as succinct as possible. (3) Find an approximate view definition that satisfies an input approximation threshold, and is as succinct as possible.

Original languageEnglish (US)
Title of host publicationDatabase Theory - ICDT 2010
Subtitle of host publication13th International Conference on Database Theory, Proceedings
Pages89-103
Number of pages15
DOIs
StatePublished - 2010
Event13th International Conference on Database Theory, ICDT'10 - Lausanne, Switzerland
Duration: Mar 23 2010Mar 25 2010

Publication series

NameACM International Conference Proceeding Series

Other

Other13th International Conference on Database Theory, ICDT'10
Country/TerritorySwitzerland
CityLausanne
Period3/23/103/25/10

Keywords

  • algorithms
  • complexity
  • query synthesis
  • view definitions

ASJC Scopus subject areas

  • Software
  • Human-Computer Interaction
  • Computer Vision and Pattern Recognition
  • Computer Networks and Communications

Cite this