Re: Distributed Join

Mehmet Bayraktar (mehmet@cs.umd.edu) 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 You can get the code to do distributed joins from Sybase! Their product offers you several different methods for doing what you want. Dave Roberts