Re: Distributed Join

mehmet@cs.umd.edu (Mehmet Bayraktar) wrote: > > Tan Kah Hong <sookee@merlion.singnet.com.sg> wrote: > >Hi, > > > >I am in a project where we are developing a distributed application. We are > >using sybase and dbTools++ to interact with Sybase. It has come to a > >point that I need to do some joins which will go across tables in > >different databases. ie. Distributed Joins. > > I assume by different databases, you also meant "they are at different sites, > too.". Otherwise semi-join does not make much sense since semi-joins try > to reduce the transmission costs associated with the join. > > > > >I just want to know whether anyone there has code to perform distributed > >join. If so, can anyone send me that? Or do anyone know about any > >location from where I can get code for joins across databases. > > > >I know performing distributed join is quite complex. I heard about a > >concept called Semi-Join. I would be happy if anybody can mail me code > >or documentation on Joins. > > Semi-joins are very easy to implement within a DBMS using SQL join stmts. > I will present the semi-join algorithm and then how to implement it with an > example. > > Algorithm: > ========== > Semi-join algorithm of R1 _semijoin_ R2 on join attribute a: > 1- Do the projection of R2.a, call this R2' > 2- Do the join of R1.a and R2'.a, call this R1' > > Join algorithm of R1 _join_ R2 via the above semijoin: > 1- Do the join of R1'.a and R2.a and take only the output attributes. > > > Example: > ======== > Assume we have relation R at site 1 and relation S at site 2. > R has the following attributes: a,b, and c. > S has the following attributes: x,y, and z. > > > Assume we want the results of R _join_ S on a==x at site 3. > > The way to get the results of this join via a R _semi-join_ S is as follows: > 1- Take the projection of S.x on site 2 > 2- Ship the resulting one-column table, S', to site 1 > 3- Do R _join_ S', call this R', at site 1 > 4- Ship R' to site 3 > 5- Ship S to site 3 > 6- Do R' _join_ S, call this the result. > > > I will show how I would do this with Informix (since I am familiar with it): > I am at site 3, and all the DBMS engines are of the same type, ie all Informix > engines, no Sybase, to simplify communications protocol. > Query SELECT a,c, x,y FROM R, S WHERE R.a = S.x > Table names in Informix has the following syntax: > database@dbservername.owner.table > > A- SELECT DISTINCT x FROM db@site2.mehmet.S > INTO db@site2.mehmet.S' > B- SELECT x,y FROM db@site1.mehmet.R table_R, db@site2.mehmet.S' table_S' > INTO db@site3.mehmet.R' > WHERE table_R.a = table_S'.x > C- SELECT a,c, x,y FROM db@site3.mehmet.R' table_R', db@site2.mehmet.S table_S > INTO db@site3.mehmet.result > WHERE table_R'.a = table_S.x > > Step A performs step_1. Step B performs step_2, step_3, and step_4. > Step C performs step_5 and step_6. > > The above steps assume that DBMS performs ship-whole relation and then does > the joins. If that is not the case. you need to break your steps into smaller. > Ie Step-B can be rewritten as follows: > B1- SELECT * FROM db@site2.mehmet.S' > INTO db@site1.mehmet.S' > B2- SELECT x,y FROM db@site1.mehmet.R table_R, db@site1.mehmet.S' table_S' > INTO db@site1.mehmet.R' > WHERE table_R.a = table_S'.x > B3- SELECT * FROM db@site1.mehmet.R' > INTO db@site3.mehmet.R' > > > > Of course semi-joins are useful if they are cost effective. > Ie if the cost of transferring the semijoin attrs is less than the cost of > transferring irrelevant tuples of R. So a carefull analysis is beneficial. > > An alternative plan to the above could have been R _join_ S via S _semijoin_ R. > > For more info, you might consult to Tamer Ozsu's Distributed Databases book. > > -mehmet > > > ---- > Mehmet Bayraktar > mehmet@cs.umd.edu > > Graduate Student 1112 Dunoon Rd. > Computer Science Dept. Silver Spring, MD 20903 > University of Maryland Phone: (301) 434-9290 > College Park, MD 20742 > > > > >Please mail me the information to this account or to the e-mail address > >jijo%istc206a04%st@singtel.com > > > >Thanks, > >Joe > >Jijo G John > > > >(Work) (Singapore - 65) 462-3575 > >(Home) (Singapore - 65) 365-8094 > >(Fax) (Singapore - 65) 467-9106 > > To be this convoluted there HAS to be something VERY wrong at the lowest level of design. i.e. the underlying RDBMS Thank heavens I work in Pick!!!!!! Gary Curtis