On the computation of relational view complements

ABSTRACT

Views as a means to describe parts of a given data collection play an important role in many database applications. In dynamic environments, where data is updated, not only information provided by views, but also information provided by data sources but missing from views turns out to be relevant: Previously, this missing information was characterized in terms of view complements; recently, it was shown that view complements can be exploited in the context of data warehouses to guarantee desirable warehouse properties such as independence and self-maintainability. As the complete source information is a trivial complement for any given view, a natural interest for "small" or even "minimal" complements arises. However, the computation of minimal complements is still not too well understood. In this paper, we show how to compute reasonably small (and in special cases even minimal) complements for monotonic relational views, where the complexity of constructing complements is polynomial in the size of schema information.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Alfred V. Aho , Jeffrey D. Ullman, Universality of data retrieval languages, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.110-119, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567763]
• 3: Sandra De Amo , Mirian Halfeld Ferrari Alves, Efficient Maintenance of Temporal Data Warehouses, Proceedings of the 2000 International Symposium on Database Engineering & Applications, p.188-196, September 18-20, 2000
• 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: A. K. Chandra, D. Harel, "Computable Queries for Relational Data Bases," JCSS 21 (2), 1980, 156-178.
• 6: Stavros S. Cosmadakis , Christos H. Papadimitriou, Updates of Relational Views, Journal of the ACM (JACM), v.31 n.4, p.742-760, Oct. 1984 [doi>10.1145/1634.1887]
• 7: Stephen J. Hegner, Unique complements and decompositions of database schemata, Journal of Computer and System Sciences, v.48 n.1, p.9-57, Feb. 1994 [doi>10.1016/S0022-0000(05)80021-2]
• 8: P. Honeyman, "Extension Joins", Proc. 6th VLDB 1980, 239-244.
• 9: R. M. Karp, "Reducibility among Combinatorial Problems," in Complexity of Computer Computations, Plenum Press, 1972, 85-103.
• 10: Arthur M Keller , Jeffrey D Ullman, On complementary and independent mappings on databases, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 11: D. Laurent , J. Lechtenbörger , N. Spyratos , G. Vossen, Monotonic complements for independent data warehouses, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.295-315, December 2001 [doi>10.1007/s007780100055]
• 12: J. Lechtenbörger, "Data Warehouse Schema Design," Ph.D. dissertation, University of Muenster, 2001; available as Vol. 79 in "Dissertationen zu Datenbanken und Informationssystemen," Akademische Verlagsgesellschaft Aka GmbH, Berlin, 2001.
• 13: J. Lechtenbörger, G. Vossen, "On the Computation of Relational View Complements," Technical Report 13/01 - I, University of Muenster, October 2001.
• 14: Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
• 15: Gottfried Vossen, Data models, database languages and database management systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.m Miscellaneous

General Terms:
Design, Theory

Keywords:
view complement