Synthesizing View Definitions from Data

Abstract

Given a database instance and a corresponding view instance, we address the {\em view definitions problem} (VDP): Find the most {\em succinct} and {\em 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 {\em exact} view definition, and if so find it. (2) Find the {\em best} view definition, i.e., one as close to the input view instance as possible, and as succinct as possible. (3) Find an {\em approximate} view definition that satisfies an input approximation threshold, and is as succinct as possible.