Managing Semantic Heterogeneity in Databases: A Theoretical Perspective.

@inproceedings{DBLP:conf/pods/Hull97,
  author    = {Richard Hull},
  editor    = {Alberto O. Mendelzon and
               Z. Meral {\"O}zsoyoglu},
  title     = {Managing Semantic Heterogeneity in Databases: A Theoretical Perspective},
  booktitle = {Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona,
               USA},
  publisher = {ACM Press},
  year      = {1997},
  isbn      = {0-89791-910-6},
  pages     = {51-61},
  ee        = {http://doi.acm.org/10.1145/263661.263668, db/conf/pods/Hull97.html},
  crossref  = {DBLP:conf/pods/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Modern database management systems essentially solve the problem of accessing and managing large volumes of related data on a single platform, or on a cluster of tightly-coupled platforms. But many problems remain when two or more databases need to work together. A fundamental problem is raised by semantic heterogeneity - the fact that data duplicates across multiple databases is represented differently in the underlying database schemes. This tutorial describes fundamental problems raised by semantic heterogeneity and surveys theoretical frameworks that can provide solutions for them.

The tutorial considers the following topics: (1) representative architectures for supporting database interoperation; (2) notions for comparing the "information capacity" of database schemas; (3) providing support for read-only integrated views of data, including the virtual and materialized approaches; (4) providing support for read-write integrated views of data, including the issue of workflows on heterogeneous databases; and (5) research and tools for accessing and effectively using meta-data, e.g., to identify the relationships between schemas of different databases.

Copyright © 1997 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

Slides

References

[AABM82]

Paolo Atzeni, Giorgio Ausiello, Carlo Batini, Marina Moscarini: Inclusion and Equivalence between Relational Database Schemata. Theor. Comput. Sci. 19: 267-285(1982)

[AB91]

Serge Abiteboul, Anthony J. Bonner: Objects and Views. SIGMOD Conference 1991: 238-247

[Abi97]

Serge Abiteboul: Querying Semi-Structured Data. ICDT 1997: 1-18

[ACHK93]

Yigal Arens, Chin Y. Chee, Chun-Nan Hsu, Craig A. Knoblock: Retrieving and Integrating Data from Multiple Information Sources. Int. J. Cooperative Inf. Syst. 2(2): 127-158(1993)

[ACM90]

...

[AGS87]

Rafael Alonso, Hector Garcia-Molina, Kenneth Salem: Concurrency Control and Recovery for Global Procedures in Federated Database Systems. IEEE Data Eng. Bull. 10(3): 5-11(1987)

[AH88]

Serge Abiteboul, Richard Hull: Restructuring Hierarchical Database Objects. Theor. Comput. Sci. 62(1-2): 3-38(1988)

[AHV95]

Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents

[AIR97]

Joseph Albert, Yannis E. Ioannidis, Raghu Ramakrishnan: Conjunctive Query Equivalence of Keyed Relational Schemas. PODS 1997: 44-50

[AK89]

Serge Abiteboul, Paris C. Kanellakis: Object Identity as a Query Language Primitive. SIGMOD Conference 1989: 159-173

[ANRS92]

Mansoor Ansari, Linda Ness, Marek Rusinkiewicz, Amit P. Sheth: Using Flexible Transactions to Support Multi-System Telecommunication Applications. VLDB 1992: 65-76

[AT93]

Paolo Atzeni, Riccardo Torlone: A metamodel approach for the management of multiple models and translation of schemes. Inf. Syst. 18(6): 349-362(1993)

[AV88]

Serge Abiteboul, Victor Vianu: Procedural and Declarative Database Update Languages. PODS 1988: 240-250

[AV90]

Serge Abiteboul, Victor Vianu: Procedural Languages for Database Queries and Updates. J. Comput. Syst. Sci. 41(2): 181-229(1990)

[B+81]

Philip A. Bernstein, Nathan Goodman, Eugene Wong, Christopher L. Reeve, James B. Rothnie Jr.: Query Processing in a System for Distributed Databases (SDD-1). ACM Trans. Database Syst. 6(4): 602-625(1981)

[BBMR89]

Alexander Borgida, Ronald J. Brachman, Deborah L. McGuinness, Lori Alperin Resnick: CLASSIC: A Structural Data Model for Objects. SIGMOD Conference 1989: 58-67

[BDFS97]

Peter Buneman, Susan B. Davidson, Mary F. Fernandez, Dan Suciu: Adding Structure to Unstructured Data. ICDT 1997: 336-350

[BDHO95]

Peter Buneman, Susan B. Davidson, Kyle Hart, G. Christian Overton, Limsoon Wong: A Data Transformation System for Biological Data Sources. VLDB 1995: 158-169

[BDW91]

Peter Buneman, Susan B. Davidson, Aaron Watters: A Semantics for Complex Objects and Approximate Answers. J. Comput. Syst. Sci. 43(1): 170-218(1991)

[BGS92]

Yuri Breitbart, Hector Garcia-Molina, Abraham Silberschatz: Overview of Multidatabase Transaction Management. VLDB J. 1(2): 181-239(1992)

[BHM90]

Philip A. Bernstein, Meichun Hsu, Bruce Mann: Implementing Recoverable Requests Using Queues. SIGMOD Conference 1990: 112-122

[BK91]

Naser S. Barghouti, Gail E. Kaiser: Concurrency Control in Advanced Database Applications. ACM Comput. Surv. 23(3): 269-317(1991)

[BLN86]

Carlo Batini, Maurizio Lenzerini, Shamkant B. Navathe: A Comparative Analysis of Methodologies for Database Schema Integration. ACM Comput. Surv. 18(4): 323-364(1986)

[BLT86]

José A. Blakeley, Per-Åke Larson, Frank Wm. Tompa: Efficiently Updating Materialized Views. SIGMOD Conference 1986: 61-71

[BMSU81]

Catriel Beeri, Alberto O. Mendelzon, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalence of Relational Database Schemes. SIAM J. Comput. 10(2): 352-370(1981)

[BOT86]

Yuri Breitbart, Peter L. Olson, Glenn R. Thompson: Database Integration in a Distributed Heterogeneous Database System. ICDE 1986: 301-310

[Bre90]

Yuri Breitbart: Multidatabase Interoperability. SIGMOD Record 19(3): 53-60(1990)

[BS81]

François Bancilhon, Nicolas Spyratos: Update Semantics of Relational Views. ACM Trans. Database Syst. 6(4): 557-575(1981)

[Bun97]

Peter Buneman: Semistructured Data. PODS 1997: 117-121

[Cat93]

R. G. G. Cattell: The Object Database Standard: ODMG-93. Morgan Kaufmann 1993, ISBN 1-55860-302-6

[CGH+94]

Sudarshan S. Chawathe, Hector Garcia-Molina, Joachim Hammer, Kelly Ireland, Yannis Papakonstantinou, Jeffrey D. Ullman, Jennifer Widom: The TSIMMIS Project: Integration of Heterogeneous Information Sources. IPSJ 1994: 7-18

[CGL+96]

Latha S. Colby, Timothy Griffin, Leonid Libkin, Inderpal Singh Mumick, Howard Trickey: Algorithms for Deferred View Maintenance. SIGMOD Conference 1996: 469-480

[CH+95a]

Michael J. Carey, Laura M. Haas, Peter M. Schwarz, Manish Arya, William F. Cody, Ronald Fagin, Myron Flickner, Allen Luniewski, Wayne Niblack, Dragutin Petkovic, Joachim Thomas II, John H. Williams, Edward L. Wimmers: Towards Heterogeneous Multimedia Information Systems: The Garlic Approach. RIDE-DOM 1995: 124-131

[CH95b]

Ti-Pin Chang, Richard Hull: Using Witness Generators to Support Bi-directional Update Between Object-Based Databases. PODS 1995: 196-207

[CKW89]

Weidong Chen, Michael Kifer, David Scott Warren: HiLog: A First-Order Semantics for Higher-Order Logic Programming Constructs. NACLP 1989: 1090-1114

[CR90]

Panos K. Chrysanthis, Krithi Ramamritham: ACTA: A Framework for Specifying and Reasoning about Transaction Structure and Behavior. SIGMOD Conference 1990: 194-203

[CW91]

Stefano Ceri, Jennifer Widom: Deriving Production Rules for Incremental View Maintenance. VLDB 1991: 577-589

[CW92]

...

[CW93]

Stefano Ceri, Jennifer Widom: Managing Semantic Heterogeneity with Production Rules and Persistent Queues. VLDB 1993: 108-119

[Dat95]

C. J. Date: An Introduction to Database Systems, 6th Edition. Addison-Wesley 1995, ISBN 0-201-82458-2

[Day89]

Umeshwar Dayal: Queries and Views in an Object-Oriented Data Model. DBPL 1989: 80-102

[DD93]

C. J. Date, Hugh Darwen: A Guide to SQL Standard, 3rd Edition. Addison-Wesley 1993, ISBN 0-201-55822-X

[DH84]

Umeshwar Dayal, Hai-Yann Hwang: View Definition and Generalization for Database Integration in a Multidatabase System. IEEE Trans. Software Eng. 10(6): 628-645(1984)

[DHL91]

Umeshwar Dayal, Meichun Hsu, Rivka Ladin: A Transactional Model for Long-Running Activities. VLDB 1991: 113-122

[DHR96]

Michael Doherty, Richard Hull, Mohammed Rupawalla: Structures for Manipulating Proposed Updates in Object-Oriented Databases. SIGMOD Conference 1996: 306-317

[Ell79]

...

[ELM95]

...

[Fag82]

Ronald Fagin: Horn clauses and database dependencies. J. ACM 29(4): 952-985(1982)

[Fag96]

Ronald Fagin: Combining Fuzzy Information from Multiple Systems. PODS 1996: 216-226

[FFP96]

...

[FFR96]

...

[FHMS91]

...

[Gen91]

Michael R. Genesereth: Knowledge Interchange Format. KR 1991: 599-600

[GHJ96]

Shahram Ghandeharizadeh, Richard Hull, Dean Jacobs: Heraclitus: Elevating Deltas to be First-Class Citizens in a Database Programming Language. ACM Trans. Database Syst. 21(3): 370-426(1996)

[GHS95]

Dimitrios Georgakopoulos, Mark F. Hornick, Amit P. Sheth: An Overview of Workflow Management: From Process Modeling to Workflow Automation Infrastructure. Distributed and Parallel Databases 3(2): 119-153(1995)

[GJM96]

Ashish Gupta, H. V. Jagadish, Inderpal Singh Mumick: Data Integration using Self-Maintainable Views. EDBT 1996: 140-144

[GK94]

Michael R. Genesereth, Steven P. Ketchpel: Software Agents. Commun. ACM 37(7): 48-53(1994)

[GL95]

Timothy Griffin, Leonid Libkin: Incremental Maintenance of Views with Duplicates. SIGMOD Conference 1995: 328-339

[GLS96]

Marc Gyssens, Laks V. S. Lakshmanan, Iyer N. Subramanian: Tables as a Paradigm for Querying and Restructuring. PODS 1996: 93-103

[GMS93]

Ashish Gupta, Inderpal Singh Mumick, V. S. Subrahmanian: Maintaining Views Incrementally. SIGMOD Conference 1993: 157-166

[Gru93]

...

[GSS94]

...

[Gun92]

Carl A. Gunter: The Mixed Powerdomain. Theor. Comput. Sci. 103(2): 311-334(1992)

[Gup89]

...

[GZ82]

Seymour Ginsburg, Sami Mohammed Zaiddan: Properties of functional-dependency families. J. ACM 29(3): 678-698(1982)

[HBG+97]

Joachim Hammer, Hector Garcia-Molina, Svetlozar Nestorov, Ramana Yerneni, Markus M. Breunig, Vasilis Vassalos: Template-Based Wrappers in the TSIMMIS System. SIGMOD Conference 1997: 532-535

[HM85]

Dennis Heimbigner, Dennis McLeod: A Federated Architecture for Information Management. ACM Trans. Inf. Syst. 3(3): 253-278(1985)

[HM93]

Joachim Hammer, Dennis McLeod: An Approach to Resolving Semantic Heterogenity in a Federation of Autonomous, Heterogeneous Database Systems. Int. J. Cooperative Inf. Syst. 2(1): 51-83(1993)

[HS91]

Meichun Hsu, Abraham Silberschatz: Unilateral Commit: A New Paradigm for Reliable Distributed Transaction Processing. ICDE 1991: 286-293

[HS93]

Richard Hull, Jianwen Su: Algebraic and Calculus Query Languages for Recursively Typed Complex Objects. J. Comput. Syst. Sci. 47(1): 121-156(1993)

[Hul84]

Richard Hull: Finitely Specifiable Implicational Dependency Families. J. ACM 31(2): 210-226(1984)

[Hul86]

Richard Hull: Relative Information Capacity of Simple Relational Database Schemata. SIAM J. Comput. 15(3): 856-886(1986)

[HY84]

Richard Hull, Chee-Keng Yap: The Format Model: A Theory of database Organization. J. ACM 31(3): 518-544(1984)

[HY90]

Richard Hull, Masatoshi Yoshikawa: ILOG: Declarative Creation and Manipulation of Object Identifiers. VLDB 1990: 455-468

[HZ96]

Richard Hull, Gang Zhou: A Framework for Supporting Data Integration Using the Materialized and Virtual Approaches. SIGMOD Conference 1996: 481-492

[I3-95]

...

[IK93]

...

[JK84]

David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies. J. Comput. Syst. Sci. 28(1): 167-189(1984)

[KAAK93]

William Kent, Rafi Ahmed, Joseph Albert, Mohammad A. Ketabchi, Ming-Chien Shan: Object Identification in Multidatabase Systems. DS-5 1992: 313-330

[Kai95]

...

[Kal93]

Leonid A. Kalinichenko: A Declarative Framework for Capturing Dynamic Behaviour in Heterogeneous Interoperable Information Resource Environment. RIDE-IMS 1993: 249-252

[KCGS95]

...

[Kel86]

Arthur M. Keller: The Role of Semantics in Translating View Updates. IEEE Computer 19(1): 63-73(1986)

[KH96]

Daniel Kuokka, Larry Harada: Integrating Information via Matchmaking. J. Intell. Inf. Syst. 6(2/3): 261-279(1996)

[Kim95]

Won Kim (Ed.): Modern Database Systems: The Object Model, Interoperability, and Beyond. ACM Press and Addison-Wesley 1995, ISBN 0-201-59098-0
Contents

[KK95]

...

[KKS92]

Michael Kifer, Won Kim, Yehoshua Sagiv: Querying Object-Oriented Databases. SIGMOD Conference 1992: 393-402

[KS91]

...

[Lib95]

Leonid Libkin: Approximation in Databases. ICDT 1995: 411-424

[LMR90]

Witold Litwin, Leo Mark, Nick Roussopoulos: Interoperability of Multiple Autonomous Databases. ACM Comput. Surv. 22(3): 267-293(1990)

[LMSS95a]

Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104

[LMSS95b]

James J. Lu, Guido Moerkotte, Joachim Schü, V. S. Subrahmanian: Efficient Maintenance of Materialized Mediated Views. SIGMOD Conference 1995: 340-351

[LRO96]

Alon Y. Levy, Anand Rajaraman, Joann J. Ordille: Querying Heterogeneous Information Sources Using Source Descriptions. VLDB 1996: 251-262

[LRU96]

Alon Y. Levy, Anand Rajaraman, Jeffrey D. Ullman: Answering Queries Using Limited External Processors. PODS 1996: 227-237

[MAGK95]

C. Mohan, Gustavo Alonso, Roger Günthör, Mohan Kamath: Exotica: A Research Perspective ob Workflow Management Systems. IEEE Data Eng. Bull. 18(1): 19-26(1995)

[MFO90]

Donald P. McKay, Timothy W. Finin, Anthony B. O'Hare: The Intelligent Database Interface: Integrating AI and Database Systems. AAAI 1990: 677-684

[MIR93]

Renée J. Miller, Yannis E. Ioannidis, Raghu Ramakrishnan: The Use of Information Capacity in Schema Integration and Translation. VLDB 1993: 120-133

[MIR94]

Renée J. Miller, Yannis E. Ioannidis, Raghu Ramakrishnan: Schema equivalence in heterogeneous systems: bridging theory and practice. Inf. Syst. 19(1): 3-31(1994)

[MR92]

...

[MS92]

Victor M. Markowitz, Arie Shoshani: Representing Extended Entity-Relationship Structures in Relational Databases: A Modular Approach. ACM Trans. Database Syst. 17(3): 423-464(1992)

[MWF92]

...

[MY95]

...

[OMG]

...

[PFPS+92]

Ramesh S. Patil, Richard Fikes, Peter F. Patel-Schneider, Donald P. McKay, Timothy W. Finin, Thomas R. Gruber, Robert Neches: The DARPA Knowledge Sharing Effort: A Progress Report. KR 1992: 777-788

[PKH88]

Calton Pu, Gail E. Kaiser, Norman C. Hutchinson: Split-Transactions for Open-Ended Activities. VLDB 1988: 26-37

[Rei84]

...

[Ros92]

Kenneth A. Ross: Relations with Relation Names as Arguments: Algebra and Calculus. PODS 1992: 346-353

[RPR89]

...

[RR93]

G. Ramalingam, Thomas W. Reps: A Categorized Bibliography on Incremental Computation. POPL 1993: 502-510

[RS95]

...

[RSK91]

Marek Rusinkiewicz, Amit P. Sheth, George Karabatis: Specifying Interdatabase Dependencies in a Multidatabase Environment. IEEE Computer 24(12): 46-53(1991)

[RSS96]

Kenneth A. Ross, Divesh Srivastava, S. Sudarshan: Materialized View Maintenance and Integrity Constraint Checking: Trading Space for Time. SIGMOD Conference 1996: 447-458

[SA95]

...

[SAL+96]

Michael Stonebraker, Paul M. Aoki, Witold Litwin, Avi Pfeffer, Adam Sah, Jeff Sidell, Carl Staelin, Andrew Yu: Mariposa: A Wide-Area Distributed Database System. VLDB J. 5(1): 48-63(1996)

[SAP97]

...

[SK95]

...

[SL90]

Amit P. Sheth, James A. Larson: Federated Database Systems for Managing Distributed, Heterogeneous, and Autonomous Databases. ACM Comput. Surv. 22(3): 183-236(1990)

[Sta95]

Doug Stacey: Replication: DB2, Oracle, or Sybase? SIGMOD Record 24(4): 95-101(1995)

[Suc96]

Dan Suciu: Query Decomposition and View Maintenance for Query Languages for Unstructured Data. VLDB 1996: 227-238

[Syb97]

...

[T+90]

Gomer Thomas, Glenn R. Thompson, Chin-Wan Chung, Edward Barkmeyer, Fred Carter, Marjorie Templeton, Stephen Fox, Berl Hartman: Heterogeneous Distributed Database Systems for Production Use. ACM Comput. Surv. 22(3): 237-266(1990)

[TBC+87]

...

[Tho95]

...

[Ull88]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents

[Ull97]

Jeffrey D. Ullman: Information Integration Using Logical Views. ICDT 1997: 19-40

[VGV93]

Jan Van den Bussche, Dirk Van Gucht, Gottfried Vossen: Reflective Programming in the Relational Algebra. PODS 1993: 17-25

[WAC+93]

Darrell Woelk, Paul C. Attie, Philip Cannata, Greg Meredith, Amit P. Sheth, Munindar P. Singh, Christine Tomlinson: Task Scheduling Using Intertask Dependencies in Carot. SIGMOD Conference 1993: 491-494

[WCH+93]

Darrell Woelk, Philip Cannata, Michael N. Huhns, Wei-Min Shen, Christine Tomlinson: Using Carnot for Enterprise Information Integration (Synopsis). PDIS 1993: 133-136

[WHW89]

...

[WHW90]

Surjatini Widjojo, Richard Hull, Dave Wile: A Specificational Approach to Merging Persistent Object Bases. POS 1990: 267-278

[Wie92]

Gio Wiederhold: Mediators in the Architecture of Future Information Systems. IEEE Computer 25(3): 38-49(1992)

[Wie96a]

Gio Wiederhold: Intelligent Integration of Information - Foreword. J. Intell. Inf. Syst. 6(2/3): 93-98(1996)

[Wie96b]

Gio Wiederhold: Glossary: Intelligent Integration of Information. J. Intell. Inf. Syst. 6(2/3): 281-291(1996)

[WW97]

Dirk Wodtke, Gerhard Weikum: A Formal Foundation for Distributed Workflow Execution Based on State Charts. ICDT 1997: 230-246

[WWWD96]

Dirk Wodtke, Jeanine Weißenfels, Gerhard Weikum, Angelika Kotz Dittrich: The Mentor Project: Steps Toward Enterprise-Wide Workflow Management. ICDE 1996: 556-565

[ZGHW95]

Yue Zhuge, Hector Garcia-Molina, Joachim Hammer, Jennifer Widom: View Maintenance in a Warehousing Environment. SIGMOD Conference 1995: 316-327

[ZHK96]

Gang Zhou, Richard Hull, Roger King: Generating Data Integration Mediators that Use Materialization. J. Intell. Inf. Syst. 6(2/3): 199-221(1996)

Referenced by

1. Sonia Bergamaschi, Silvana Castano, Maurizio Vincini: Semantic Integration of Semistructured and Structured Data Sources. SIGMOD Record 28(1): 54-59(1999)
2. Xun Cheng, Guozhu Dong, Tzekwan Lau, Jianwen Su: Data Integration by Describing Sources with Constraint Databases. ICDE 1999: 374-381
3. Vânia Maria Ponte Vidal, Bernadette Farias Lóscio: Solving the Problem of Semantic Heterogeneity in Defining Mediator Update Translators. ER 1999: 293-308
4. Peter McBrien, Alexandra Poulovassilis: Automatic Migration and Wrapping of Database Applications - A Schema Transformation Approach. ER 1999: 96-113
5. Daniela Florescu, Alon Y. Levy, Alberto O. Mendelzon: Database Techniques for the World-Wide Web: A Survey. SIGMOD Record 27(3): 59-74(1998)
6. Renée J. Miller: Using Schematically Heterogeneous Structures. SIGMOD Conference 1998: 189-200
7. Mary F. Fernández, Daniela Florescu, Jaewoo Kang, Alon Y. Levy, Dan Suciu: Catching the Boat with Strudel: Experiences with a Web-Site Management System. SIGMOD Conference 1998: 414-425
8. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini: On the Decidability of Query Containment under Constraints. PODS 1998: 149-158
9. Judith Bayard Cushing, Justin Laird, Emir Pasalic, Elizabeth Kutter, Tim Hunkapiller, Frank Zucker, David P. Yee: Beyond Interoperability - Tracking and Managing the Results of Computational Applications. SSDBM 1997: 223-236

Last update Fri May 25 08:32:50 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page