Query processing in heterogeneous distributed database management systems

dc.contributor.authorBhasker, Bharaten
dc.contributor.committeechairEgyhazy, Csaba J.en
dc.contributor.committeememberHaddad, Emile K.en
dc.contributor.committeememberTriantis, Konstantinos P.en
dc.contributor.committeememberHartson, H. Rexen
dc.contributor.committeememberRicci, Fred J.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2014-03-14T21:19:10Zen
dc.date.adate2005-09-20en
dc.date.available2014-03-14T21:19:10Zen
dc.date.issued1992-06-06en
dc.date.rdate2005-09-20en
dc.date.sdate2005-09-20en
dc.description.abstractThe goal of this work is to present an advanced query processing algorithm formulated and developed in support of heterogeneous distributed database management systems. Heterogeneous distributed database management systems view the integrated data through an uniform global schema. The query processing algorithm described here produces an inexpensive strategy for a query expressed over the global schema. The research addresses the following aspects of query processing: (1) Formulation of a low level query language to express the fundamental heterogeneous database operations; (2) Translation of the query expressed over the global schema to an equivalent query expressed over a conceptual schema; (3) An estimation methodology to derive the intermediate result sizes of the database operations; (4) A query decomposition algorithm to generate an efficient sequence of the basic database operations to answer the query. This research addressed the first issue by developing an algebraic query language called cluster algebra. The cluster algebra consists of the following operations: (a) Selection, union, intersection and difference, which are extensions of their relational algebraic counterparts to heterogeneous databases; (b) Normal-join and normal-projection which replace their counterparts, join and projection, in the relational algebra; (c) Two new operators embed and unembed to restructure the database schema. The second issue of the query translation was addressed by development of an algorithm that translates a cluster algebra query expressed over the virtual views to an equivalent cluster algebra query expressed over the conceptual databases. A non-parametric estimation methodology to estimate the result size of a cluster algebra operation was developed to address the third issue described above. Finally, this research developed a query decomposition algorithm, applicable to the relational and non-relational databases, that decomposes a query by computing all profitable semi-join operations, followed by the determination of the best sequence of join operations per processing site. The join optimization is performed by formulating a zero-one integer linear program that uses the non-parametric estimation technique to compute the sizes of intermediate results. The query processing algorithm was implemented in the context of DAVID, a heterogeneous distributed database management system.en
dc.description.degreePh. D.en
dc.format.extentvi, 224 leavesen
dc.format.mediumBTDen
dc.format.mimetypeapplication/pdfen
dc.identifier.otheretd-09202005-091021en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-09202005-091021/en
dc.identifier.urihttp://hdl.handle.net/10919/39437en
dc.language.isoenen
dc.publisherVirginia Techen
dc.relation.haspartLD5655.V856_1992.B424.pdfen
dc.relation.isformatofOCLC# 26554378en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.lccLD5655.V856 1992.B424en
dc.subject.lcshDatabase managementen
dc.subject.lcshDistributed databasesen
dc.titleQuery processing in heterogeneous distributed database management systemsen
dc.typeDissertationen
dc.type.dcmitypeTexten
thesis.degree.disciplineComputer Scienceen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.leveldoctoralen
thesis.degree.namePh. D.en

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
LD5655.V856_1992.B424.pdf
Size:
7.2 MB
Format:
Adobe Portable Document Format