On propagation of deletions and annotations through views

ABSTRACT

We study two classes of view update problems in relational databases. We are given a source database S, a monotone query Q, and the view Q(S) generated by the query. The first problem that we consider is the classical view deletion problem where we wish to identify a minimal set T of tuples in S whose deletion will eliminate a given tuple t from the view. We study the complexity of optimizing two natural objectives in this setting, namely, find T to minimize the side-effects on the view, and the source, respectively. For both objective functions, we show a dichotomy in the complexity. Interestingly, the problem is either in P or is NP-hard, for queries in the same class in either objective function.The second problem in our study is the annotation placement problem. Suppose we annotate an attribute of a tuple in S. The rules for carrying the annotation forward through a query are easily stated. On the other hand, suppose we annotate an attribute of a tuple in the view Q(S), what annotation(s) in S will cause this annotation to appear in the view, minimizing the propagation to other attributes in Q(S)? View annotation is becoming an increasingly useful method of communicating meta-data among users of shared scientific data sets, and to our knowledge, there has been no formal study of this problem.Our study of these problems gives us important insights into computational issues involved in data provenance or lineage --- the process by which data moves through databases. We show that the two problems correspond to two fundamentally distinct notions of provenance, why and where-provenance.

REFERENCES

• 1: Arthur M. Keller, Algorithms for translating view updates to database updates for views involving selections, projections, and joins, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.154-163, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325423]
• 2: Arthur M. Keller, Choosing a View Update Translator by Dialog at View Definition Time, Proceedings of the 12th International Conference on Very Large Data Bases, p.467-474, August 25-28, 1986
• 3: D. Maier and L. Delcambre. Superimposed Information for the Internet. In Proceedings of the Int'l Workshop on Web and Databases (WebDB), pages 1-9, 1999.
• 4: F. Bancilhon , N. Spyratos, Update semantics of relational views, ACM Transactions on Database Systems (TODS), v.6 n.4, p.557-575, Dec. 1981 [doi>10.1145/319628.319634]
• 5: E. M. Gold. Complexity of automatic identification of given data, 1974. Unpublished manuscript.
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: Peter Buneman , Sanjeev Khanna , Wang Chiew Tan, Why and Where: A Characterization of Data Provenance, Proceedings of the 8th International Conference on Database Theory, p.316-330, January 04-06, 2001
• 8: Stavros S. Cosmadakis , Christos H. Papadimitriou, Updaies of relational views, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588096]
• 9: Lincoln Stein. Distributed Annotation Server. http://biodas.org.
• 10: Thomas J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing, p.216-226, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804350]
• 11: Umeshwar Dayal , Philip A. Bernstein, On the correct translation of update operations on relational views, ACM Transactions on Database Systems (TODS), v.7 n.3, p.381-416, Sept. 1982 [doi>10.1145/319732.319740]
• 12: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 13: W3C. Annotea Project. http://www.w3.org/2001/Annotea.
• 14: Y. Cui and J. Widom. Run-Time Translation of View Tuple Deletions Using Data Lineage. Technical report, Stanford University, 2001. http://dbpubs.stanford.edu:8090/pub/2001-24.
• 15: Yingwei Cui , Jennifer Widom , Janet L. Wiener, Tracing the lineage of view data in a warehousing environment, ACM Transactions on Database Systems (TODS), v.25 n.2, p.179-227, June 2000 [doi>10.1145/357775.357777]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

Additional Classification:
  K. Computing Milieux
  K.8 PERSONAL COMPUTING
      K.8.1 Application Packages
          Subjects: Database processing

General Terms:
Design, Languages, Theory