Virtual University Pakistan 1 Course Title: Distributed Database Management Systems Course Code: CS712 Instructor: Dr. Nayyer Masood Lecture No: 23& 24 Virtual University Pakistan 2 In previous lecture: - Fragmentation In this lecture: - Reasons for Fragmentation o Maximizes local access o Reduces table size, etc. - PHF using the SQL Server on same machine - Implemented PHF in a Banking Environment Fragmentation • We know there are different types, we start with the simplest one and that is the PHF • Supposedly, you have already gone through the design phase and have got the predicates to be used as basis for PHF, just as a reminder • From the user queries, we first collect the simple predicates and then we form a complete and minimal set of minterm predicates, a minterm predicate is ….., you know that otherwise refer back to lecture 16, 17 • Lets say we go back to our Bank example, and lets say we have decided to place our servers at QTA and PESH so we have two servers where we are going to place our PHFs • As before we register our servers and now at our Enterprise Manager we can see two instances of SS • At each of the three sites we define one database named BANK and also one relation, normal base table, however, for the fragmentations to be disjoint (a correctness requirement) we place a check on each table at three sites, how…. • We name our fragments/local tables as custQTA, custPESH • Each table is defined as create table custPESH(custId char(6), custName varchar(25), custBal number(10,2), custArea char(5)) Virtual University Pakistan 3 • In the same way we create 2 tables one at each of our two sites, meant for containing the local users • Users that fall in that area and the value of the attribute custArea is going to be the area where a customer’s branch is, so its domain is {pesh, qta) • To ensure the disjointness and also to ensure the proper functioning of the system, we apply a check on the tables • The check is • Peshawar customers are allocated from the range C00001 to C50000, likewise • QTA is C50001 to C99999 • So we apply the check on both tables/fragments accordingly, although they can be applied while creating the table, we can also apply them later, like • Alter table custPesh add constraint chkPsh check ((custId between ‘C00001’ and ‘C50000’) and (custArea = ‘Pesh’)) • Alter table custQTA add constraint chkQta check ((custId between ‘C50001’ and ‘C99999’) and (custArea = ‘Qta’)) • Tables have been created on local sites and are ready to be populated, start running applications on them, and data enters the table, and the checks ensure the entry of proper data in each table. Now, the tables are being populated Example Data in PESH C0001 Gul Khan 4593.33 Pesh C0002 Ali Khan 45322.1 Pesh C0003 Gul Bibi 6544.54 Pesh C0005 Jan Khan 9849.44 Pesh Example Data at QTA Virtual University Pakistan 4 C50001 Suhail Gujjar 3593.33 Qta C50002 Kauser Perveen 3322.1 Qta C50003 Arif Jat 16544.5 Qta C50004 Amjad Gul 8889.44 Qta • Next thing is to create a global view for the global access/queries, for this we have to link the servers with each other, this is required • You have already registered both the servers, now to link them • You can link them using Enterprise Manager or alternatively through SQL, we do here using SQL Connect Pesh using Query Analyzer • Then execute the stored procedure sp_addlinkedserver • The syntax is • sp_addlinkedserver @server = ‘QTA', @srvproduct = '', @provider = 'sqloledb', @datasrc = ‘mysystem\QTA‘ • You will get two messages, if successful, like ‘1 row added’ and ‘1 row added’ • You have introduced QTA as a linked server with PESH. • We have to perform this operation on the other server, that is, we have to add linked server PESH at QTA • Setup is there, next thing is to create a partitioned view • In SQL Server, a partitioned view joins horizontally partitioned data across multiple servers • The statement to create the partitioned view is Virtual University Pakistan 5 Create view custG as select * from custPesh Union All select * from QTA.bank.dbo.custQTA • Likewise, we have to apply same command at QTA • Create view custG as select * from custQta Union All select * from PESH.bank.dbo.custPesh • Once it is defined, now when you access data from custG, it gives you data from all four sites. • It is also transparent • Now lets say if you are connected with Pesh, and you give the command Select * from custPesh You get the output • Same is the case with the users of the QTA server, they pose the query Virtual University Pakistan 6 • Select * from custQTA • Like a local user • The previous two examples represent access of a local user, now if the global users, like from Management, want to access data across all sites, they will pose the query against the global view, like • Select * from custG • All this is transparent from the user, that is, the distribution of data • Global user gets the feeling, as if all the users’ data is placed on a single place • For the administrative purposes they can perform analytical types of queries on this global view, like Summary: Virtual University Pakistan 7 We have discussed the fragmentation, maximize local access and reduce table size etc. and also discussed the PHF using the SQL Server on same machine. Virtual University Pakistan 8 Course Title: Distributed Database Management Systems Course Code: CS712 Instructor: Dr. Nayyer Masood Lecture No: 25 Virtual University Pakistan 9 In previous lecture: - Reasons for Fragmentation o Maximizes local access o Reduces table size, etc. - PHF using the SQL Server on same machine - Implemented PHF in a Banking Environment - DDBS layer is superimposed on the client sites - Actual Data resides with the local sites In this lecture: - Derived Horizontal Fragmentation Derived Horizontal Fragmentation • Fragmenting/ partitioning a table based on the constraints defined on another table. • Both tables are linked with each other through Owner-Member relation Scenario a, b, c, d p , q, r, s, a TABLE 1 TABLE 2 Link Owner Member Virtual University Pakistan 10 Why DHF Here • Employee and salary record is split in two tables due to Normalization • Storing all data in EMP table introduces Transitive Dependency • That causes Anomalies PHF of TITLE table • Predicates defined on the sal attribute of TITLE table • p1 = sal > 10000 and sal <= 20000 • p2 = sal > 20000 and sal <= 50000 • p3 = sal > 50000 Conditions for the TITLE Table • TITLE1 = σ (sal > 10000 and SAL ≤30000) (SAL) • TITLE2 = σ (sal > 20000 and SAL ≤50000) (SAL) • TITLE3 = σ (sal > 50000) (SAL) empId, empName, empAdres, titleId titleId, titleName, sal EMP TITLE Link Owne r Membe r Virtual University Pakistan 11 Tables created with constraints • create table TITLE1 (titleID char(3) primary key, titleName char (15), sal int check (SAL between 10000 and 20000)) • create table TITLE2 (titleID char(3) primary key, titleName char (15), sal int check (SAL between 20001 and 50000)) • create table TITLE3 (titleID char(3) primary key, titleName char (15), sal int check (SAL > 50000)) TITLE titleID titleName Sal T01 Elect. Eng 42000 T02 Sys Analyst 64000 T03 Mech. Eng 27000 T04 Programmer 19000 TITLE1 titleID titleName Sal T04 Programmer 19000 TITLE3 titleID titleName Sal T02 Sys Analyst 64000 TITLE2 titleID titleName Sal T01 Elect. Eng 42000 Virtual University Pakistan 12 T03 Mech. Eng 27000 EMP table at local sites create table EMP1 (empId char(5) primary key, empName char(25), empAdres char (30), titleId char(3) foreign key references TITLE1(titleID)) Referential Integrity Constraint • Null value in the EMP1.titleId is allowed • This violates the correctness requirement of the Fragmentation, i.e., it will violating the completeness criterion Tighten Up the Constraint Around • Further we need to impose the “NOT NULL” constraint on the EMP1.titleID • Now the records in EMP1 will strictly adhere to the DHF Revised EMP1 Definition empId, empName, empAdres, titleId titleId, titleName, sal EMP TITLE Link PHF on Owner Member Natural Join with Owner Fragments Virtual University Pakistan 13 create table EMP1 (empId char(5) primary key, empName char(25), empAdres char (30), titleId char(3) foreign key references TITLE1(titleID) not NULL) Defining all three EMP • create table EMP1 (empId char(5) primary key, empName char(25), empAdres char (30), titleId char(3) foreign key references TITLE1(titleID) not NULL) • create table EMP2 (empId char(5) primary key, empName char(25), empAdres char (30), titleId char(3) foreign key references TITLE2(titleID) not NULL) • create table EMP3 (empId char(5) primary key, empName char(25), empAdres char (30), titleId char(3) foreign key references TITLE3(titleID) not NULL) PHF of EMP at different sites • create table EMP1 (empId char(5) primary key check (empId in ('Programmer')), empName char(25), empAdres char (30), titleId char(3)) • create table EMP2 (empId char(5) primary key check (empId in (‘Elect. Engr’,’Mech. Engr’)), empName char(25), empAdres char (30), titleId char(3)) • create table EMP3 (empId char(5) primary key check (empId in (' Sys Analyst ')), empName char(25), empAdres char (30), titleId char(3)) Adding a new record in TITLE titleID titleName Sal T01 Elect. Eng 42000 T02 Sys Analyst 64000 T03 Mech. Eng 27000 Virtual University Pakistan 14 T04 Programmer 19000 T05 Assist Supr 16000 All three predicates of PHF defined in the two slide a couple of slides ago create table EMP1 (empId char(5) primary key check (empId in ('Programmer‘, ‘Assist Supr’)), empName char(25), empAdres char (30), titleId char(3)) Original EMP Table empId empName empAdres titleId E1 T Khan Multan T01 E2 W Shah Islamabad T02 E3 R Dar Islamabad T03 E4 K Muhammad Lahore T04 E5 F Sahbai Lahore T02 E6 A Haq Multan T01 E7 S Farhana Lahore T03 E8 M Daud Jhelum T02 DHFs of EMP Table EMP1 empId empName empAdres titleId E4 K Muhammad Lahore T04 EMP3 empId empName empAdres titleId E2 W Shah Islamabad T02 E5 F Sahbai Lahore T02 E8 M Daud Jhelum T02 EMP2 empId empName empAdres titleId Virtual University Pakistan 15 E1 T Khan Multan T01 E3 R Dar Islamabad T03 E6 A Haq Multan T01 E7 S Farhana Lahore T03 Transactional Replication • Data replicated as the transaction executes • Preferred in higher bandwidth and lower latency • Transaction is replicated as it is executed • Begins with a snapshot, changes sent at subscribers as they occur or at timed intervals • A special Type allows changes at subscribers From the Enterprise Manager, select Replication, after a couple of nexts, we get this screen Virtual University Pakistan 16 Virtual University Pakistan 17 Publication has been created that can be viewed from Replication Monitor or from Replication, like this Virtual University Pakistan 18 It has also created snapshot and log reader agents, which won’t work until we create a subscription. For this, we select the publication from replication monitor, right click it, and then select Push new subscription. You select the particular database where you want to subscribe, we have created a new one. Virtual University Pakistan 19 A couple of more nexts and then Virtual University Pakistan 20 After this we run the snapshot agent, that creates a snapshot, you can verify this from snapshot agent history, or you can go to subscriber database and have a look, like this We delete a record from our publication and we see that it is expressed in Virtual University Pakistan 21 This will be automatically being transferred to Subscription. If this activity could not be performed on subscriber, then the replication monitor will generate an error. You have to trap it and tune your application. Merge Replication From replication, start a new publication, a few next, and once again our old familiar screen. After a few next, the merge publication will be created. Virtual University Pakistan 22 Now you execute the snapshot agent of this replication. It will create the snapshot, and then you subscribe a database. We find the original data in the subscriber After this if we make any change on either side, it will be reflected on the other side. In case of merge replication, we have to be careful about the constraints, like Primary Key, or other constraints. Summary We have discussed the Derived Horizontal Fragmentation. Virtual University Pakistan 23 Course Title: Distributed Database Management Systems Course Code: CS712 Instructor: Dr. Nayyer Masood Lecture No: 26 Virtual University Pakistan 24 In this lecture: - Transaction Management o Basics o Properties of Transaction Database and Transaction Consistency The concept of transaction is used within the database domain as a logical unit of work. A database is in a consistent state if it obeys all of the consistency (integrity) constraints defined over it state changes occur due to modifications, insertions and deletions (together called updates). The database can be temporarily inconsistent during the execution of a transaction. The important point is that the database should be consistent when then transaction terminates as shown in figure 1 Figure 1: A Transaction Model Transaction consistency refers to the actions of concurrent transactions. Transaction Management is difficult in case of the concurrent access to the database by multiple users. Multiple read-only transactions cause no problem at all, however, if one or more of Begin Transaction T Consistent State of DB May be Temporarily Inconsistent Consistent State Execution of Transaction T End of Transaction T Virtual University Pakistan 25 concurrent transactions try to update data that may cause problem. A transaction is considered to be a sequence of read or/and write operations; it may even consist of a single statement. Transaction Example T-SQL Transaction BUDGET_UPDATE begin EXEC SQL UPDATE J SET BUDGET = BUDGET * 1.1 WHERE JNAME = “CAD/CAM" end The Begin_transaction and end statements delimit a transaction. The use of delimiters is not enforced in every DBMS. Example Database Airline Reservation System – FLIGHT(fNo, fDate, fSrc, fDest, stSold, fCap) – CUST(cName, cAddr, cBal) – FC(fNo, fDate, cName, cSpecial) Let us consider a simplified version of a typical reservation application, where a travel agent enters the flight number, the date, and a customer name and asks for a reservation. The transaction to perform this function can be implemented as follows, where database accesses are specified in embedded SQL notation: Begin_transaction Reservation input(flight_no, dt, c_name); EXEC SQL Select stSold, cap into temp1, temp2 where fNo = flight_no and date = dt if temp1 = temp2 then Virtual University Pakistan 26 output("no free seats"); Abort else EXEC SQL update flight set stSold = stSold + 1 where fNo = flight_no and date = dt; EXEC SQL insert into FC values (flight_no, dt, c_Name, null); Commit; output("reservation completed") end The transaction on Line 1: is to input the flight number, the date and the customer name. Line 2: updates the number of sold seats on the requested flight by one. Line 3: inserts a tuple into the FC relation here we assume that customer is old one so its not necessary to have an insertion into the CUST relation. Line 4: reports the result of the transaction to the agent’s terminal. Termination conditions of Transaction If transaction can complete its task successfully, we say that the transaction commits. If a transaction stops without completing its tasks, we say that it aborts when a transaction is aborted its execution is stopped and all of its already executed actions are undone by returning the database to the state before their execution. This is also known as rollback. Characterization of Transaction Read and Write are major operations of database concern in a transaction. Read set (RS): The set of data items that are read by a transaction. Write set (WS): The set of data items whose values are changed by this transaction Virtual University Pakistan 27 The read set and write set of a transaction need not be mutually exclusive. Finally, the unions of the read set and write set of a transaction constitutes its base set (BS = RS U WS) Formalization of the Transaction Concept Let Oij(x) be some operation Oj of transaction Ti operating on data item x, where Oj € {read,write} and Oj is atomic. Let OSi denote the set of all operations in Transaction Ti, OSi = Uj Oij. We denote by Ni the termination condition for Ti, where Ni € {abort,commit}. Transaction Ti is a partial order Ti = {∑i, <i} where 1- ∑i = OSi U {Ni } 2- For any two operations Oij, Oik € OSi , if Oij = R(x) and Oik = W(x) for any data item x, then either Oij∝iOik or Oik ‘E3’ (EMP) • ASG1 = σeNo ≤ ‘E3’ (ASG) • ASG2 = σeNo > ‘E3’ (ASG) Further suppose these fragments are stored at site 1, 2, 3 and 4 and result at site 5 ASC1’=σresp = ‘Manager(ASG1) EMP1’=EMP1⋈(ASG1’) Site Site ASC2’=σresp = ‘Manager(ASG2) EMP2’=EMP2⋈(ASG2’) Site Site ASG1’ ASG2’ result = EMP1’ U EMP2’ Site EMP1’ EMP2’ result = (EMP1 U EMP2) ⋈ eNo σ resp = ‘Manager’ (ASG1 U ASG2) Site 1 Site 2 Site 3 Site 4 ASG1 ASG2 EMP EMP Virtual University Pakistan 57 Figure 1: Equivalent Distributed Execution Strategies Two equivalent distributed execution strategies for the query are shown in figure 1. an arrow from site I to site j labeled with R indicates that relation R is transferred from site I to site j. Strategy A exploits the fact that relations EMP and ASG are fragmented the same way in order to perform the select and join operation in parallel. Strategy B centralizes all the operand data at the result site before processing the query as shown in figure 1. To evaluate the resource consumption of these two strategies we use a cost model. Let’s Assume • size(EMP) • size(ASG) 400 1000 • tuple access cost • tuple transfer cost 1 unit 10 units • There are 20 Managers • Data distributed evenly at all sites Strategy 1 The cost of strategy A can be derived as follows: • produce ASG': 20*1 20 • transfer ASG' to the sites of E: 20 * 10 200 • produce EMP': (10+10) *1*2 40 • transfer EMP' to result site: 20*10 200 Total 460 Virtual University Pakistan 58 Strategy 2 The cost of strategy B can be derived as follows: • Transfer EMP to site 5: 400 * 10 4000 • Transfer ASG to the site 5 1000 * 10 10000 • Produce ASG‘ by selecting ASG 1000 • Join EMP and ASG’ 8000 Total 23000 In strategy B we assumed that the access methods to relations EMP an ASG based on attributes RESP and ENO are lost because of data transfer. This is reasonable assumption. Strategy A is better by a factor of 50, which is quite significant. It provides better distribution of wok among sites. The difference would be higher if we assumed slower communication and/or high degree of fragmentation. Objective of Query Processing The objective of query processing in a distributed context is to transform a high level query on a distributed database. An important of query processing is query optimization. Query Optimization Many execution strategies are correct transformations of the same high level query the one that optimizes (minimizes) resource consumption should be retained. A good measure of resource consumption is the total cost that will be incurred in processing the query. Total cost is the sum of all times incurred in processing the operations of the query at various sites. In a distributed database system, the total cost to be minimized includes CPU, I/O and communication costs. The first two components (I/O and CPU costs) are the only factors considered by centralized DBMSs. Communication Cost will dominate in WAN but not that dominant in LANs. Query optimization can also maximize throughput Operators’ Complexity Virtual University Pakistan 59 Relational algebra is the output of query processing. The complexity of relational algebra operations, which directly affects their execution time, dictates some principles useful to a query processor. Figure 2 shows the complexity of unary and binary operations. • Select, Project (without duplicate elimination) O(n) • Project (with duplicate elimination), Group O(nlogn) • Join, Semi-Join, Division, Set Operators O(nlog n) • Cartesian Product O(n2) Figure 2: Complexity of Unary and Binary Operations Characterization of Query Processors There are some characteristics of query processors that can be used as a basis for comparison. • Types of Optimization – Exhaustive search for the cost of each strategy to find the most optimal one – May be very costly in case of multiple options and more fragments – Heuristics • Optimization Timing – Static: during compilation • Size of intermediate tables not known always • Cost justified with repeated execution – Dynamic: during execution • Intermediate tables’ size known • Re-optimization may be required Virtual University Pakistan 60 • Statistics – Relation/Fragment: Cardinality, size of a tuple, fraction of tuples participating in a join with another relation – Attribute: cardinality of domain, actual number of distinct values • Decision Sites – Centralized: simple, need knowledge about the entire distributed database – Distributed: cooperation among sites to determine the schedule, need only local information – Hybrid: one site determines the global schedule, each site optimizes the local sub queries Summary We have discussed the basic concepts of query processing and the query optimization in centralized and distributed databases. Virtual University Pakistan 61 Course Title: Distributed Database Management Systems Course Code: CS712 Instructor: Dr. Nayyer Masood Lecture No: 31 Virtual University Pakistan 62 In previous lecture: - Basic concepts of query optimization - Query processing in centralized and distributed DBs In this lecture: - Query decomposition - Its different phases Virtual University Pakistan 63 Query Decomposition: Query decomposition transforms an SQL (relational calculus) query into relational algebra query on global relations. The information needed for this transformation is found in the global conceptual schema. Steps in query decomposition: It consists of four phases: 1) Normalization: Input query can be complex depending on the facilities provided by the language. The goal of normalization is to transform the query to a normalized form to facilitate further processing. This process includes the lexical and analytical analysis and the treatment of WHERE clause. There are two possible normal forms. Conjunctive NF: This is a conjunction (∧ predicate) of disjunctions (∧ predicates) as follows: (p11 ∧p12 ∧…∧p1n) ∧…∧(pm1 ∧pm2 …∧pmn) Disjunctive NF: This is disjunction (∧ predicate) of conjunctions (∧ predicates) as follows: (p11 ∧p12∧…∧p1n) ∧…∧(pm1∧pm2 ∧…∧pmn) The transformation of the quantifier-free predicate is using equivalence rules. Equivalence rules: Some of equivalence rules are: 1. p1∧ p2 ∧ p2∧ p1 2. p1∧ p2 ∧ p2∧ p1 3. p1 ∧ (p2∧ p3) ∧ (p1∧p2) ∧ p3 4. p1 ∧ (p2∧ p3) ∧ (p1∧p2) ∧ p3 5. ¬(¬ p1) ∧ p … Example Virtual University Pakistan 64 The query expressed in SQL is SELECT ENAME FROM EMP,ASG WHERE EMP.ENO=ASG.ENO AND ASG.PNO=’P1’ AND DUR=12 OR DUR=24 The qualification in conjunctive NF is EMP.ENO = ASG.ENO ∧ ASG.PNO=”P1” ∧ (DUR=12 ∧ DUR=24) The qualification in disjunctive NF is (EMP.ENO = ASG.ENO ∧ ASG.PNO=”P1” ∧ DUR=12) ∧ (EMP.ENO = ASG.ENO ∧ ASG.PNO=”P1” ∧ DUR=24) 2) Analysis: Query analysis enables rejection of normalized queries for which further processing is either impossible or necessary. The main reasons for rejection are that the query is type incorrect or semantically incorrect. Type incorrect • If any of its attribute or relation names are not defined in the global schema • If operations are applied to attributes of the wrong type Semantically incorrect • Components do not contribute in any way to the generation of the result • Only a subset of relational calculus queries can be tested for correctness • Those that do not contain disjunction and negation • To detect through Connection graph (query graph) and Join graph Query Graph This graph is used for most queries involving select, project, and join operations. In a graph, one node represents the result relation and any other node represents an operand relation. An edge between two nodes that are not results represents a join, whereas an edge whose destination node is the result represents a project. Virtual University Pakistan 65 Example Consider the following query in SQL; SELECT ENAME, RESP FROM EMP, ASG, PROJ WHERE EMP.ENO = ASG.ENO AND ASG.PNO = PROJ.PNO AND PNAME = “CAD/CAM” AND DUR >= 36 AND TITLE = “PROGRAMMER” Figure1: Query graph Join graph This is the graph in which only joins are considered. Figure2: Join graph If the query graph is not connected, the query is wrong. Virtual University Pakistan 66 Example Consider the SQL query; SELECT ENAME, RESP FROM EMP, ASG, PROJ WHERE EMP.ENO = ASG.ENO AND PNAME = “CAD/CAM” AND DUR >= 36 AND TITLE = “PROGRAMMER” The query graph is shown in figure is disconnected; whish tell us that the query is semantically incorrect. Figure 3: Disconnected query graph 3) Elimination of redundancy: A user query expressed on a view may be enriched with several predicates to achieve view-relation correspondence and ensure semantic integrity and security. The enriched query qualification may then contain redundant predicates. Such redundancy may be eliminated by simplifying the qualification with the following well-known idempotency rules: 1. p1∧¬( p1) ∧false 2. p1∧(p1∧p2) ∧p1 3. p1∧false ∧p1 Virtual University Pakistan 67 … Example Consider SQL query: SELECT TITLE FROM EMP WHERE EMP.ENAME = “J. Doe” OR(NOT(EMP.TITLE = “Programmer”) AND(EMP.TITLE = “Programmer” OR EMP.TITLE = “Elect. Eng.”) AND NOT(EMP.TITLE = “Elect. Eng.”)) After simplification the query becomes SELECT TITLE FROM EMP WHERE EMP.ENAME = “J. Doe” 4) Rewriting: This process is divided into two steps: • Straightforward transformation of query from relational calculus into relational algebra • Restructuring of relational algebra to improve performance Operator tree is used to represent the algebra query graphically. Operator tree It is a tree in which a leaf node is a relation and a nonleaf node is an intermediate relation produced by a relational algebra operator. The transformation of a tuple relational calculus query into an operator tree can easily be achieved as follows. First, a different leaf is created for each different tuple variable. In SQL, the leaves are immediately Virtual University Pakistan 68 available in the FROM clause. Second, the root node is created as a project operation and these are found in SELECT clause. Third, the SQL WHERE clause is translated into the sequence of relational operations (select, join, union, etc.). Example Consider the SQL query: SELECT ENAME FROM PROJ, ASG, EMP WHERE ASG.ENO = EMP.ENO AND ASG.PNO = PROJ.PNO AND ENAME = “J.DOE” AND PROJ.PNAME = “CAD/CAM” AND (DUR = 12 OR DUR = 24) Figure 4: Example of operator tree By applying transformation rules many different trees may be found. Transformation Rules Virtual University Pakistan 69 • Commutativity of binary operations R × S ∧ S × R R S ∧ S R • Associativity of binary operations ( R × S) × T ∧ R × (S × T) (R S) T ∧ R (S T) There are other rules that we will discuss in next lecture. Summary: Query processing has four different phases and the first phase is the Query Decomposition. The steps of query decomposition are normalization, analysis, simplification and rewriting. Our goal in every process is same to produce a correct and efficient query. We have studied an equivalence rules, idempotency rules and some of transformation rules. Virtual University Pakistan 70 Course Title: Distributed Database Management Systems Course Code: CS712 Instructor: Dr. Nayyer Masood Lecture No: 32 Virtual University Pakistan 71 In previous lecture: - Query decomposition - Its different phases In this lecture: - Final phase of Query decomposition - Next phase of query optimization: Data localization Virtual University Pakistan 72 Transformation Rules: First two transformation rules have discussed in previous lecture and we are going to discuss other rules. • Idempotence of unary operations o ΠA’(ΠA’’(R)) ⇔ ΠA’(R) o σp1(A1)(σp2(A2)(R)) ⇔σp1(A1) ∧ p2(A2)(R) • Commuting selection with projection o πA1, ….,An(σp(Ap)(R)) ⇔ πA1, ….,An((σp(Ap) πA1, ….,An, Ap(R))) • Commuting selection with binary operations o σp(A)(R×S) ⇔ (σp(A) (R)) ×S o σp(Ai)(R(Aj,Bk)S) ⇔ (σp(Ai) (R)) (Aj,Bk)S • Commuting projection with binary operations o ΠC(R×S) ⇔ΠA’(R) ×ΠB’(S) o ΠC(R(Aj,Bk)S) ⇔ΠA’(R) (Aj,Bk)ΠB’(S) These rules enables the generation of many equivalent trees. In optimization phase, one can imagine comparing all possible trees based on their predicted cost. The excessively large number of possible trees makes this approach unrealistic. The above rules can be used to restructure the tree in a systematic way so that the bad operator trees are eliminated. These rules can be used in four different ways: • They allow the separation of unary operations, simplifying the query expression. • Unary operations on the same relation may be grouped together • Unary operations can be commuted with binary operations • Binary operations can be ordered Example Consider the SQL query: SELECT ENAME Virtual University Pakistan 73 FROM PROJ, ASG, EMP WHERE ASG.ENO = EMP.ENO AND ASG.PNO = PROJ.PNO AND ENAME = “Saleem” AND PROJ.PNAME = “CAD/CAM” AND (DUR = 12 OR DUR = 24) Figure1: Equivalent operator tree ASG PROJ EMP x ⋈ pNo^eNo σ (pName = ‘CAD/CAM’)^ (dur = 12 v dur = 24)^ eName ≠’Saleem’ π eName Virtual University Pakistan 74 Figure 2: Rewritten operator tree This concludes query decomposition and restructuring. Now we move towards the second phase of query optimization or query processing that is Data Localization. Data Localization: The localization layer translates an algebraic query on global relations into an algebraic query expressed on physical fragments. Localization uses information stored in the fragment schema. Fragmentation is defined through fragmentation riles, which can be expressed as relational queries. A global relation can be reconstructed by applying the reconstruction rules and deriving a relational algebra program whose operands are the fragments, this process is called localization program. A native way to localize a distributed query is to generate a query where each global relation is substituted by its localization program. This can be viewed as replacing the PROJ ASG EMP σpName = ‘CAD/CAM’ σdur=12 v dur = 24 σeName != ‘Saleem’ π pNo’ π pNo, eNo π eNo, eName π pNo, eName π eName Virtual University Pakistan 75 leaves of the operator tree of distributed query with sub trees corresponding to the localization programs. The query obtained in this way is called a generic query. Here we are going to present reduction techniques for each type of fragmentation. Reduction for primary horizontal fragmentation: The horizontal fragmentation function distributes a relation based on selection predicates. Consider an example: Example: Relation EMP(eNo, eName, title) can be split into three horizontal fragments. • EMP1 = σeNo ≤ ‘E3’ (EMP) • EMP2 = σ’E3’ ‘E6’ (EMP) The localization program for a horizontally fragmented relation is the union of fragments.e.g. EMP = EMP1 U EMP2 U EMP3 Horizontal fragmentation can be exploited to simplify both selection and join operations. Reduction with selection: Selections on fragments that have a qualification contradicting the qualification of the fragmentation rule generate empty relations. The rule can be stated as: Rule 1: σpi (Rj) = Ø if ∧x in R: ¬(pi(x) ^ pj(x)) where pi and pj are selection predicates, x denotes a tuple, and p(x) denotes “predicate p holds for x”. Example: Consider a query SELECT * FROM EMP Virtual University Pakistan 76 WHERE ENO = ‘E7’ Generic query Reduced query Figure 3: Reduction for horizontal fragmentation (with selection) Reduction with join: Joins on horizontally fragmented relations can be simplified when the joined relations are fragmented according to the join attribute. The simplification consists of distributing joins over unions and eliminating useless joins. The distribution of join over union can be stated as: (R1UR2) ∧ S= (R1 ∧ R3) U (R2 ∧ R3) Where Ri are fragments of R and S is a relation. With this transformation, unions can be moved up in the operator tree so that all possible joins of fragments are exhibited. Useless joins of fragments can be determined when the qualifications of joined fragments are contradicting. Assuming the fragments Ri and Rj are defined, according to predicates pi and pj on the same attribute the simplification rule can be stated as follows: Rule2: Ri∧Rj = Ø if for all x in Ri and for all y in Rj:¬(pi(x) ^ pj(y)) EMP3 σeNo = ‘E7’ EMP1 EMP2 EMP3 U σeNo = ‘E7’ Virtual University Pakistan 77 The determination of useless joins are thus be performed by looking only at the fragment predicates. The application of this rule permits the join of two relations to be implemented as parallel partial joins of fragments. It is not always the case that the reduced query is better than the generic query. The generic query is better when there are a large number of partial joins in the reduced query. Example: Assume relation ASG is fragmented as: • ASG1 = σeNo ≤ ‘E3’ (ASG) • ASG2 = σ’eNo > ‘E3’ (ASG). Consider a query: SELECT eName FROM EMP, ASG WHERE EMP.eNo = ASG. eNo The equivalent generic query is given in figure4. The query reduced by distributing joins over unions and applying rule 2 can be implemented as a union of three partial joins that can be done in parallel (figure5). Figure 4: Generic query EMP1 EMP2 EMP3 U ⋈eNo ASG1 ASG2 U Virtual University Pakistan 78 Figure 5: Reduced query Reduction for vertical fragmentation: The vertical fragmentation function distributes a relation based on projection attributes. Since the reconstruction operator for vertical fragmentation is the join, the localization program for a vertically fragmented relation consists of the join of the fragment on the common attribute. Example: Relation EMP can be divided into VFs where the key attribute ENO is duplicated. • EMP1 = πeNo, eName (EMP) • EMP2 = πeNo, title (EMP) Relation R defined over attributes A = {A1, ..., An} vertically fragmented as Ri = πA' (R) where A' ⊆ A Rule3: πD,K(Ri) is useless if the set of projection attributes D is not in A‘. Example: Consider a query: Select eName from EMP EMP1 U ⋈eNo ASG1 EMP2 ⋈eNo ASG2 EMP3 ⋈eNo ASG2 Virtual University Pakistan 79 Generic query Reduced query Figure 6: Reduction for vertical fragmentation Reduction for derived fragmentation: Relation R is fragmented based on the predicate on S. Derived fragmentation should be done for hierarchical relationship between R and S. Example: Assume ASG and EMP relations can be indirectly fragmented according to the following rules: • ASG1: ASG ∧ ENO EMP1 • ASG2: ASG ∧ ENO EMP2 • EMP1: σ title= ‘Programmer’ (EMP) • EMP2: σ title ≠“Programmer’ (EMP) Consider a query: EMP1 ⋈eNo EMP2 π eName EMP1 π eName Virtual University Pakistan 80 SELECT * FROM EMP, ASG WHERE ASG.eNo = EMP.eNo AND EMP.title = "Mech. Eng." Generic query Query after pushing selection down ASG1 ⋈eNo U ASG2 EMP1 EMP2 U σtitle = ‘Mech ASG1 ⋈eNo U ASG2 EMP2 σtitle = ‘Mech Eng.’ Virtual University Pakistan 81 Figure 7: Query after moving unions up Figure 8: Reduced query after eliminating the left sub tree Summary We have discussed final phase of Query decomposition and next phase of query optimization i.e. Data localization. ASG1 ⋈eNo U EMP2 ASG2 EMP2 σtitle = ‘Mech Eng.’ σtitle = ‘Mech Eng.’ ⋈eNo ASG2 EMP2 σtitle = ‘Mech Eng.’ ⋈eNo Virtual University Pakistan 82 Course Title: Distributed Database Management Systems Course Code: CS712 Instructor: Dr. Nayyer Masood Lecture No: 33 Virtual University Pakistan 83 In previous lecture: - Final phase of QD - Data Localization: for HF, VF and DF In this lecture: - Data Localization for Hybrid Fragmentation - Query Optimization Reduction for hybrid fragmentation: Hybrid fragmentation contains both types of Fragmentations. The goal of hybrid fragmentation is to support, efficiency, queries involving projection, selection and join. Example: Here is an example of hybrid fragmentation of relation EMP: • EMP1=σeNo ≤ E4 (πeNo, eName (EMP)) • EMP2=σeNo > E4 (πeNo, eName (EMP)) • EMP3=πeNo, title (EMP) Consider a SQL query Select eName from EMP where eNo = “E5”. Generic query is shown in figure 1. and reduced query is shown in figure 2. Virtual University Pakistan 84 Figure 1: Generic query Figure 2: Reduced query Summary of what we have done so far • Query Decomposition: generates an efficient query in relational algebra – Normalization, Analysis, Simplification, Rewriting EMP2 π eName σeNo = E5 EMP1 ⋈eNo EMP2 π eName EMP3 U σeNo = E5 Virtual University Pakistan 85 • Data Localization: applies global query to fragments; increases optimization level • So, next is the cost-based optimization Query optimization: Query optimization refers to the process of producing a query execution plan (QEP) which represents an execution strategy for the query. The selected plan minimizes an objective cost functions. A query optimizer, the software module that performs query optimization, is usually seen as three components: 1. Search space 2. Search strategy 3. Cost model 1) Search Space The search space is the set of alternative execution plans to represent the input query. These plans are equivalent, in the sense that the same result but they differ on execution order of operations and the way these operations are implemented. Search space consists of equivalent query trees produced using transformation rules. Optimizer concentrates on join trees, since join cost is the most effective. Example: Select eName, resp From EMP, ASG, PROJ where EMP.eNo = ASG. eNo and ASG.pNo = PROJ.pNo. The Equivalent join trees are shown in figure 3. Virtual University Pakistan 86 EMP x PROJ ASG ⋈ pNo, eNo PROJ ⋈ pNo ASG EMP ⋈eNo EMP ⋈eNo ASG PROJ ⋈ pNo Virtual University Pakistan 87 Figure 3: Equivalent join trees For a complex query the number of equivalent operator trees can be very high. For instance, the number of alternative join trees that can be produced by applying the commutativity and associativity rules is O(N!) for N relations. Query optimizers restrict the size of the search space they consider. Two restrictions are: 1- Heuristics - Most common heuristic is to perform selection and projection on base relations - Another is to avoid Cartesian product 2- Shape of join Tree Two types of join trees are distinguished: - Linear Tree: At least one node for each operand is a base relation - Bushy tree: May have operators with no base relations as operands (both operands are intermediate relations) 2) Search Strategy • Most popular search strategy is Dynamic Programming • That starts with base relations and keeps on adding relations calculating cost • DP is almost exhaustive so produces best plan • Too expensive with more than 5 relations • Other option is Randomized strategy • Do not guarantee best 3) Cost Model: An optimizer’s cost model includes cost functions to predict the cost of operators, statistics, and base data and formulas to evaluate the sizes of intermediate results. Cost function: • The cost of distributed execution strategy can be expressed with respect to either the total time or the response time. • Total time = CPU time + I/O time + tr time • In WAN, major cost is tr time Virtual University Pakistan 88 • Initially ratios were 20:1 for tr and I/O, for LAN it is 1:1.6 • Response time = CPU time + I/O time + tr time • TCPU = time for a CPU insts • TI/O = a disk I/O • TMSG = fixed time for initiating and recv a msgs • TTR = transmit a data unit from one site to another Example: Figure 4 Assume that TMSG and TTR are expressed in time units. The total cost of transferring x data units from site 1 to site 3 as shown in figure 4 and y data units from site 2 to site 3 is • Total Time = 2TMSG + TTR*(x+y) • Response Time = max{TMSG + TTR*X, TMSG + TTR*Y} Site 1 Site 2 Site 3 X units Y units Virtual University Pakistan 89 Database Statistics The main factor affecting the performance of an execution strategy is the size of the intermediate relations that are produced during the execution. When a subsequent operation is located at a different site, the intermediate relation must be transmitted over the network. There is a direct trade-off between the precision of the statistics and the cost of managing them, the more precise statistics being the more costly. For each relation R[A1, A2, …, An] fragmented as R1, …, Rr,the statistical data typically are the following: 1. Length of each attribute: length(Ai) 2. The number of distinct values for each attribute in each fragment: card(πAi(Rj)) 3. Maximum and minimum values in the domain of each attribute: min(Ai), max(Ai) 4. The cardinalities of each domain: card(dom[Ai]) and the cardinalities of each fragment: card(Rj) 5. Join selectivity factor for some of the relations SFJ (R,S) = card(R ⋈ S)/ (card(R) ∗ card(S)) Cardinalities of Intermediate Results Database statistics are useful in evaluating the cardinalities of the intermediate results of queries. Two simplifying assumptions are commonly made about the database. The distribution of attribute values in a relation is supposed to be uniform, and all attributes are independent, meaning that the value of an attribute does not affect the value of any other attribute. The following are the formulas for estimating the cardinalities of the result of the basic relational algebra operations. Selection Operation: • Card(σF(R))=SFS(F) * card(R) • SFS(A = value) = 1/card(πA(R)) • SFS(A > value) = max(A) – value/(max(A) – min(A)) • SFS(A < value) = value - min(A) /(max(A) – min(A)) • SFS(A < value) = max(A) – value /(max(A) – min(A)) • SFS(p(Ai) ^ p(Aj)) = SFS(p(Ai)) *(SFSp(Aj)) Virtual University Pakistan 90 • SFS(p(Ai) v p(Aj)) = SFS(p(Ai)) + SFS(p(Aj))–(SFS(p(Ai))* SFS(p(Ai))). Cardinality of Projection: • Hard to determine precisely • Two cases when it is trivial 1- When a single attribute A, card(πA(R)) = card (A) 2- When PK is included card(πA(R)) = card (R) Cartesian Product: • card(RxS) = card (R) * card(S) Cardinality of Join: • No general way to test without additional information • In case of PK/FK combination Card(R ⋈ S) = card (S) Semi Join: • SFSJ(R ⋉AS)= card(πA(S))/ card(dom[A]) • card(R ⋉AS) = SFSJ(S.A) * card(R) Union: • Hard to estimate • Limits possible which are card(R) + card(S) and max{card (R) + card (S)) Difference: • Like Union, card (R) for (R-S), and 0 Centralized Query Optimization Virtual University Pakistan 91 A distributed query is transformed into local ones, each of which is presented in centralized way. Distributed query optimization techniques are often extensions of the techniques for centralized systems. Centralized query optimization is simpler problem; the minimization of communication costs makes distributed query optimization more complex. Two popular query optimization techniques: • INGRES • Dynamic optimization • Recursively breaks into smaller ones • System R • Static optimization • Based on exhaustive search using statistics about the database Maximum DBMs uses static approach s here our focus is on static approach that is adopted by system R. Summary We have discussed the final phase of data localization the concepts of query optimization and the components of query optimization: search space, cost model and search strategy. For cost calculation database information and statistics are required. Virtual University Pakistan 92 Course Title: Distributed Database Management Systems Course Code: CS712 Instructor: Dr. Nayyer Masood Lecture No: 34 Virtual University Pakistan 93 In previous lecture: - Concluded Data Localization - Query Optimization o Components: Search space, cost model, search strategy o Search space consists of equivalent query trees o Search strategy could be static, dynamic or randomized o Cost model sees response and total times… o Transmission cost is the most important o Another major factor is size of intermediate tables o Database statistics are used to evaluate size of intermediate tables o Selectivity factor, card, size are some major figures In this lecture: - Query Optimization - Centralized Query optimization o Best access path o Join Processing - Query optimization in Distributed Environment Centralized Query Optimization: System R: System R performs static query optimization based on the exhaustive search of the solution space. The input to the optimizer of system R is a relational algebra tree resulting from the decomposition of an SQL query. The output is an execution plan that implements the “optimal” relational algebra tree. The optimizer assigns a cost to every candidate tree and retains the one with the smallest cost. The candidate trees are obtained by a permutation of the join orders of the n relations of the query using the commutativity and associativity rules. To limit the overhead of optimization, the number of alternative trees is reduced using dynamic Virtual University Pakistan 94 programming. The set of alternative strategies is considered dynamically so that when two joins are equivalent by commutativity, only the cheapest one is kept. Two major steps in Optimization Algorithm • Best access path for individual relation with predicate • The best join ordering is eliminated An important decision with either join method is to determine the cheapest access path to internal relation. There are two methods: 1) Nested loops 2) Merge join 1) Nested loops: It composes the product of the two relations. For each tuple of the external relation, the tuples of the internal relation that satisfy the join predicate are retrieved one by one to form the resulting relation. An index on the join attribute is very efficient access path for internal relation. In the absence of an index, for relations of n1 and n2 pages resp. this algorithm has a cost proportional to n1*n2 which may be prohibitive if n1 & n2 are high. 2) Merge join: If consists of merging two sorted relations on the join attribute as shown in figure 1. Indices on the join attribute may be used as access paths. If the join criterion is equally the cost of joining two relations n1 and n2 pages, resp. is proportional to n1+n2. this method is always chosen when there is an equi join, and when the relations are previously sorted. Example: Select eName From EMP, ASG, PROJ Where EMP.eNo = ASG.eNo & PROJ.pNo = ASG.pNo & pName = ‘CAD/CAM’ We assume the following indices: • EMP has an index on eNo • ASG has an index on pNo • PROJ has an index on pNo and an index on pName Virtual University Pakistan 95 Figure 1: Join graph of query We assume that the first loop of the algorithm selects the following best single relation access paths: • EMP: sequential scan (no selection on EMP) • ASG: sequential scan (no selection on ASG) • PROJ: index on pName (there is a selection on PROJ based on pName) The dynamic construction of tree of alternative strategies is shown in figure. The maximum number of join orders is 3!. The operations that are underlined are dynamically eliminated. The first level of the tree indicates the best single-relation access method. The second level indices for each of these, the best join method with any other relation as shown in figure 2. Figure 2: Alternative join orders EMP x PROJ EMP ASG PROJ EMP⋈ASG ASG⋈EMP PROJ x EMP PROJ⋈ASG ASG⋈PROJ (ASG⋈EMP )⋈PROJ (PROJ⋈ASG)⋈EMP EMP PROJ eNo ASG pNo Virtual University Pakistan 96 Join Ordering in Fragmented Queries: Ordering joins is an important aspect of centralized query optimization. Join ordering in a distributed context is even more important since joins between fragments may increase the communication time. Two basic approaches exist to order joins in fragment queries. • Optimize the ordering of joins • Replaces joins by combination of semi-joins to minimize communication cost Join Ordering: Some algorithms optimize the ordering of joins directly without using semijoins. Distributed INGRES and R* algorithms are representative of algorithms that use joins rather than semijoins. Example: Let us consider a simpler problem of operand transfer in a single join. The query is R ∧ S, where R and S are relation stored at different sites as shown in figure 3. The obvious choice of the relation to transfer is to send the smaller relation to the site of the larger one, which gives rise to two possibilities as shown in figure. To make this choice we need to evaluate the size of R and of S. we now consider the case where there are more than two relations to join. As in the case of single join, the objective of the join-ordering algorithm is to transmit smaller operands. Estimating the size of join results is mandatory, but also difficult. A solution is to estimate the communication cost of all alternative strategies and to choose the best one. The number of strategies grows rapidly with the number of relations. Figure 3: Transfer of operands in binary operation Example: Consider the following query expressed in relational algebra: PROJ ∧ pNO EMP ∧ eNO ASG R If size(R) < size(S) S If size(S) < size(R) Virtual University Pakistan 97 Whose join graph is given in figure 4, we have made certain assumptions about the locations of three relations. This query can be executed in at least five different ways. We describe these strategies by the following programs, where (R site j) stands for “relation R is transferred to site j”. Figure 4: Join graph of distributed query Strategy 1: EMP
site2, site2 computes EMP’= EMP ∧ ASG
site3 computes EMP’ ∧ PROJ Strategy 2: ASG
site1, site1 computes EMP’= EMP ∧ ASG
site3 computes EMP’ ∧ PROJ Strategy 3: ASG
site3, site3 computes ASG’= PROJ ∧ ASG
site1 Strategy 4: PROJ
site2, site2 computes PROJ’= PROJ ∧ ASG
site1 computes EMP ∧ PROJ’ Strategy 5: EMP, PROJ
site2, site2 computes PROJ ∧ ASG ∧ EMP To select one of these programs, the following sizes must be known or predicted : size(EMP), size(ASG),size(PROJ),size(EMP ∧ ASG), and size(ASG ∧ PROJ). If it is the reponse time that is being considered, the optimization must take into account the fact that transfers can be done in parallel with strategy 5. an alternate to enumerating all the solutions is to use heuristics that consider only the sizes of the operand relations by assuming, e.g. that the cardinality of the resulting join is the product of cardinalities. In EMP ASG PROJ eNo pNo Site 2 Site 1 Site 3 Virtual University Pakistan 98 this case relations are ordered by increasing sizes ans the order of execution is given by this ordering and the join graph. For instance, the order (EMP, ASG, PROJ) coule use strategy 1, while the order (PROJ, ASG, EMP) could use strategy 4. Summary We have discussed the query optimization, join operations that are required in centralized and fragmented queries that are required in distributed environment. We will continue this discussion in next lecture. Virtual University Pakistan 99 Course Title: Distributed Database Management Systems Course Code: CS712 Instructor: Dr. Nayyer Masood Lecture No: 35 Virtual University Pakistan 100 In previous lecture: - Query Optimization - Centralized Query Optimization o Best access path o Join Processing - Query Optimization in Distributed Environment. In this lecture: - Query Optimization o Fragmented Queries o Joins replaced by Semijoins o Three major Query Optimization algorithms Semijoin based Algorithms: The main shortcoming of the join approach is that entire operand relations must be transferred between sites. The semijoin acts as a size reducer for a relation much as a selection does. The join of two relations R and S over attribute A, stored at sites 1 and 2,resp. can be computed by replacing one or both operand relations by a semijoin with the other relation, using the following rules: So R ⋈A S can be replaced: – (R ⋉A S) ⋈A S – R ⋈A (S ⋉A R) – (R ⋉A S) ⋈A (S ⋉A R) The choice between one of the three semijoin strategies requires estimating their respective costs. The use of the semijoin is beneficial if the cost to produce and send it to the other site is less than the cost of sending the whole operand relation and of doing the Virtual University Pakistan 101 actual join. To illustrate the potential benefit of the semijoin, let us compare the costs of the two alternatives R ⋈A S verses (R ⋉A S) ⋈A S, assuming that size(R) < size (S). The following program, using the semijoin operation: 1) πA (S)
site 1 2) Site1 computes R’ = R ⋉A S’ 3) R’
site 2 4) Site2 computes R’ ⋈A S For the sake of simplicity let us ignore the constant TMSG in the communication time assuming that the term TTR*size(R) is much larger. We can then compare the two alternatives in terms of the amount of transmitted data. The cost of the join-based algorithm is that of transferring relation R to site2. The cost of the semi-join based algorithm is the cost of steps1 and 3 above. Therefore the semijoin approach is better if Size(πA(S)) + size(R ⋉A S) < size(R) The semijoin approach is better if the semijoin acts as a sufficient reducer, if a few tuples of R participate in the join. The join approach is better if almost all tuples of R participate in the join, because the semijoin approach requires an additional transfer of a projection on the join attribute. The cost of projection step can be minimized by encoding the result of the projection in bit arrays thereby reducing the cost of transferring the joined attribute values. It is important to note that neither approach is systematically the best; they should be considered as complementary. The semijoin can be useful in reducing the size of the operand relations involved in multiple join queries. Query optimization becomes more complex in these cases. Semijoin approach can be applied to each individual join, consider an example: Example: Consider an example of a program to compute EMP ⋈ ASG ⋈ PROJ is EMP’ ⋈ ASG’ ⋈ PROJ Virtual University Pakistan 102 where EMP’ = EMP ⋉ ASG and ASG’ = ASG ⋉ PROJ We may further reduce the size of an operand relation by using more than one semioin. For example, EMP’ can be replaced in the preceding program by EMP” derived as EMP” = EMP ⋉ (ASG ⋉ PROJ) Since if size (ASG ⋉ PROJ) <= size(ASG), we have size(EMP’’) <= size(EMP’). In this way EMP can be reduced by the sequence of semijoins: EMP ⋉ASG ⋉ PROJ). Such a sequence of semijoins is called a semijoin program for EMP. Similarly, semijoin programs can be found for any relation in a query. For example, PROJ could be reduced by the semijoin program PROJ ⋉ (ASG ⋉ EMP). Not all of the relations involved in a query need to be reduced; we can ignore those relations that are not involved in the final joins. For a given relation, there exist several potential semijoin programs. The number of possibilities is in fact exponential in the number of relations. But there is one optimal semijoin program called full reducer, which for each relation R reduces R more than the others. The problem is to find the full reducer. A simple method is to evaluate the size of all possible semijoin programs and to select the best one. The problems with the enumerative method are twofold: There is a class of queries, called cyclic queries that have cycles in their join graph and for which full reducers can not be found For other queries, called tree queries, full reduces exist, but the number of candidate semijoin programs is exponential in the number of relations, which makes the enumerative approach NP-hard. Example: Consider a SQL query: Select eName From EMP, ASG, PROJ Where EMP.eNo = ASG.eNo and ASG.eNo = PROJ.eNo and EMP.city = PROJ.city Virtual University Pakistan 103 Figure 1: Cyclic Query Figure 2: Tree Query It is possible to derive semijoin programs for reducing it, but the number of operations is multiplied by the number of tuples in each relation, making this approach inefficient. One solution consists of transforming the cyclic graph into a tree by removing one arc of the graph and by adding appropriate predicates to the other arcs such that the removed predicate is preserved by transitivity as shown in figure 1 and 2. Distributed Query Processing Algorithms: Three main representative algorithms are • Distributed INGRES Algorithm • R* Algorithm • SDD-1 Algorithm R* Algorithm: R* uses a compilation approach where an exhaustive search of all alternative strategies is performed in order to choose the one with the least cost. Predicting and enumerating these strategies is costly, the overhead of exhaustive search is rapidly amortized if the query is executed frequently. The R* query processing algorithm deals only with relations as basic units. Query compilation is distributed task in R* coordinated by a EMP ASG PROJ eNo, city pNo, city EMP ASG PROJ eNo pNo city Virtual University Pakistan 104 master site, where the query is initiated. The optimizer of the master site makes all intersite decisions, such as the selection of the execution sitesand the fragments as well as the method for transferring data. As in the centralized case, the optimizer must select the join ordering, the join algorithm (nested loop or merge loop), and the access path for each fragment (e.g clustered index, sequential scan e.t.c). these decisions are based on statistics and formulas used to estimate the size of intermediate results and access path information. The optimizer must select the sites of join results and the method of transferring data between sites. To join two relations, there are three candidate sites: the site of a first relation, the site of second relation or a third site. In R*, two methods are supported for intersite data transfers. 1) Ship-whole • Entire relation transferred • Stored in a temporary relation • In case of merge-join approach, tuples can be processed as they arrive 2) Fetch-as-needed • External relation is sequentially scanned • Join attribute value is sent to other relation • Relevant tuples scanned at other site and sent to first site Inter-site transfers: comparison o Ship-whole  larger data transfer  smaller number of messages  better if relations are small o Fetch-as-needed  number of messages = O(cardinality of external relation)  data transfer per message is minimal • better if relations are large and the join selectivity is good. Example: Virtual University Pakistan 105 Given the join of an external relation R with an internal relation S on attribute A there are four join strategies. Strategy 1: Move outer relation tuples to the site of the inner relation the external tuples can be joined with S as they arrive. Total Cost = LT (retrieve card(R) tuples from R) + CT (size(R)) + LT (retrieve s tuples from S) * card (R) Strategy 2: Move inner relation to the site of outer relation. The internal tuples can not be joined as they arrive; they need to be stored Total Cost = LT (retrieve card(S) tuples from S) + CT (size (S)) + LT (store card(S) tuples as T) + LT (retrieve card(R) tuples from R) + LT (retrieve s tuples from T) * card (R) Strategy 3: Fetch inner tuples as needed for each tuple in R, send join attribute value to site of S. Retrieve matching inner tuples at site S. Send the matching S tuples to site of R. Join as they arrive: Total Cost = LT (retrieve card(R) tuples from R)+ CT (length(A) * card (R)) + LT(retrieve s tuples from S) * card(R) + CT (s * length(S)) * card(R) Strategy 4: Move both inner and outer relations to another site Example: A query consisting join of PROJ (ext) and ASG (int) on pNo Four strategies 1- Ship PROJ to site of ASG 2- Ship ASG to site of PROJ 3- Fetch ASG tuples as needed for each tuple of PROJ Virtual University Pakistan 106 4- Move both to a third site Optimization involves costing for each possibility. That is it regarding R* algorithm for distributed query optimization. SDD-1 Algorithm The query optimization algorithm of SDD-1 is derived from an earlier method called the “hill-climbing” algorithm which has the distinction of being the first distribution query processing algorithm. In this algorithm, refinements of an initial feasible solution are recursively computed until no more cost improvements can be made. The algorithm does not use semijoins, nor does it assume data replication and fragmentation. It is devised for wide area point-to-point networks. The cost of transferring the result to the final site is ignored. This algorithm is quite general in that it can minimize an arbitrary objective function, including the total time and response time. The hill climbing algorithm proceeds as follows. 1- The input to the algorithm includes the query graph, location of relations, and relation statistics. 2- Do the initial local processing 3- Select the initial best plan (ES0) – Calculate cost of moving all relations to a single site – Plan with the least cost is ES0 4- Split ES0 into ES1 and ES2 – ES1: Sending one of the relation to other site, relations joined there – ES2:Sending the result back to site in ES0. 5- Replace ES0 with ES1 and ES2 when we should have cost(ES1) + cost(local join) + cost (ES2) < cost (ES0) 6- Recursively apply step 3 and 4 on ES1 and ES2, until no improvement Example Find the salaries of engineers working on CAD/CAM project • Involves EMP, PAY, PROJ and ASG Πsal(PAY ⋈ title(EMP ⋈ eNo(ASG ⋈ pNo(σpName = ‘CAD/CAM’ (PROJ))))) Virtual University Pakistan 107 Assume that Tmsg = 0 and TTR = 1. we ignore the local processing following which the database is Relation Size Site EMP PAY PROJ ASG 8 4 1 10 1 2 3 4 Assume Length of a tuple is 1 So size(R) = card(R) Considering only transfers costs Site 1 • PAY
site 1 = 4 • PROJ
site 1 = 1 • ASG
site 1 = 10 • Total = 15 Cost for site 2 = 19 Cost for site 3 = 22 Cost for site 4 = 13 So site 4 is our ES0 Move all relations to site 4. Summary We have discussed Query Optimization, Fragmented Queries, Joins replaced by Semijoins. Three major Query Optimization algorithms. Virtual University Pakistan 108 Course Title: Distributed Database Management Systems Course Code: CS712 Instructor: Dr. Nayyer