Efficient maintenance of materialized mediated views

ABSTRACT

Integrating data and knowledge from multiple heterogeneous sources -- like databases, knowledge bases or specific software packages -- is often required for answering certain queries. Recently, a powerful framework for defining mediated views spanning multiple knowledge bases by a set of constrained rules was proposed [24, 4, 16]. We investigate the materialization of these views by unfolding the view definition and the efficient maintenance of the resulting materialized mediated view in case of updates. Thereby, we consider two kinds of updates: updates to the view and updates to the underlying sources. For each of these two cases several efficient algorithms maintaining materialized mediated views are given. We improve on previous algorithms like the DRed algorithm [12] and introduce a new fixpoint operator W_P which -- opposed to the standard fixpoint operator T_P [9] -- allows us to correctly capture the update's semantics without any recomputation of the materialized view.

References

1. 1.S. Abiteboul, S. Cluet, and T. Milo. Querying and updating the file. In Proc. Int. Conf. on Very Large Da~a Bases (VLDB), page~ 73-84, 1993.
2. 2.S. Adah and R. Emery. (1994) A Uniform Framework for Integrating Knowledge in Heterogeneous Knowledge Systems, to appear in Proceedings of ICDE.
3. 3.S. Adah and V.S. Subrahmanian. (1993) Amalgamating Knowledge Bases, N: Algorithms, Data Structures and Query Processing, submitted for journal publication.
4. 4.S. Adah and V.8. Subrahmanian. (1994) Amalgamating Knowledge Bases, III: Distributed Mediators, to appear in Journal of Cooperative Informatzon Systems, Dec. t994.
5. 5.J. Blakeley, N. Coburn, and P.-A. Larson. Updating derived relations: Detecting irrelevant and autonomously computable updates. A CM Trans. on Database Systems, 14(3):369-400, 1989.
6. 6.Stefano Ceri and Jennifer Widom. Deriving Production Rules for Incremental View Maintenance. In 17th VLDB, 1991.
7. 7.Stefano Ceri and Jennifer Widom. Deriving Incremental Production Rules for Deductive Data. IBM RJ 9071, IBM Almaden, 1992.
8. 8.M. Falaschi, G. Levi, M. Martelli, C. Palamidessi (1991) A New Declarative Semantics for Logic Programs, ICLP, 1991.
9. 9.M. Gabbrielli, G. Levi. (1991) Modelling answer constraints in Constraint Logic Programs, ICLP, 1991, pp.238-251,
10. 10.N. Gehani, It. Jagadish, and W. Roome. OdeFS" A file system interface to an objectoriented database, in Proc. Int. Conf. on Very Large Data Bases (VLDB), pages 249- 260, 1994.
11. 11.Ashish Gupta, Dinesh Katiyar, and Inderpal Singh Mumick. Counting Solutions to the View Maintenance Problem. in Workshop on Deductive Databases, JICSLP, 1992.
12. 12.A. Gupta, I.S. Mumick and V.S. Subrahmanian. Maintaining Views Incrementally, Proc. 1993 A CM SIGMOD Conf. on Management of Data, Washington, DC.
13. 13.E. Hanson. A performance analysis of view materialization strategies. In Proc. of the A CM SIGMOD Conf. on Management of Data, pages 440-453, 1987.
14. 14.John V. Harrison and Suzanne Dietrich. Maintenance of Materialized Views in a Deductive Database: An Update Propagation Approach. In Workshop on Deductive Databases, JICSLP, 1992.
15. 15.J. Jaffar, J.-L. Lassez. Constraint Logic Programming In. Proceedings of Fourteenth Annual ACM Symposium on Principles of Programming Languages, pp. 111-119. ACM, New York, USA, 1987
16. 16.J. Lu, A. Nerode and V.S. Subrahmanian. Hybrid Knowledge Bases, to appear in IEEE Transactions on Data and Knowledge Engineerzng.
17. 17.P. Kanellakis, G. Kuper and P. Revesz. (1990) Constraint Query Languages, Proc. 9th ACM Symp. on Principles of Database Systems, pps 299-313.
18. 18.A. Kemper, C. Kilger, G. Moerkotte. Function Materialization in Object Bases: Design, Realization, and Evaluation IEEE Transactions on Knowledge and Data Engineering, Vol.6, No.4, August 1994
19. 19.V. Kfichenhoff. On the efficient computation of the difference between consecutive database states. In Proc. Iu~. Conf. on Deductive and Object-Oriented Databases (DOOD), pages 478-502, 1991.
20. 20.G. Moerkotte and P.C. Lockemann. Reactive consistency control in deductive databases. A CM Trans. on Database Systems, 16(4):670- 702, 1991.
21. 21.I. S. Mumick. Query Optimization in Deductive and Relational Databases. Ph.D. Thesis, Stanford University, CA 94305, 1991.
22. 22.Oded Shmueli and Alon itai. Maintenance of Views. in Sigmod Record, 14(2):240-255, 1984.
23. 23.M. Stonebraker, A. Jhingran, j. Goh, and S. Potamianos. On rules, procedures, caching and views in data base systems, in Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 281-290, 1990.
24. 24.V.S. Subrahmanian. Amalgamating Knowledge Bases, A CM Trans. on Database Systems, 19, 2, pps 291-331, 1994.
25. 25.V.S. Subrahmanian. Hybrid Knowledge Bases for Integratzng Symbolic, Numemc and Image Data, Proc. 1994 Intl. Workshop on Applied Imagery and Pattern Recognition, Washington DC, Oct. 1994, SPIE Press.
26. 26.V.S. Subrahmanian, S. Adali, A. Brink, R. Emery, A. Rajput, T.J. Rogers, R. Ross, and C. ward. (1994) HERMES: A Heterogeneous Reasoning and Mediator System, draft manuscript.
27. 27.E. Teniente and A. Olive. Updating knowledge bases while maintaining their consistency. Report de recerca, Universitat Politecnica de Catalunya, Report LSI-94-25-R. Barcelona, Spain. 1994.
28. 28.Toni Urpi and Antoni Olive. A Method for Change Computation in Deductive Databases. In 18th VLDB~ pases 225-237~ 1992.
29. 29.G. Wied~hold. (1993) I~Z~ig~n~ In~g~a~o~ of Information, Proc. 1993 ACM SIGMOD Conf. on Management of Data, pps 434-437.

Index Terms

• Information systems

  • Data management systems

    • Database design and models

    • Database management system engines

      • Database query processing

  • Information systems applications

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Database query processing and optimization (theory)