A vision for management of complex models

ABSTRACT

Many problems encountered when building applications of database systems involve the manipulation of models. By "model," we mean a complex structure that represents a design artifact, such as a relational schema, object-oriented interface, UML model, XML DTD, web-site schema, semantic network, complex document, or software configuration. Many uses of models involve managing changes in models and transformations of data from one model into another. These uses require an explicit representation of "mappings" between models. We propose to make database systems easier to use for these applications by making "model" and "model mapping" first-class objects with special operations that simplify their use. We call this capability model management.In addition to making the case for model management, our main contribution is a sketch of a proposed data model. The data model consists of formal, object-oriented structures for representing models and model mappings, and of high-level algebraic operations on those structures, such as matching, differencing, merging, selection, inversion and instantiation. We focus on structure and semantics, not implementation.

REFERENCES

• 1: Rakesh Agrawal , Shaul Dar , H. V. Jagadish, Direct transitive closure algorithms: design and performance evaluation, ACM Transactions on Database Systems (TODS), v.15 n.3, p.427-458, Sept. 1990 [doi>10.1145/88636.88888]
• 2: Rakesh Agrawal , H. V. Jagadish, Direct Algorithms for Computing the Transitive Closure of Database Relations, Proceedings of the 13th International Conference on Very Large Data Bases, p.255-266, September 01-04, 1987
• 3: David Shutt , Philip A. Bernstein , Thomas Bergstraesser , Jason Carlson , Shankar Pal , Paul Sanders, Microsoft repository version 2 and the open information model, Information Systems, v.24 n.2, p.71-98, April 1999 [doi>10.1016/S0306-4379(99)00006-X]
• 4: S. Bergamaschi , S. Castano , M. Vincini, Semantic integration of semistructured and structured data sources, ACM SIGMOD Record, v.28 n.1, p.54-59, March 1999 [doi>10.1145/309844.309897]
• 5: Jay Banerjee , Won Kim , Hyoung-Joo Kim , Henry F. Korth, Semantics and implementation of schema evolution in object-oriented databases, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.311-322, May 27-29, 1987, San Francisco, California, United States
• 6: [BLP00] Philip A. Bernstein, Alon Y. Levy, and Rachel A. Pottinger. A vision for management of complex models. Technical Report MSR-TR-2000-53, Microsoft Research, Available from http://research.microsoft.com/pubs/., 2000.
• 7: Francois Bancilhon , David Maier , Yehoshua Sagiv , Jeffrey D Ullman, Magic sets and other strange ways to implement logic programs (extended abstract), Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.1-15, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15399]
• 8: Alexander Borgida, Description Logics in Data Management, IEEE Transactions on Knowledge and Data Engineering, v.7 n.5, p.671-682, October 1995 [doi>10.1109/69.469829]
• 9: Francois Bancilhon , Raghu Ramakrishnan, An amateur's introduction to recursive query processing strategies, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.16-52, May 28-30, 1986, Washington, D.C., United States
• 10: [BR00] Philip A. Bernstein and Erhard Rahm. Data warehouse scenarios for model management. In Proceedings of the Entity Relationship Conference, pages 1-15. Springer Verlag, 2000.
• 11: R. G. G. Cattell , Douglas K. Barry , Mark Berler , Jeff Eastman , David Jordan , Craig Russell , Olaf Schadow , Torsten Stanienda , Fernando Velez, The object data standard: ODMG 3.0, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 12: Sudarshan S. Chawathe , Hector Garcia-Molina, Meaningful change detection in structured data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.26-37, May 11-15, 1997, Tucson, Arizona, United States
• 13: Kajal T. Claypool , Jing Jin , Elke A. Rundensteiner, SERF: schema evolution through an extensible, re-usable and flexible framework, Proceedings of the seventh international conference on Information and knowledge management, p.314-321, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288672]
• 14: Sudarshan S. Chawathe , Anand Rajaraman , Hector Garcia-Molina , Jennifer Widom, Change detection in hierarchically structured information, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.493-504, June 04-06, 1996, Montreal, Quebec, Canada
• 15: [DDL00] Anhai Doan, Pedro Domings, and Alon Y. Levy. Learning source descriptions for data integration. In In Proc. of WebDB, 2000.
• 16: Guozhu Dong , Chaoyi Pang, Maintaining transitive closure in first order after node-set and edge-set deletions, Information Processing Letters, v.62 n.4, p.193-199, May 28, 1997 [doi>10.1016/S0020-0190(97)00066-5]
• 17: Shaul Dar , Raghu Ramakrishnan, A performance study of transitive closure algorithms, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.454-465, May 24-27, 1994, Minneapolis, Minnesota, United States
• 18: Guozhu Dong , Jianwen Su, Incremental and decremental evaluation of transitive closure by first-order queries, Information and Computation, v.120 n.1, p.101-106, July 1995 [doi>10.1006/inco.1995.1102]
• 19: Guozhu Dong , Jianwen Su, Incremental maintenance of recursive views using relational calculus/SQL, ACM SIGMOD Record, v.29 n.1, p.44-51, March 2000 [doi>10.1145/344788.344808]
• 20: Alon Y. Halevy, Answering queries using views: A survey, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.270-294, December 2001 [doi>10.1007/s007780100054]
• 21: Yannis Ioannidis , Raghu Ramakrishnan , Linda Winger, Transitive closure algorithms based on graph traversal, ACM Transactions on Database Systems (TODS), v.18 n.3, p.512-576, Sept. 1993 [doi>10.1145/155271.155273]
• 22: H. V. Jagadish, A compression technique to materialize transitive closure, ACM Transactions on Database Systems (TODS), v.15 n.4, p.558-598, Dec. 1990 [doi>10.1145/99935.99944]
• 23: M. Jarke , M. Jeusfeld, Rule representation and management in conceptbase, ACM SIGMOD Record, v.18 n.3, p.46-51, Sep. 1989 [doi>10.1145/71031.71037]
• 24: [JMN⁺99] Jan Jannink, Prasenjit Mitra, Erich Neuhold, Srinivasan Pichai, Rudi Studer, and Gio Wiederhold. An algebra for semantic interoperation of semistructured data. In IEEE Knowledge and Data Engineering Exchange Workshop (KDEX), 1999.
• 25: Michael Kifer , Georg Lausen , James Wu, Logical foundations of object-oriented and frame-based languages, Journal of the ACM (JACM), v.42 n.4, p.741-843, July 1995 [doi>10.1145/210332.210335]
• 26: Chien-Tsai Liu , Shi-Kuo Chang , Panos K. Chrysanthis, Database schema evolution using EVER diagrams, Proceedings of the workshop on Advanced visual interfaces, p.123-132, June 01-04, 1994, Bari, Italy [doi>10.1145/192309.192338]
• 27: John Mylopoulos , Alex Borgida , Matthias Jarke , Manolis Koubarakis, Telos: representing knowledge about information systems, ACM Transactions on Information Systems (TOIS), v.8 n.4, p.325-362, Oct. 1990 [doi>10.1145/102675.102676]
• 28: Renée J. Miller , Laura M. Haas , Mauricio A. Hernández, Schema Mapping as Query Discovery, Proceedings of the 26th International Conference on Very Large Data Bases, p.77-88, September 10-14, 2000
• 29: Renée J. Miller , Yannis E. Ioannidis , Raghu Ramakrishnan, The Use of Information Capacity in Schema Integration and Translation, Proceedings of the 19th International Conference on Very Large Data Bases, p.120-133, August 24-27, 1993
• 30: [MMP95] John Mylopoulos and Renate Motschnig-Pitrik. Partitioning information bases with contexts. In Proceedings of 3rd CoopIS, pages 44-54, 1995.
• 31: Prasenjit Mitra , Gio Wiederhold , Martin L. Kersten, A Graph-Oriented Model for Articulation of Ontology Interdependencies, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.86-100, March 27-31, 2000
• 32: [Mye86] E. Myers. An o(nd) difference algorithm and its variations. Algorithmica, 1(2):251-266, 1986.
• 33: Tova Milo , Sagit Zohar, Using Schema Matching to Simplify Heterogeneous Data Translation, Proceedings of the 24rd International Conference on Very Large Data Bases, p.122-133, August 24-27, 1998
• 34: D. Saccà L. Palopol , D. Ursino, Semi-Automatic, Semantic Discovery of Properties from Database Schemes, Proceedings of the 1998 International Symposium on Database Engineering & Applications, p.244, July 08-10, 1998
• 35: N. C. Shu , B. C. Housel , R. W. Taylor , S. P. Ghosh , V. Y. Lum, EXPRESS: a data EXtraction, Processing, and Restructuring System, ACM Transactions on Database Systems (TODS), v.2 n.2, p.134-174, June 1977 [doi>10.1145/320544.320549]
• 36: Dennis Shasha , Kaizhong Zhang, Fast algorithms for the unit cost editing distance between trees, Journal of Algorithms, v.11 n.4, p.581-621, Dec. 1990 [doi>10.1016/0196-6774(90)90011-3]
• 37: Jason Tsong-Li Wang , Dennis Shasha , George J. S. Chang , Liam Relihan , Kaizhong Zhang , Girish Patel, Structural matching and discovery in document databases, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.560-563, May 11-15, 1997, Tucson, Arizona, United States
• 38: [ZWS95] Kaizhong Zhang, Jason Tsong-Li Wang, and Dennis Shasha. On the editing distance between undirected acyclic graphs and related problems. In Proceedings of CPM, pages 395-407, 1995.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Design, Management, Performance, Theory