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

@inproceedings{DBLP:conf/vldb/WangM90,
  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, http://dblp.uni-trier.de}
}

Abstract

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

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb8997 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[1]

Serge Abiteboul, Richard Hull: IFO: A Formal Semantic Database Model. ACM Trans. Database Syst. 12(4): 525-565(1987) BibTeX

[2]

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

[3]

Paolo Atzeni, Peter P. Chen: Completeness of Query Languages for the Entity-Relationship Model. ER 1981: 109-122 BibTeX

[4]

...

[5]

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

[6]

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

[7]

David Brill, Marjorie Templeton, Clement T. Yu: Distributed Query Processing Strategies in Mermaid, A Frontend to Data Management Systems. ICDE 1984: 211-218 BibTeX

[8]

...

[9]

Marco A. Casanova, Vânia Maria Ponte Vidal: Towards a Sound View Integration Methodology. PODS 1983: 36-47 BibTeX

[10]

...

[11]

Stefano Ceri, Giuseppe Pelagatti: Distributed Databases: Principles and Systems. McGraw-Hill Book Company 1984, ISBN 0-07-010829-3
BibTeX

[12]

Peter P. Chen: A Preliminary Framework for Entity-Relationship Models. ER 1981: 19-28 BibTeX

[13]

Peter P. Chen: An Algebra for a Directional Binary Entity-Relationship Model. ICDE 1984: 37-40 BibTeX

[14]

Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976) BibTeX

[15]

...

[16]

E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX

[17]

E. F. Codd: An Evaluation Scheme for Database Management Systems that are claimed to be Relational. ICDE 1986: 720-729 BibTeX

[18]

E. F. Codd: Extending the Database Relational Model to Capture More Meaning. ACM Trans. Database Syst. 4(4): 397-434(1979) BibTeX

[19]

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

[20]

...

[21]

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

[22]

C. J. Date: The Outer Join. ICOD 1983: 76-106 BibTeX

[23]

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

[24]

Umeshwar Dayal: Processing Queries Over Generalization Hierarchies in a Multidatabase System. VLDB 1983: 342-353 BibTeX

[25]

...

[26]

S. Misbah Deen, R. R. Amin, Malcolm C. Taylor: Data Integration in Distributed Databases. IEEE Trans. Software Eng. 13(7): 860-864(1987) BibTeX

[27]

S. Misbah Deen, R. R. Amin, Malcolm C. Taylor: Implementation of a Prototype for PRECI. Comput. J. 30(2): 157-162(1987) BibTeX

[28]

Linda G. DeMichiel: Performing Operations over Mismatched Domains. ICDE 1989: 36-45 BibTeX

[29]

...

[30]

...

[31]

Clesio Saraiva dos Santos, Erich J. Neuhold, Antonio L. Furtado: A Data Type Approach to the Entity-Relationship Approach. ER 1979: 103-119 BibTeX

[32]

...

[33]

Ramez Elmasri, Gio Wiederhold: GORDAS: A Formal High-Level Query Language for the Entity-Relationship Model. ER 1981: 49-72 BibTeX

[34]

...

[35]

...

[36]

Arlette Ferrier, Christine Stangret: Heterogeneity in the Distributed Database Management System SIRIUS-DELTA. VLDB 1982: 45-53 BibTeX

[37]

...

[38]

...

[39]

...

[40]

...

[41]

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

[42]

Richard Hull, Roger King: Semantic Database Modeling: Survey, Applications, and Research Issues. ACM Comput. Surv. 19(3): 201-260(1987) BibTeX

[43]

Hai-Yann Hwang, Umeshwar Dayal: Using the Entity-Relationship Model for Implementing Multi-Model Database Systems. ER 1981: 235-256 BibTeX

[44]

Blake Ives, Gerard P. Learmonth: The Information System as a Competitive Weapon. Commun. ACM 27(12): 1193-1201(1984) BibTeX

[45]

Randy H. Katz, Nathan Goodman: View Processing in MULTIBASE, A Heterogeneous Database System. ER 1981: 257-277 BibTeX

[46]

...

[47]

Anthony C. Klug: Equivalence of Relational Algebra and Relational Calculus Query Languages Having Aggregate Functions. J. ACM 29(3): 699-717(1982) BibTeX

[48]

Y. Edmund Lien, Jonathan E. Shopiro, Shalom Tsur: DSIS - A Database System with Interrelational Semantics. VLDB 1981: 465-477 BibTeX

[49]

Witold Litwin, Abdelaziz Abdellatif: Multidatabase Interoperability. IEEE Computer 19(12): 10-18(1986) BibTeX

[50]

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

[51]

Peter Lyngbæk, Dennis McLeod: An Approach to Object Sharing in Distributed Datbase Systems. VLDB 1983: 364-375 BibTeX

[52]

...

[53]

...

[54]

Frank Manola, Umeshwar Dayal: PDM: An Object-Oriented Data Model. OODBS 1986: 18-25 BibTeX

[55]

...

[56]

...

[57]

Victor M. Markowitz, Yoav Raz: A Modified Relational Algebra and its Use in an Entity-Relationship Environment. ER 1983: 315-328 BibTeX

[58]

Victor M. Markowitz, Arie Shoshani: Abbreviated Query Interpretation in Extended Entity-Relationship Oriented Databases. ER 1989: 325-343 BibTeX

[59]

Victor M. Markowitz, Arie Shoshani: On the Correctness of Representing Extended Entity-Relationship Structures in the Relational Model. SIGMOD Conference 1989: 430-439 BibTeX

[60]

...

[61]

Shamkant B. Navathe, T. Sashidhar, Ramez Elmasri: Relationship Merging in Schema Integration. VLDB 1984: 78-90 BibTeX

[62]

...

[63]

Christine Parent, Stefano Spaccapietra: An Algebra for a General Entity-Relation1hip Model. IEEE Trans. Software Eng. 11(7): 634-643(1985) BibTeX

[64]

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

[65]

Joan Peckham, Fred J. Maryanski: Semantic Data Models. ACM Comput. Surv. 20(3): 153-189(1988) BibTeX

[66]

...

[67]

Xiaolei Qian, Gio Wiederhold: Knowledge-based Integrity Constraint Validation. VLDB 1986: 3-12 BibTeX

[68]

...

[69]

Marek Rusinkiewicz, Bogdan D. Czejdo: Query Transformation in Heterogeneous Distributed Database Systems. ICDCS 1985: 300-307 BibTeX

[70]

...

[71]

Gail M. Shaw, Stanley B. Zdonik: A Query Algebra for Object-Oriented Databases. ICDE 1990: 154-162 BibTeX

[72]

Gail M. Shaw, Stanley B. Zdonik: Object-Oriented Queries: Equivalence and Optimization. DOOD 1989: 281-295 BibTeX

[73]

...

[74]

David W. Shipman: The Functional Data Model and the Data Language DAPLEX. ACM Trans. Database Syst. 6(1): 140-173(1981) BibTeX

[75]

...

[76]

Michael Stonebraker: Inclusion of New Types in Relational Data Base Systems. ICDE 1986: 262-269 BibTeX

[77]

...

[78]

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

[79]

...

[80]

...

[81]

...

[82]

Y. Richard Wang, Stuart E. Madnick: The Inter-Database Instance Identification Problem in Integrating Autonomous Systems. ICDE 1989: 46-55 BibTeX

[83]

...

[84]

Daniel L. Weller, Bryant W. York: A Relational Representation of an Abstract Type System. IEEE Trans. Software Eng. 10(3): 303-309(1984) BibTeX

[85]

...

[86]

...

[87]

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)