A Polygen Model for Heterogeneous Database Systems: The Source Tagging Perspective.

Y. Richard Wang, Stuart E. Madnick: A Polygen Model for Heterogeneous Database Systems: The Source Tagging Perspective. VLDB 1990: 519-538
  author    = {Y. Richard Wang and
               Stuart E. Madnick},
  editor    = {Dennis McLeod and
               Ron Sacks-Davis and
               Hans-J{\"o}rg Schek},
  title     = {A Polygen Model for Heterogeneous Database Systems: The Source
               Tagging Perspective},
  booktitle = {16th International Conference on Very Large Data Bases, August
               13-16, 1990, Brisbane, Queensland, Australia, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1990},
  isbn      = {1-55860-149-X},
  pages     = {519-538},
  ee        = {db/conf/vldb/WangM90.html},
  crossref  = {DBLP:conf/vldb/90},
  bibsource = {DBLP,}


This paper studies heterogeneous database systems from the multiple (poly) source (gen perspective. It aims at addressing issues such as "where is the data from" and "which intermediate data sources were used to arrive at that data" - issues which are critical to many users in utilizing information composed from multiple sources. Specifically, it presents a polygen model for resolving the Data Source Tagging and Intermediate Source Tagging problems. Secondly, it presents a data-driven query translation mechanism for mapping a polygen query into a set of local queries dynamically. A concrete example is also provided to exemplify polygen query processing.

The significance of this paper lies not only in a precise characterization of a practical problem and a solution per se, but also in the establishment of a foundation for resolving many other critical research issues such as domain mismatch, semantic reconciliation, and data conflict amongst data retrieved fromdifferent sources. In a federated database environment with hundreds of databases, all of these issues are critical to their effective use.

Copyright © 1990 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Dennis McLeod, Ron Sacks-Davis, Hans-Jörg Schek (Eds.): 16th International Conference on Very Large Data Bases, August 13-16, 1990, Brisbane, Queensland, Australia, Proceedings. Morgan Kaufmann 1990, ISBN 1-55860-149-X


Serge Abiteboul, Richard Hull: IFO: A Formal Semantic Database Model. ACM Trans. Database Syst. 12(4): 525-565(1987) BibTeX
Sabah S. Al-Fedaghi, Peter Scheuermann: Mapping Considerations in the Design of Schemas for the Relational Model. IEEE Trans. Software Eng. 7(1): 99-111(1981) BibTeX
Paolo Atzeni, Peter P. Chen: Completeness of Query Languages for the Entity-Relationship Model. ER 1981: 109-122 BibTeX
Carlo Batini, Maurizio Lenzerini, Shamkant B. Navathe: A Comparative Analysis of Methodologies for Database Schema Integration. ACM Comput. Surv. 18(4): 323-364(1986) BibTeX
Yuri Breitbart, Peter L. Olson, Glenn R. Thompson: Database Integration in a Distributed Heterogeneous Database System. ICDE 1986: 301-310 BibTeX
David Brill, Marjorie Templeton, Clement T. Yu: Distributed Query Processing Strategies in Mermaid, A Frontend to Data Management Systems. ICDE 1984: 211-218 BibTeX
Marco A. Casanova, Vânia Maria Ponte Vidal: Towards a Sound View Integration Methodology. PODS 1983: 36-47 BibTeX
Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
Peter P. Chen: A Preliminary Framework for Entity-Relationship Models. ER 1981: 19-28 BibTeX
Peter P. Chen: An Algebra for a Directional Binary Entity-Relationship Model. ICDE 1984: 37-40 BibTeX
Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976) BibTeX
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
E. F. Codd: An Evaluation Scheme for Database Management Systems that are claimed to be Relational. ICDE 1986: 720-729 BibTeX
E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX
E. F. Codd: Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972) BibTeX
Bogdan D. Czejdo, Marek Rusinkiewicz, David W. Embley: An Approach to Schema Integration and Query Formulation in Federated Database Systems. ICDE 1987: 477-484 BibTeX
C. J. Date: The Outer Join. ICOD 1983: 76-106 BibTeX
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) BibTeX
Umeshwar Dayal: Processing Queries Over Generalization Hierarchies in a Multidatabase System. VLDB 1983: 342-353 BibTeX
S. Misbah Deen, R. R. Amin, Malcolm C. Taylor: Data Integration in Distributed Databases. IEEE Trans. Software Eng. 13(7): 860-864(1987) BibTeX
S. Misbah Deen, R. R. Amin, Malcolm C. Taylor: Implementation of a Prototype for PRECI. Comput. J. 30(2): 157-162(1987) BibTeX
Linda G. DeMichiel: Performing Operations over Mismatched Domains. ICDE 1989: 36-45 BibTeX
Clesio Saraiva dos Santos, Erich J. Neuhold, Antonio L. Furtado: A Data Type Approach to the Entity-Relationship Approach. ER 1979: 103-119 BibTeX
Ramez Elmasri, Gio Wiederhold: GORDAS: A Formal High-Level Query Language for the Entity-Relationship Model. ER 1981: 49-72 BibTeX
Arlette Ferrier, Christine Stangret: Heterogeneity in the Distributed Database Management System SIRIUS-DELTA. VLDB 1982: 45-53 BibTeX
Dennis Heimbigner, Dennis McLeod: A Federated Architecture for Information Management. ACM Trans. Inf. Syst. 3(3): 253-278(1985) BibTeX
Richard Hull, Roger King: Semantic Database Modeling: Survey, Applications, and Research Issues. ACM Comput. Surv. 19(3): 201-260(1987) BibTeX
Hai-Yann Hwang, Umeshwar Dayal: Using the Entity-Relationship Model for Implementing Multi-Model Database Systems. ER 1981: 235-256 BibTeX
Blake Ives, Gerard P. Learmonth: The Information System as a Competitive Weapon. Commun. ACM 27(12): 1193-1201(1984) BibTeX
Randy H. Katz, Nathan Goodman: View Processing in MULTIBASE, A Heterogeneous Database System. ER 1981: 257-277 BibTeX
Anthony C. Klug: Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions. J. ACM 29(3): 699-717(1982) BibTeX
Y. Edmund Lien, Jonathan E. Shopiro, Shalom Tsur: DSIS - A Database System with Interrelational Semantics. VLDB 1981: 465-477 BibTeX
Witold Litwin, Abdelaziz Abdellatif: Multidatabase Interoperability. IEEE Computer 19(12): 10-18(1986) BibTeX
Witold Litwin, J. Boudenant, Christian Esculier, Arlette Ferrier, A. M. Glorieux, J. La Chimia, K. Kabbaj, Catherine Moulinoux, P. Rolin, Christine Stangret: SIRIUS System for Distributed Data Management. DDB 1982: 311-366 BibTeX
Peter Lyngbæk, Dennis McLeod: An Approach to Object Sharing in Distributed Datbase Systems. VLDB 1983: 364-375 BibTeX
Frank Manola, Umeshwar Dayal: PDM: An Object-Oriented Data Model. OODBS 1986: 18-25 BibTeX
Victor M. Markowitz, Yoav Raz: A Modified Relational Algebra and its Use in an Entity-Relationship Environment. ER 1983: 315-328 BibTeX
Victor M. Markowitz, Arie Shoshani: Abbreviated Query Interpretation in Extended Entity-Relationship Oriented Databases. ER 1989: 325-343 BibTeX
Victor M. Markowitz, Arie Shoshani: On the Correctness of Representing Extended Entity-Relationship Structures in the Relational Model. SIGMOD Conference 1989: 430-439 BibTeX
Shamkant B. Navathe, T. Sashidhar, Ramez Elmasri: Relationship Merging in Schema Integration. VLDB 1984: 78-90 BibTeX
Christine Parent, Stefano Spaccapietra: An Algebra for a General Entity-Relation1hip Model. IEEE Trans. Software Eng. 11(7): 634-643(1985) BibTeX
Christine Parent, Hélène Rolin, Kokou Yétongnon, Stefano Spaccapietra: An ER Calculus for the Entity-Relationship Complex Model. ER 1989: 361-384 BibTeX
Joan Peckham, Fred J. Maryanski: Semantic Data Models. ACM Comput. Surv. 20(3): 153-189(1988) BibTeX
Xiaolei Qian, Gio Wiederhold: Knowledge-based Integrity Constraint Validation. VLDB 1986: 3-12 BibTeX
Marek Rusinkiewicz, Bogdan D. Czejdo: Query Transformation in Heterogeneous Distributed Database Systems. ICDCS 1985: 300-307 BibTeX
Gail M. Shaw, Stanley B. Zdonik: A Query Algebra for Object-Oriented Databases. ICDE 1990: 154-162 BibTeX
Gail M. Shaw, Stanley B. Zdonik: Object-Oriented Queries: Equivalence and Optimization. DOOD 1989: 281-295 BibTeX
David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) BibTeX
Michael Stonebraker: Inclusion of New Types in Relational Data Base Systems. ICDE 1986: 262-269 BibTeX
Toby J. Teorey, Dongqing Yang, James P. Fry: A Logical Design Methodology for Relational Databases Using the Extended Entity-Relationship Model. ACM Comput. Surv. 18(2): 197-222(1986) BibTeX
Y. Richard Wang, Stuart E. Madnick: The Inter-Database Instance Identification Problem in Integrating Autonomous Systems. ICDE 1989: 46-55 BibTeX
Daniel L. Weller, Bryant W. York: A Relational Representation of an Abstract Type System. IEEE Trans. Software Eng. 10(3): 303-309(1984) BibTeX
Carlo Zaniolo: The Database Language GEM. SIGMOD Conference 1983: 207-218 BibTeX

Referenced by

  1. Ee-Peng Lim, Roger H. L. Chiang: A Global Object Model for Accommodating Instance Heterogeneities. ER 1998: 435-448
  2. César A. Galindo-Legaria, Arnon Rosenthal: Outerjoin Simplification and Reordering for Query Optimization. ACM Trans. Database Syst. 22(1): 43-73(1997)
  3. Stuart E. Madnick: Are We Moving Toward an Information SuperHighway or a Tower of Babel? The Challenge of Large-Scale Semantic Heterogeneity. ICDE 1996: 2-8
  4. Richard Y. Wang, Veda C. Storey, Christopher P. Firth: A Framework for Analysis of Data Quality Research. IEEE Trans. Knowl. Data Eng. 7(4): 623-640(1995)
  5. Stuart E. Madnick: From VLDB to VMLDB (Very MANY Large Data Bases): Dealing with Large-Scale Semantic Heterogenity. VLDB 1995: 11-16
  6. Edward Sciore, Michael Siegel, Arnon Rosenthal: Using Semantic Values to Falilitate Interoperability Among Heterogeneous Information Systems. ACM Trans. Database Syst. 19(2): 254-290(1994)
  7. César A. Galindo-Legaria: Outerjoins as Disjunctions. SIGMOD Conference 1994: 348-358
  8. Stuart E. Madnick: The Voice of the Customer: Innovative and Useful Research Directions (Panel). VLDB 1993: 701-704
  9. Richard Y. Wang, Henry B. Kon, Stuart E. Madnick: Data Quality Requirements Analysis and Modeling. ICDE 1993: 670-677
  10. David K. Hsiao: Federated Databases and Systems: Part I - A Tutorial on Their Data Sharing. VLDB J. 1(1): 127-179(1992)
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings: Copyright © by VLDB Endowment,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:45 2009