Synthesizing view definitions from data

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

doi:10.1145/1804669.1804683

Synthesizing view definitions from data

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

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Database Theory - ICDT 2010
Subtitle of host publication	13th International Conference on Database Theory, Proceedings
Pages	89-103
Number of pages	15
DOIs	https://doi.org/10.1145/1804669.1804683
State	Published - 2010
Externally published	Yes
Event	13th International Conference on Database Theory, ICDT'10 - Lausanne, Switzerland Duration: Mar 23 2010 → Mar 25 2010

Publication series

Name	ACM International Conference Proceeding Series

Other

Other	13th International Conference on Database Theory, ICDT'10
Country/Territory	Switzerland
City	Lausanne
Period	3/23/10 → 3/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

Online availability

10.1145/1804669.1804683

Library availability

Discover UIUC Full Text

Cite this

Das Sarma, A, Parameswaran, A, Garcia-Molina, H & Widom, J 2010, Synthesizing view definitions from data. in Database Theory - ICDT 2010: 13th International Conference on Database Theory, Proceedings. ACM International Conference Proceeding Series, pp. 89-103, 13th International Conference on Database Theory, ICDT'10, Lausanne, Switzerland, 3/23/10. https://doi.org/10.1145/1804669.1804683

@inproceedings{00ead9d85c284291bf78c564eab66f54,

title = "Synthesizing view definitions from data",

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.",

keywords = "algorithms, complexity, query synthesis, view definitions",

author = "{Das Sarma}, Anish and Aditya Parameswaran and Hector Garcia-Molina and Jennifer Widom",

year = "2010",

doi = "10.1145/1804669.1804683",

language = "English (US)",

isbn = "9781605589473",

series = "ACM International Conference Proceeding Series",

pages = "89--103",

booktitle = "Database Theory - ICDT 2010",

note = "13th International Conference on Database Theory, ICDT'10 ; Conference date: 23-03-2010 Through 25-03-2010",

}

TY - GEN

T1 - Synthesizing view definitions from data

AU - Das Sarma, Anish

AU - Parameswaran, Aditya

AU - Garcia-Molina, Hector

AU - Widom, Jennifer

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

KW - algorithms

KW - complexity

KW - query synthesis

KW - view definitions

UR - http://www.scopus.com/inward/record.url?scp=77954469726&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77954469726&partnerID=8YFLogxK

U2 - 10.1145/1804669.1804683

DO - 10.1145/1804669.1804683

M3 - Conference contribution

AN - SCOPUS:77954469726

SN - 9781605589473

T3 - ACM International Conference Proceeding Series

SP - 89

EP - 103

BT - Database Theory - ICDT 2010

T2 - 13th International Conference on Database Theory, ICDT'10

Y2 - 23 March 2010 through 25 March 2010

ER -

Synthesizing view definitions from data

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Cite this