Using schematically heterogeneous structures

ABSTRACT

Schematic heterogeneity arises when information that is represented as data under one schema, is represented within the schema (as metadata) in another. Schematic heterogeneity is an important class of heterogeneity that arises frequently in integrating legacy data in federated or data warehousing applications. Traditional query languages and view mechanisms are insufficient for reconciling and translating data between schematically heterogeneous schemas. Higher order query languages, that permit quantification over schema labels, have been proposed to permit querying and restructuring of data between schematically disparate schemas. We extend this work by considering how these languages can be used in practice. Specifically, we consider a restricted class of higher order views and show the power of these views in integrating legacy structures. Our results provide insights into the properties of restructuring transformations required to resolve schematic discrepancies. In addition, we show how the use of these views permits schema browsing and new forms of data independence that are important for global information systems. Furthermore, these views provide a framework for integrating semi-structured and unstructured queries, such as keyword searches, into a structured querying environment. We show how these views can be used with minimal extensions to existing query engines. We give conditions under which a higher order view is usable for answering a query and provide query translation algorithms.

REFERENCES

• 1: S. Abiteboul, H. Garcia-Molina, Y. Papakonstantinou, and R. Yerneni. Fusion Queries over Internet Databases. Technical Report unpublished manuscript, Stanford University, 1997.
• 2: Rafi Ahmed , Philippe De Smedt , Weimin Du , William Kent , Mohammad A. Ketabchi , Witold A. Litwin , Abbas Rafii , Ming-Chien Shan, The Pegasus Heterogeneous Multidatabase System, Computer, v.24 n.12, p.19-27, December 1991 [doi>10.1109/2.116885]
• 3: Y. Arens, C. Y. Chee, C. N. Hsu, and C. A. KnobIock. Retrieving and Integrating Data from Multiple Information Sources. intl. J. of Intelligent and Cooperative Info. Systems, 2(2):127-158, 1993.
• 4: Thierry Barsalou , Dipayan Gangopadhyay, M(DM): An Open Framework for Interoperation of Multimodel Multidatabase Systems, Proceedings of the Eighth International Conference on Data Engineering, p.218-227, February 03-07, 1992
• 5: C. Batini , M. Lenzerini , S. B. Navathe, A comparative analysis of methodologies for database schema integration, ACM Computing Surveys (CSUR), v.18 n.4, p.323-364, Dec. 1986 [doi>10.1145/27633.27634]
• 6: Michael L. Brodie , Michael Stonebraker, Migrating legacy systems: gateways, interfaces & the incremental approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1995
• 7: M. J. Carey , L. M. Haas , P. M. Schwarz , M. Arya , W. F. Cody , R. Fagin , M. Flickner , A. W. Luniewski , W. Niblack , D. Petkovic , J. Thomas , J. H. Williams , E. L. Wimmers, Towards heterogeneous multimedia information systems: the Garlic approach, Proceedings of the 5th International Workshop on Research Issues in Data Engineering-Distributed Object Management (RIDE-DOM'95), p.124, March 06-07, 1995
• 8: Surajit Chaudhuri , Ravi Krishnamurthy , Spyros Potamianos , Kyuseok Shim, Optimizing Queries with Materialized Views, Proceedings of the Eleventh International Conference on Data Engineering, p.190-200, March 06-10, 1995
• 9: Surajit Chaudhuri, Optimization of real conjunctive queries, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.59-70, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153856]
• 10: S. Chawathe, H. Gaxcia-Molina, J. Hammer, K. Ireland, Y. Papakonstantinou, J. Ullman, and J. Widom. The TSIMMIS Project: Integration of Heterogeneous Information Sources. In Proc. of the l OOth Anniversary Meeting of the Information Processing Society of Japan(IPSJ), pages 7-18, Tokyo, Japan, October 1994.
• 11: Weidong Chen , Michael Kifer , David S. Warren, HiLog as a platform for database languages, Proceedings of the second international workshop on Database programming languages, p.315-329, December 1989, Salishan Lodge, Gleneden Beach, Oregon, United States
• 12: E.F Codd and S. B. Codd. Providing OLAP (On-line Analytical Processing) to User-Analysts: An IT Mandate. Technical report, E.F. Codd and Associates, 1994.
• 13: U. Dayal and H. Y. Hwang. View Definition and Generalization for Database Integration in a Multidatabase System. IEEE Trans. on Software Engineering, SE- 10(6):628-644, November 1984.
• 14: Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996
• 15: Richard Hull, Relative information capacity of simple relational database schemata, SIAM Journal on Computing, v.15 n.3, p.856-886, August 1986 [doi>10.1137/0215061]
• 16: Richard Hull, Managing semantic heterogeneity in databases: a theoretical prospective, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.51-61, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263668]
• 17: Jan Van den Bussche , Dirk Van Gucht , Gottfried Vossen, Reflective programming in the relational algebra, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.17-25, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153852]
• 18: Vipul Kashyap , Amit Sheth, Semantic and schematic similarities between database objects: a context-based approach, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.276-304, December 1996 [doi>10.1007/s007780050029]
• 19: W. Kent. The Many Forms of a Single Fact. In Proc. of IEEE Int'l Computer Conf. (COMPCON), pages 438- 443, 1989.
• 20: Michael Kifer , Won Kim , Yehoshua Sagiv, Querying object-oriented databases, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.393-402, June 02-05, 1992, San Diego, California, United States
• 21: Won Kim , Jungyun Seo, Classifying Schematic and Data Heterogeneity in Multidatabase Systems, Computer, v.24 n.12, p.12-18, December 1991 [doi>10.1109/2.116884]
• 22: Ravi Krishnamurthy , Witold Litwin , William Kent, Language features for interoperability of databases with schematic discrepancies, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.40-49, May 29-31, 1991, Denver, Colorado, United States
• 23: Fereidoon Sadri, Modeling Uncertainty in Object-Oriented Databases, Proceedings of the SOFTEKS Workshop on Incompleteness and Uncertainty in Information Systems, p.56-68, October 08-09, 1993
• 24: Laks V. S. Lakshmanan , Fereidoon Sadri , Iyer N. Subramanian, SchemaSQL - A Language for Interoperability in Relational Multi-Database Systems, Proceedings of the 22th International Conference on Very Large Data Bases, p.239-250, September 03-06, 1996
• 25: Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220198]
• 26: Alon Y. Levy , Anand Rajaraman , Joann J. Ordille, Querying Heterogeneous Information Sources Using Source Descriptions, Proceedings of the 22th International Conference on Very Large Data Bases, p.251-262, September 03-06, 1996
• 27: Witold Litwin , Abdelaziz Abdellatif, Multidatabase interoperability, Computer, v.19 n.12, p.10-18, Dec. 1986 [doi>10.1109/MC.1986.1663123]
• 28: Witold Litwin , M. Ketabchi , Ravi Krishnamurthy, First order normal form for relational databases and multidatabases, ACM SIGMOD Record, v.20 n.4, p.74-76, Dec. 1991 [doi>10.1145/141356.141389]
• 29: R. J. Miller. Using Schematically Heterogeneous Structures: Extended Version. Technical Report OSU- CISRC-3/98-TR09, Ohio State University, Dept of Computer and Information Science, 1998.
• 30: 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
• 31: Renée J. Miller , Odysseas G. Tsatalos , John H. Williams, DataWeb: Customizable Database Publishing for the Web, IEEE MultiMedia, v.4 n.4, p.14-21, October 1997 [doi>10.1109/93.641875]
• 32: Yannis Papakonstantinou , Hector Garcia-Molina , Jennifer Widom, Object Exchange Across Heterogeneous Information Sources, Proceedings of the Eleventh International Conference on Data Engineering, p.251-260, March 06-10, 1995
• 33: Kenneth A. Ross, Relations with relation names as arguments: algebra and calculus, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.346-353, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137905]
• 34: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 35: Divesh Srivastava , Shaul Dar , H. V. Jagadish , Alon Y. Levy, Answering Queries with Aggregation Using Views, Proceedings of the 22th International Conference on Very Large Data Bases, p.318-329, September 03-06, 1996
• 36: A. Tomasic, L. Raschid, and P. Valduriez. A Data Model and Query Processing Techniques for Scaling Access to Distributed Heterogeneous Databases in Disco. IEEE Trans on Computers, 1997.
• 37: Odysseas G. Tsatalos , Marvin H. Solomon , Yannis E. Ioannidis, The GMAP: a versatile tool for physical data independence, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.2, p.101-118, April 1996 [doi>10.1007/s007780050018]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

          Nouns: SQL

General Terms:
Algorithms, Languages