Side-Effect Estimation: A Filtering Approach to the View Update Problem

Yun Peng, Byron Choi, Jianliang Xu, Haibo Hu, Sourav S. Bhowmick

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

Views and their updates have long been a fundamental technology required in a wide range of applications. However, it has been known that updates through views is a classical intractable problem. In this paper, we propose a novel, data-oriented approach to this problem that provides a practical support for view updates. In particular, we propose a summarization of the source database of views, which serves as an update filter. The update filter aims to efficiently reject untranslatable view updates by estimating the side effects of the updates, thereby avoiding costly translation analysis. For applications where estimation errors are not preferred, our update filter can be tuned to be exact. In this paper, we present our approach with SPJ views, an important class of view definitions. We first revise the notion of estimation errors to quantify the filter's qualities. We then propose a novel join cardinality summary (JCard) derived from cardinality equivalence. An estimation algorithm is proposed. Finally, we present optimizations enabling the construction of an accurate JCard through heuristics and sampling. Our extensive experiments show that update filters are efficient and can be easily tuned to produce accurate estimations on TPC-H and DBLP.
Original languageEnglish
Article number6560063
Pages (from-to)2307-2322
Number of pages16
JournalIEEE Transactions on Knowledge and Data Engineering
Volume26
Issue number9
DOIs
Publication statusPublished - 1 Sept 2014
Externally publishedYes

Keywords

  • Database Management
  • Relational databases

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Side-Effect Estimation: A Filtering Approach to the View Update Problem'. Together they form a unique fingerprint.

Cite this