
COMPUTER ENGINEERING
1999 25 12 vol.25 No.12 1999



ֲʽݿݺͲķ
ʯɡܶ
ֲʽݿĿΪЧ֯зֲڲͬվݣڷֲʽݿȫָϵģʽɼƬΣÿƬϵͳпܾмÿڲͬĽڵ㣬ֲʽݿйؼݺͲķ䣬ݵķ䶨ʲôݴʲôڵ㣬䶨ﱻִУݷͲ䲻Ƕ⣬ͬʱĿǰһЩֲʽݿģͣЩģеļȫӵ绷еļ绷ļĽڵ㶼һ[1]þ̬Ͷ̬ʽ㷨˷ֲʽݿݵķ䣬ûпǸ²Ͳпƣ[2]ģȷֽѯɲѯȻļͲѯڵ㣬ϵͳģ͹ڼ򵥣[3]չ[2]Ĺļĸϵͳģͽ[2]ƣҪչ[3]Ĺһʵõķֲʽݿģ͡
1 ݷͲ
ڷֲʽݿģ֪ΪȫֹϵģʽͲѯָ(ûѯ͸Ҫ)ֲʽݿģ͵ĽΪơݷ䡢;ֲݿƣƹɽĻ֪ͨ˴۾ֲݿƣ˷ֲʽݿģ֪ȫֹϵģʽѯָƣΪݷ䣬䡣
ѯָ
class CQuery{CString m_query_idѯ 
CString m_typeѯ()
CString m_originates_note_idѯĽڵ
int m_frequenceòѯƵ};
(ڵ)
class CNode{CString m_node_idڵ
int m_CPU_capacityCPU
int m_unit_CPU_costλCPU
int m_I/O_capacityI/O
int m_unit_I/O_costλI/O
int m_storage_capacity
int m_unit_storage_costλ};
class CLink{CString m_node_id1ڵ1
CString m_node_id2ڵ2
int m_speedٶ int m_capacity
int m_unit_cost λ }
ȫֹϵģʽΪR1R2...RtѯָΪCQuery Q1Q2...QsڵCNode N1N2...NnֲʽݿƷΪȷѯָȫָģʽֶΣȻÿһѯֽɷֶϵļ򵥲ѯʹģ͵õϵͳ͵ݷͲ䡣
1.1 ȫֹϵֶμ
һϵrֶΪr1r2...rnЩֶΰ㹻ϢعϵrϵֶΰˮƽֶκʹֱֶΣˮƽֶαΪȫֹϵģʽϵһѡPΪνʣֶriɱʾΪri=p(r)ǿùϵrзֶεĲعϵrֱֶ漰ϵģʽԵӼ R1R2...RnR=R1R2...Rn ÿһֶοɱʾΪ
ri=Ri(r)
ǿùϵrзֶεȻعϵrڷֲʽݿģпòѯָȫֹϵзֶΣֶεԭǾʹֲԼͨſ
磺ϵͳȫָģʽAccount(branch-name,account-number,customer_id,balance) customer(customer_id,customer_name
,customer_address,city)
ϵͳ3վ㣺ܲHQ͵AB
ѯָУQ1SELECT branch-name,account-number,balance
FROM Account
WHERE branch-name=Q2,SELECT customer_id,customer_name,account-number,balance
FROM Account,customer
WHERE Account.customer_id=customer.customer_id
AND account-number=[specified]
òѯָQ1A͵BԽȫֹϵAccountֶΪA1=branch-name=A(Account)
A2=branch-name=B(Account)
ͬϿòѯָQ2A͵BȫֹϵcustomerֶΪC1C2
ֶεĸƣֶθƼݷָϵһϵվ㣬߿ɻԡɿԺͲԣ˸²ĸԣԸķֶκվڲͬĸƲԣֶθƱʾΪX=(xij)xijʾֶεķiֶδ洢ڵjڵxij=1xij=0зֶθƵӣA1HQABA2BC1HQABC2BǵĿ֮һѰŵķֶθƲԣݷ䡣
1.2 ѯֽͲֽ
ֶθƲȷ󣬲ѯָȴӸѡִвѯĸȻֽѯָΪѡ񸱱ϵļ򵥲ѯ漰ֶεΪĲѯɷֽΪ²
1)һֶεĽڵ㷢ϢԻö2)ڵһִֶвѯҪѡͶӰ3)ڶֶεĽڵ㷢ϢԻö4)ڵڶִֶвѯҪѡͶӰ5)ʹӻ2)4)вݽ6)ͽѯڵ㡣
2PLһ²ɷֽΪ²
1)÷ֶεĸнڵ㷢Ϣ2)ܸȷϢ3)͸ݵнڵ㣬4)ִоֲ²5)ÿһڵܸȷϢ6)ÿһڵ㷢ͷϢ
ѯֽĲѯ
class CQuery_Step{CString m_query_id;ѯ
CString m_step_no;ѯ
CString m_opration;};
磺ڲѯָQ2ڽڵ1ļڵ2ϵĹ˿͵Ĳѯ丱ѡͲѯֽԼڽڵѡԲ²ԣC2ӽڵ2A2ӽڵ2SelectProjectڽڵ2SelectProjectCombineڽڵ2ڵ1Final stepڽڵ1ѯѡĸԱʾΪZ=(zkij)zkijʾѯʹõĸkѯʹôڵjڵĵiֶΣzkij=1zkij=0ԱʾΪY=(ykmj)ykmjʾѯһڵִУkѯĵmڵjڵִУykmj=1ykmj=0
2 ģ
ԸķֶθƲԣXԼĸѡͲѡ񣬼ZYȷϵͳõļ㹫ʽ[3]ѡĿʹϵͳðͨŷáI/OCPUͣϵͳΪ
Cost=kjf(k,j)m(COM(k,j,m)+IO(k,j,m)+CPU(k,j,m))+tSTO(t)
˴f(kj)ʾÿһλʱڽڵjĵkѯƵʣCOM(k,j,m),IO(k,j,m),CPU(k,j,m)ֱʾڽڵjĵkѯĵmͨŷãI/OCPUʱ䣬STO(t)ʾÿһλʱڽڵtĴã[3]ÿһȷݷͲ䣬XYZԼϵͳCostCostXYZĺڵĴI/OCPUʹԼͨ£XYZʹϵͳС㷽Բʽ㷨[1]ݻ㷨[3]
3 
˷ֲʽݿȫָģʽķֶκͷֶθķԼѯԸѡͲڵѡĿǵõŵݷͲģͣʹϵͳðͨŷáI/OCPUͣģͶʵʵķֲʽݿƾָ壬ģͿԽһչ԰ͨŶӳٺ;ֲݿ
ߵλ人ˮѧѧϵ人430072
ο
1 Apers P M G.Data Allocation in Distributed Database System. ACM Trans. on Database Systems,1988,13(3):263-304
2 Cornell D W. Yu P S. On Optimal Site Assignment for Relations in the Distributed Database Environment. IEEE Trans. on Soft- ware Engineering,1989,15(8):1004-1009
3 March S T,Rho S.Allocating Data and Operations to Nodes in Distributed Database Design.IEEE Trans.Knowl Data Eng.,1995, 7(2):305-316
