{"id":58,"date":"2018-07-18T09:16:45","date_gmt":"2018-07-18T09:16:45","guid":{"rendered":"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=58"},"modified":"2018-08-01T06:46:52","modified_gmt":"2018-08-01T06:46:52","slug":"relational-algebra","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/chapter\/relational-algebra\/","title":{"rendered":"Relational Algebra"},"content":{"raw":"<p style=\"text-align: justify\"><strong>Relational Algebra<\/strong><\/p>\r\n&nbsp;\r\n\r\nAn algebra is a formal structure consisting of <em>sets<\/em> and <em>operations<\/em> on those sets.\r\n\r\nRelational algebra is a formal system for manipulating relations.\r\n<ul>\r\n \t<li>Operands of this algebra are relations.<\/li>\r\n \t<li style=\"text-align: justify\">Operations of this algebra include the usual set operations (since relations are sets of tuples), and special operations defined for relations selection<\/li>\r\n \t<li>projection<\/li>\r\n \t<li>join<\/li>\r\n<\/ul>\r\n<p style=\"text-align: center\"><img class=\"size-full wp-image-59 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-11.png\" alt=\"\" width=\"662\" height=\"373\" \/><\/p>\r\n&nbsp;\r\n<div>\r\n\r\n<strong>\u00a0<\/strong>\r\n<p style=\"text-align: justify\">A <em>predicate<\/em> is a boolean expression whose operators are the logical connectives (and, or, not) and arithmetic comparisons (LT, LE, GT, GE, EQ, NE), an<\/p>\r\n<p style=\"text-align: center\"><img class=\"size-full wp-image-60 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-12.png\" alt=\"\" width=\"429\" height=\"136\" \/><\/p>\r\n<p style=\"text-align: center\"><img class=\"size-full wp-image-61 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-13.png\" alt=\"\" width=\"666\" height=\"376\" \/><\/p>\r\n\r\n<div>\r\n\r\n<strong>\u00a0 \u00a0Implementing Set Operations<\/strong>\r\n\r\n&nbsp;\r\n\r\nTo implement R1 U R2 (while eliminating duplicates) we can\r\n\r\n<\/div>\r\n<ul>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">sort R1 in O(N log N)<\/span><\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">sort R2 in O(M log M)<\/span><\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">merge R1 and R2 in O(N M)<\/span><\/li>\r\n<\/ul>\r\n<div>\r\n\r\n\u00a0 \u00a0If we allow duplicates in union (and remove them later) we can\r\n<ul>\r\n \t<li>copy R1 to R3 in O(N)<\/li>\r\n \t<li>insert R2 in R3 in O(M)<\/li>\r\n<\/ul>\r\nIf we have an index and don't want duplicates we can\r\n<ul>\r\n \t<li>copy R1 to R3 in O(N)<\/li>\r\n \t<li>for each tuple in R2 (which is O(M))<\/li>\r\n \t<li>use index to lookup tuples in R1 with the same index value O(1)<\/li>\r\n \t<li>if R2 tuple equals some such R1 tuple, don't add R2 tuple to R3<\/li>\r\n<\/ul>\r\nIntersection and set difference have corresponding implementations.\r\n\r\n&nbsp;\r\n\r\n<strong>Implementing Projection<\/strong>\r\n\r\n&nbsp;\r\n\r\nTo implement projection we must\r\n<ul>\r\n \t<li>\u00a0process every tuple in the relation<\/li>\r\n \t<li>remove any duplicates that result To avoid duplicates we can<\/li>\r\n \t<li>sort the result and remove consecutive tuples that are equal<\/li>\r\n \t<li>requires time O(N log N) where N is the size of the original relation<\/li>\r\n \t<li>implement the result as a set<\/li>\r\n \t<li>set insertion guarantees no duplicates<\/li>\r\n \t<li>by using a hash table, insertion is O(1), so projection is O(N)<\/li>\r\n<\/ul>\r\n<strong>\u00a0 Implementing Selection<\/strong>\r\n\r\n&nbsp;\r\n\r\nIn the absence of an index we\r\n<ul>\r\n \t<li>apply the predicate to every tuple in the relation<\/li>\r\n \t<li>insert matches in the resulting relation<\/li>\r\n \t<li>duplicates can't occur<\/li>\r\n \t<li>take O(N) time<\/li>\r\n<\/ul>\r\nGiven an index, and a predicate that uses the index key, we\r\n<ul>\r\n \t<li>Lookup tuples using the key<\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">evaluate only those tuples with the predicate<\/span><\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">take O(K) time, where K tuples match the key<\/span><\/li>\r\n<\/ul>\r\n<\/div>\r\n<div>\r\n\r\n<strong>\u00a0 \u00a0Implementing Join with Nested Loops<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">A <em>nested loop join<\/em> on relations R1 (with N domains) and R2 (with M domains), considers all |R1| x |R2| pairs of tuples.<\/p>\r\n&nbsp;\r\n\r\n<strong>R3= join(R1,Ai,R2,Bj)<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>for each tuple t in R1 do<\/strong>\r\n\r\n<strong>for each tuple s in R2 do<\/strong>\r\n\r\n<strong>if t.Ai = s.Bj then<\/strong>\r\n\r\n<strong>insert(R3, t.A1, t.A2, ..., t.AN,<\/strong>\r\n\r\n<strong>s.B1, ..., s.B(j-1), s.B(j 1), ..., s.BM)<\/strong>\r\n\r\n&nbsp;\r\n\r\nThis implementation takes time O(|R1|*|R2|).\r\n\r\n&nbsp;\r\n\r\n<strong>Index Join<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">An <em>index join<\/em> exploits the existence of an index for one of the domains used in the join to find matching tuples more quickly.<\/p>\r\n&nbsp;\r\n\r\n<strong>R3= join(R1,Ai,R2,Bj)<\/strong>\r\n\r\n<strong>for each tuple t in R1 do<\/strong>\r\n\r\n<strong>for each tuple s in R2 at index(t.Ai) do<\/strong>\r\n\r\n<strong>insert(R3, t.A1, t.A2, ..., t.AN,<\/strong>\r\n\r\n<strong>s.B1, ..., s.B(j-1), s.B(j 1), ..., s.BM)<\/strong>\r\n\r\n&nbsp;\r\n\r\nWe could choose to use an index for R2, and reverse the order of the loops.\r\n\r\nThe decision on which index to use depends on the number of tuples in each relation.\r\n\r\n&nbsp;\r\n\r\n<strong>Sort Join<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">If we don't have an index for a domain in the join, we can still improve on the nested-loop join using <em>sort join<\/em>.<\/p>\r\n&nbsp;\r\n\r\n<strong>R3= join(R1,Ai,R2,Bj)<\/strong>\r\n<ul>\r\n \t<li>Merge the tuples of both relations into a single list<\/li>\r\n \t<li>list elements must identify the original relation<\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">Sort the list based on the value in the join domains Ai and Bj<\/span><\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">all tuples on the sorted list with a common value for the join domains are consecutive<\/span><\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">Pair all (consecutive) tuples from the two relations with the same value in the join domains<\/span><\/li>\r\n<\/ul>\r\n<\/div>\r\n<div>\r\n\r\n<strong>\u00a0 \u00a0Comparison of Join Implementations<\/strong>\r\n\r\n&nbsp;\r\n\r\nAssumptions\r\n<ul>\r\n \t<li>Join R1 and R2 (on domain D) producing R3<\/li>\r\n \t<li>R1 has i tuples, R2 has j tuples<\/li>\r\n \t<li>|R3| = m, 0 &lt;= m &lt;= i * j<\/li>\r\n \t<li>Every implementation takes at least time O(m)<\/li>\r\n<\/ul>\r\nComparison\r\n<ul>\r\n \t<li>Nested-loop join takes time O(i * j)<\/li>\r\n \t<li>Index join (using R2 index) takes time O(i m)<\/li>\r\n \t<li>lookup is O(1) for each tuple in R1<\/li>\r\n \t<li>at most O(m) tuples match<\/li>\r\n \t<li>Sort join takes time O(m (i j)log(i j))<\/li>\r\n \t<li>O(i j) to merge the tuples in R1 and R2<\/li>\r\n \t<li>O((i j) log (i j)) to sort the list<\/li>\r\n \t<li>O(m) to produce the output (0 &lt;= m &lt;= i*j)<\/li>\r\n<\/ul>\r\n<strong>\u00a0 \u00a0Expressing Queries in Relational Algebra<\/strong>\r\n\r\n&nbsp;\r\n\r\nRelational algebra is an unambiguous notation (or formalism) for expressing queries.\r\n\r\nQueries are simply expressions in relational algebra.\r\n<p style=\"text-align: justify\">Expressions can be manipulated symbolically to produce simpler expressions according to the laws of relational algebra.<\/p>\r\n<p style=\"text-align: justify\">Expression simplification is an important query optimization technique, which can affect the running time of queries by an order of magnitude or more.<\/p>\r\n\r\n<ul>\r\n \t<li>early \"selection\" reduces the number of tuples<\/li>\r\n \t<li>early \"projection\" reduces the number of domains<\/li>\r\n<\/ul>\r\n<\/div>\r\n<strong style=\"text-align: initial;font-size: 1em\">\u00a0 \u00a0 Algebraic Laws for Join<\/strong>\r\n<div>\r\n\r\n\u00a0 \u00a0 \u00a0 Commutativity (assuming order of columns doesn't matter)<strong>\u00a0join(R1, Ai, R2, Bj) = join(R2, Bj, R1, Ai)<\/strong>\r\n\r\n&nbsp;\r\n\r\nNonassociativity<strong>\u00a0 join (join(R1, Ai, R2, Bj),Bj,R3,Ck)\u00a0<\/strong>is not the same as<strong>\u00a0 join (R1,Ai,join(R2, Bj, R3, Ck),Bj)<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>Algebraic Laws for Selection<\/strong>\r\n\r\n&nbsp;\r\n\r\nCommutativity\r\n\r\n<strong>\u00a0 \u00a0select(select(R1,P1),P2) = select(select(R1,P2),P1)<\/strong>\r\n\r\n&nbsp;\r\n\r\nSelection pushing\r\n<ul>\r\n \t<li>if P contains attributes of R<\/li>\r\n<\/ul>\r\n<strong>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 select(join(R,Ai,S,Bj),P) = join(select(R,P),Ai,S,Bj)<\/strong>\r\n<ul>\r\n \t<li>if P contains attributes of S<\/li>\r\n<\/ul>\r\n<strong>\u00a0 \u00a0 \u00a0selection (join(R,Ai,S,Bj),P) = join(R,Ai,select(S,P),Bj)<\/strong>\r\n\r\n&nbsp;\r\n\r\nSelection Splitting (where P = A and B)\r\n\r\n&nbsp;\r\n\r\n<strong>select(R,P) = select(select(R,A),B)<\/strong>\r\n\r\n<strong>select(R,P) = select(select(R,B),A)<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>Example: Selection Pushing and Splitting<\/strong>\r\n\r\n&nbsp;\r\n\r\nConsider the following 4 relation database\r\n<ul>\r\n \t<li>CSG: Course-StudentID-Grade<\/li>\r\n \t<li>SNAP: StudentID-Name-Address-Phone<\/li>\r\n \t<li>CDH: Course-Day-Hour<\/li>\r\n \t<li>CR: Course-Room<\/li>\r\n<\/ul>\r\n&nbsp;\r\n\r\nImplement the query \"Where is Amy at Noon on Monday?\"\r\n\r\nLet P be (Name=\"Amy\" and Day=\"Monday\" and Hour=\"Noon\")\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">We can use a brute-force approach that <em>joins<\/em> all the data in the relations into a single large relation, <em>selects <\/em>those tuples that meet the query criteria, and then isolates the answer field using<em> projection<\/em>.<\/p>\r\n\r\n<ul>\r\n \t<li>\u00a0R1 = join(CSG,SNAP)<\/li>\r\n \t<li>\u00a0R2 = join(R1,CDH)<\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">\u00a0R3 = join(R2,CR)<\/span><\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">\u00a0R4 = select(R3,P)<\/span><\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">\u00a0R5 = project(R4,Room)<\/span><\/li>\r\n<\/ul>\r\n<\/div>\r\n<div>\r\n\r\n\u00a0 \u00a0 project(select(join(join(join(CSG,SNAP),CDH),CR),P),Room)\r\n\r\n&nbsp;\r\n\r\n<strong>Selection Pushing and Splitting (cont)<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The selection uses only Name, Day, and Hour attributes (and not Course or Room), so we can push the selection inside the outermost join.<\/p>\r\n\r\n<ul>\r\n \t<li>R1 = join(CSG,SNAP)<\/li>\r\n \t<li>R2 = join(R1,CDH)<\/li>\r\n \t<li>R3 = select(R2,P)<\/li>\r\n \t<li>R4 = join(R3,CR)<\/li>\r\n \t<li>R5 = project(R4,Room)<\/li>\r\n<\/ul>\r\n<p style=\"text-align: justify\">\u00a0 \u00a0We cannot push selection further, because the predicate involves attributes from both operands of the next innermost join (R1,CDH).<\/p>\r\n&nbsp;\r\n\r\nWe can split the selection into two, one based on Name, and the other based on Day-Hour.\r\n<ul>\r\n \t<li>\u00a0 R1 = join(CSG,SNAP)<\/li>\r\n \t<li>\u00a0 R2 = join(R1,CDH)<\/li>\r\n \t<li>\u00a0 R3 = select(R2,Day=\"Monday\" and Hour=\"Noon\")<\/li>\r\n \t<li>\u00a0 R4 = select(R3,Name=\"Amy\")<\/li>\r\n \t<li>\u00a0 R5 = join(R4,CR)<\/li>\r\n \t<li>\u00a0 R6 = project(R5,Room)<\/li>\r\n<\/ul>\r\n<strong>\u00a0 \u00a0Selection Pushing and Splitting (cont 2)<\/strong>\r\n\r\n&nbsp;\r\n\r\nNow we can push the first selection inside the join, since it involves only attributes from the CDH relation.\r\n<ul>\r\n \t<li>\u00a0R1 = join(CSG,SNAP)<\/li>\r\n \t<li>\u00a0R2 = select(CDH,Day=\"Monday\" and Hour=\"Noon\")<\/li>\r\n \t<li>\u00a0R3 = join(R1,R2)<\/li>\r\n \t<li>\u00a0R4 = select(R3,Name=\"Amy\")<\/li>\r\n \t<li>\u00a0R5 = join(R4,CR)<\/li>\r\n \t<li>\u00a0R6 = project(R5,Room)<\/li>\r\n<\/ul>\r\n<p style=\"text-align: justify\">\u00a0 Similarly we can push the second selection inside the preceding join, since it involves only attributes from R1 (ie, Name).<\/p>\r\n\r\n<ul>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">R1 = join(CSG,SNAP)<\/span><\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">R2 = select(CDH,Day=\"Monday\" and Hour=\"Noon\")<\/span><\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">R3 = select(R1,Name=\"Amy\")<\/span><\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">R4 = join(R2,R3)<\/span><\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">R5 = join(R4,CR)\u00a0<\/span><\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">R6 = project(R5,Room)<\/span><\/li>\r\n<\/ul>\r\n<\/div>\r\n<div>\r\n\r\n\u00a0 \u00a0Continuing to push the second select inside the first join\r\n<ul>\r\n \t<li>R1 = select(SNAP,Name=\"Amy\")<\/li>\r\n \t<li>R2 = join(CSG,R1)<\/li>\r\n \t<li>R3 = select(CDH,Day=\"Monday\" and Hour=\"Noon\")<\/li>\r\n \t<li>R4 = join(R2,R3)<\/li>\r\n \t<li>R5 = join(R4,CR)<\/li>\r\n \t<li>R6 = project(R5,Room)<\/li>\r\n<\/ul>\r\n<strong>\u00a0 \u00a0Algebraic Laws for Projection<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>Projection pushing<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">To push a projection operation inside a join requires that the result of the projection contain the attributes used in the join.<\/p>\r\n&nbsp;\r\n\r\n<strong>project(join(R,Ai,S,Bj),D1,D2,...Dn)<\/strong>\r\n\r\n&nbsp;\r\n\r\nIn this case, we know that the domains in the projection will exist in the relation that results from the join.\r\n\r\nIn performing projection first (on the two join relations)\r\n<ul>\r\n \t<li>we should only project on those domains that exist in each of the two relations<\/li>\r\n \t<li>we must ensure that the join domains Ai and Bj exist in the resulting two relations Let PDR = {D|D domain in R, D in {D1...Dn}} U Ai<\/li>\r\n<\/ul>\r\nLet PDS = {D|D domain in S, D in {D1...Dn}} U Bi\r\n\r\n&nbsp;\r\n\r\n<strong>R1 = project(R,PDR)<\/strong>\r\n\r\n<strong>R2 = project(S,PDS)<\/strong>\r\n\r\n<strong>R3 = join(R1,Ai,R2,Bj) = project(join(R,Ai,S,Bj),D1,D2,...Dn)<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>Example: Projection Pushing<\/strong>\r\n\r\n&nbsp;\r\n\r\nImplement the query \"Where is Amy at Noon on Monday?\"\r\n<ul>\r\n \t<li>R1 = select(SNAP,Name=\"Amy\")<\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">R2 = join(CSG,R1)<\/span><\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">R3 = select(CDH,Day=\"Monday\" and Hour=\"Noon\")<\/span><\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">R4 = join(R2,R3)<\/span><\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">R5 = join(R4,CR)\u00a0<\/span><\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">R6 = project(R5,Room)<\/span><\/li>\r\n<\/ul>\r\n<\/div>\r\n<div>\r\n\r\n\u00a0 \u00a0 \u00a0This approach carries along unnecessary attributes every step of the way.\r\n<ul>\r\n \t<li><span style=\"font-size: 1em\">R1 carries Address and Phone attributes<\/span><\/li>\r\n \t<li><span style=\"font-size: 1em\">R4 carries Grade attribute<\/span><\/li>\r\n<\/ul>\r\nWe use projection pushing to eliminate unnecessary attributes early in the implementation.\r\n<ul>\r\n \t<li>R1 = select(SNAP,Name=\"Amy\")<\/li>\r\n \t<li>R2 = join(CSG,R1)<\/li>\r\n \t<li>R3 = select(CDH,Day=\"Monday\" and Hour=\"Noon\")<\/li>\r\n \t<li>R4 = join(R2,R3)<\/li>\r\n \t<li>R5 = project(CR, Course, Room)<\/li>\r\n \t<li>R6 = project(R4, Course)<\/li>\r\n \t<li>R7 = join(R5,R6)<\/li>\r\n \t<li>R8 = project(R7,Room)<\/li>\r\n<\/ul>\r\nNote that R5 is unnecessary, since the domains in the projection are all the domains of CR.\r\n\r\n&nbsp;\r\n\r\n<strong>Projection Pushing (cont)<\/strong>\r\n\r\n&nbsp;\r\n\r\nImplement the query \"Where is Amy at Noon on Monday?\"\r\n<ul>\r\n \t<li>R1 = select(SNAP,Name=\"Amy\")<\/li>\r\n \t<li>R2 = join(CSG,R1)<\/li>\r\n \t<li>R3 = select(CDH,Day=\"Monday\" and Hour=\"Noon\")<\/li>\r\n \t<li>R4 = join(R2,R3)<\/li>\r\n \t<li>R5 = project(R4, Course)<\/li>\r\n \t<li>R6 = join(CR,R5)<\/li>\r\n \t<li>R7 = project(R6,Room)<\/li>\r\n<\/ul>\r\nWe can continue pushing the projection on Course below the join for R4.\r\n<ul>\r\n \t<li>R1 = select(SNAP,Name=\"Amy\")<\/li>\r\n \t<li>R2 = join(CSG,R1)<\/li>\r\n \t<li>R3 = select(CDH,Day=\"Monday\" and Hour=\"Noon\")<\/li>\r\n \t<li>R4 = project(R2,Course)<\/li>\r\n \t<li>R5 = project(R3,Course)<\/li>\r\n \t<li>R6 = join(R4,R5)<\/li>\r\n \t<li>R7 = join(CR,R6)<\/li>\r\n \t<li><span style=\"text-align: initial;font-size: 1em\">R8 = project(R7,Room)<\/span><\/li>\r\n<\/ul>\r\n<\/div>\r\n<div>\r\n\r\n<strong>\u00a0 Projection Pushing (cont2)<\/strong>\r\n\r\n&nbsp;\r\n\r\nWe can continue pushing the projection on Course for R4 below the join for R2.\r\n<ul>\r\n \t<li>R1 = select(SNAP,Name=\"Amy\")\\<\/li>\r\n \t<li>R2 = project(CSG,Course,StudentID)<\/li>\r\n \t<li>R3 = project(R1,StudentID)<\/li>\r\n \t<li>R4 = join(R2,R3)<\/li>\r\n \t<li>R5 = project(R4,Course)<\/li>\r\n \t<li>R6 = select(CDH,Day=\"Monday\" and Hour=\"Noon\")<\/li>\r\n \t<li>R7 = project(R6,Course)<\/li>\r\n \t<li>R8 = join(R6,R7)<\/li>\r\n \t<li>R9 = join(CR,R8)<\/li>\r\n \t<li>R10 = project(R9,Room)<\/li>\r\n<\/ul>\r\n<p style=\"text-align: justify\">A <strong>query language<\/strong> is a language in which user requests information from the database. it can be categorized as either <strong>procedural<\/strong> or <strong>nonprocedural.<\/strong> In a procedural language the user instructs the system to do a sequence of operations on database to compute the desired result. In non procedural language the user describes the desired information without giving a specific procedure for obtaining that information.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">The relational algebra is a procedural query language. It consists of a set of operations that take one or two relations as input and produces a new relation as output.<\/p>\r\n&nbsp;\r\n\r\n<strong>Fundamental Operations<\/strong>\r\n<ul>\r\n \t<li>SELECT<\/li>\r\n \t<li>PROJECT<\/li>\r\n \t<li>UNION<\/li>\r\n \t<li>SET DIFFERENCE<\/li>\r\n \t<li>CARTESIAN PRODUCT<\/li>\r\n \t<li>RENAME<\/li>\r\n<\/ul>\r\n<\/div>\r\n<div>\r\n<p style=\"text-align: justify\">Select and project operations are unary operation as they operate on a single relation.Union, set difference, Cartesian product and rename operations are binary operations as they operate on pairs of relations.<\/p>\r\n&nbsp;\r\n\r\n<strong>Other Operations<\/strong>\r\n<ul>\r\n \t<li>SET INTERSECTION<\/li>\r\n \t<li>NATURAL JOIN<\/li>\r\n \t<li>DIVISION<\/li>\r\n \t<li>ASSIGNMENT<\/li>\r\n<\/ul>\r\n<p style=\"text-align: justify\"><strong>\u00a0 \u00a0The select operation<\/strong>: - to identify a set of tuples which is a part of a relation and to extract only these tuples out. The select operation selects tuples that satisfy a given predicate or condition.<\/p>\r\n\r\n<ul>\r\n \t<li>It is a unary operation defined on a single relation.<\/li>\r\n \t<li>It is denoted as <strong>\u03c3<\/strong>.<\/li>\r\n<\/ul>\r\n<p style=\"text-align: justify\"><strong>\u00a0 \u00a0The union operation: <\/strong>- is used when we need some attributes that appear in either or both of the two relations.<\/p>\r\n\r\n<ul>\r\n \t<li>It is denoted as <strong>U<\/strong>.<\/li>\r\n<\/ul>\r\n<strong>\u00a0 \u00a0example:<\/strong>\r\n\r\n&nbsp;\r\n\r\nBorrower (customer-name, loan-number)\r\n\r\nDepositor (customer-name, account-number)\r\n\r\nCustomer (customer-name, street-number, customer-city)\r\n\r\n&nbsp;\r\n\r\nFor a union operation <strong>r U s<\/strong> to be valid, two conditions must hold:\r\n<ul>\r\n \t<li>\u00a0The relation r and s must be of the same arity, i.e. they must have the same number of attributes.<\/li>\r\n \t<li>The domains of the ith attribute of r and the ith attribute of s must be the same for all i.<\/li>\r\n<\/ul>\r\n<strong>\u00a0 \u00a0 The set difference operation: - <\/strong>finds tuples in one relation but not in other.\r\n<ul>\r\n \t<li>It is denoted as \u2013<\/li>\r\n<\/ul>\r\n<strong>\u00a0 \u00a0 The Cartesian product operation: - <\/strong>allows combining information from two relations.\r\n<ul>\r\n \t<li>It is denoted as <strong>r X s<\/strong> where r and s are relations.<\/li>\r\n<\/ul>\r\nIf relation r has n1 tuples and relation s has n2 tuples then <strong>r X s<\/strong> has n1*n2 tuples.\r\n\r\n<\/div>\r\n<span style=\"text-align: initial;font-size: 1em\">\u00a0 \u00a0<strong>Example:<\/strong><\/span>\r\n<div>\r\n\r\n\u00a0 \u00a0 \u00a0Borrower (customer-name, loan-number)\r\n\r\nLoan (loan-number, branch-name, city, amount)\r\n\r\n&nbsp;\r\n\r\n<strong>The rename operation: - <\/strong>used to rename.\r\n<ul>\r\n \t<li>It is denoted as <strong>\u03c1<\/strong>.<\/li>\r\n<\/ul>\r\nE <strong>:<\/strong> relational algebra expression\r\n\r\n&nbsp;\r\n\r\n\u03c1\u00a0 <strong>x (E): <\/strong>returns the result of expression E under the name x.\r\n\r\n<strong>\u00a0<\/strong>\r\n\r\n\u03c1\u00a0\u00a0 <strong>x (A1, A2, A3\u2026 An) (E): <\/strong>returns the result of expression E under the name x with attributes renamed to A1, A2, A3\u2026 An.\r\n\r\n<strong>\u00a0<\/strong>\r\n\r\n<strong>The set intersection operation: - <\/strong>finds tuples in both the relations.\r\n<ul>\r\n \t<li>It is denoted as \u2229.<\/li>\r\n<\/ul>\r\n<strong>\u00a0 \u00a0 Example:<\/strong>\r\n\r\n&nbsp;\r\n\r\nBorrower (customer-name, loan-number)\r\n\r\nDepositor (customer-name, account-number)\r\n\r\nCustomer (customer-name, street-number, customer-city)\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>The natural join operation: - <\/strong>it is a binary operation and a combination of certain selections and a Cartesian product into one operation.<\/p>\r\n\r\n<ul>\r\n \t<li>\u00a0It is denoted as |X| .<\/li>\r\n \t<li>It is associative.<\/li>\r\n<\/ul>\r\nIt forms a Cartesian product of its two arguments.\r\n\r\nThen performs a selection forcing equality on those attributes those appear in both the relations.\r\n\r\nAnd finally removes duplicates attributes.\r\n\r\n&nbsp;\r\n\r\nr(R): r is a relation with attributes R.\r\n\r\ns(S): s is a relation with attributes S.\r\n\r\nIf R \u2229 S = \u0424 i.e. they have no attributes in common then <strong>r |X| s = r X s<\/strong>\r\n\r\n&nbsp;\r\n\r\n<strong>The division \/ quotient operation: -<\/strong>\r\n<ul>\r\n \t<li>It is denoted as \u00f7. Letr(R) and s(S) be relations<\/li>\r\n<\/ul>\r\n<\/div>\r\n<p style=\"text-align: justify\"><strong style=\"text-align: initial;font-size: 1em\">\u00a0 \u00a0 r \u00f7 s: - <\/strong><span style=\"text-align: initial;font-size: 1em\">the result consists of the restrictions of tuples in r to the attribute names unique to R, i.e. in the Header of r but not in the Header of s, for which it holds that all their combinations with tuples in s are present in r.<\/span><\/p>\r\n\r\n<div>\r\n\r\n<strong>\u00a0 \u00a0 Extended Relational Algebra Operations<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>GENERALIZED PROJECTION: - <\/strong>It extends the projection operation by allowing arithmetic functions to be used in projection list.<\/p>\r\n\u03a0\u00a0 <strong>F1,F2 \u2026 Fn <\/strong><strong>(E)<\/strong>\r\n\r\nWhere E: relational algebra expression\r\n\r\nFi: arithmetic expression\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>AGGREGATE FUNCTION:-<\/strong>It takes a collection of values and returns a single value as a result.<\/p>\r\nLimitations Of Relational Algebra\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">Although relational algebra seems powerful enough for most practical purposes, there are some simple and natural operators on relations which cannot be expressed by relational algebra. The transitive closure of a binary relation is one of them.<\/p>\r\n&nbsp;\r\n\r\n<strong>Relational Algebra Implemented In SQL<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">SQL (Structured query Language) is the most popular computer language used to create, modify, retrieve data from relational database management system.The basic structure of an SQL expression consists of three clauses:<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>SELECT: - <\/strong>This clause corresponds to the projection operation of the relational algebra. It is used to list the attributes of the result of a query.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>FROM: <\/strong>-It corresponds to the Cartesian product operation of the relational algebra. It lists the relations scanned in the evaluation of an expression.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\"><strong>WHERE<\/strong>: - This clause corresponds to selection predicate of relational algebra. It consists of a predicate involving attributes of the relations that appear in the FROM clause.<\/p>\r\n&nbsp;\r\n\r\nSQL QUERY FORM:\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">Select A1, A2\u2026.An<\/span>\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">From r1, r2\u2026rm<\/span>\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">Where P<\/span>\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">Ai : attribute<\/span>\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">Ri : relation<\/span>\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">P : predicate<\/span>\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">SELECT clause- specifies the table columns retrieved.<\/span>\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">FROM clause- specifies the tables to be accessed.<\/span>\r\n\r\n<span style=\"text-align: initial;font-size: 1em\">WHERE clause- which rows in the FROM tables to use.<\/span>\r\n\r\n<\/div>\r\n<strong>\u00a0 \u00a0Joining Tables<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">The FROM clause allows more than 1 table in its list. The rows from one table must be correlated with the rows of the others. This correlation is known as joining.<\/p>\r\n&nbsp;\r\n\r\n<strong>Set Operations<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">UNION, INTERSECT and EXCEPT operations can be done in SQL corresponding to their operations U, \u2229 and \u2013 in relational algebra only if the domains of the attributes of the relations match and the relations have same arity i.e same number of attributes.<\/p>\r\n<img class=\"size-full wp-image-62 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-14.png\" alt=\"\" width=\"631\" height=\"313\" \/>\r\n\r\n<\/div>","rendered":"<p style=\"text-align: justify\"><strong>Relational Algebra<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>An algebra is a formal structure consisting of <em>sets<\/em> and <em>operations<\/em> on those sets.<\/p>\n<p>Relational algebra is a formal system for manipulating relations.<\/p>\n<ul>\n<li>Operands of this algebra are relations.<\/li>\n<li style=\"text-align: justify\">Operations of this algebra include the usual set operations (since relations are sets of tuples), and special operations defined for relations selection<\/li>\n<li>projection<\/li>\n<li>join<\/li>\n<\/ul>\n<p style=\"text-align: center\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-59 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-11.png\" alt=\"\" width=\"662\" height=\"373\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-11.png 662w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-11-300x169.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-11-65x37.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-11-225x127.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-11-350x197.png 350w\" sizes=\"auto, (max-width: 662px) 100vw, 662px\" \/><\/p>\n<p>&nbsp;<\/p>\n<div>\n<p><strong>\u00a0<\/strong><\/p>\n<p style=\"text-align: justify\">A <em>predicate<\/em> is a boolean expression whose operators are the logical connectives (and, or, not) and arithmetic comparisons (LT, LE, GT, GE, EQ, NE), an<\/p>\n<p style=\"text-align: center\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-60 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-12.png\" alt=\"\" width=\"429\" height=\"136\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-12.png 429w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-12-300x95.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-12-65x21.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-12-225x71.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-12-350x111.png 350w\" sizes=\"auto, (max-width: 429px) 100vw, 429px\" \/><\/p>\n<p style=\"text-align: center\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-61 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-13.png\" alt=\"\" width=\"666\" height=\"376\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-13.png 666w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-13-300x169.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-13-65x37.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-13-225x127.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-13-350x198.png 350w\" sizes=\"auto, (max-width: 666px) 100vw, 666px\" \/><\/p>\n<div>\n<p><strong>\u00a0 \u00a0Implementing Set Operations<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>To implement R1 U R2 (while eliminating duplicates) we can<\/p>\n<\/div>\n<ul>\n<li><span style=\"text-align: initial;font-size: 1em\">sort R1 in O(N log N)<\/span><\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">sort R2 in O(M log M)<\/span><\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">merge R1 and R2 in O(N M)<\/span><\/li>\n<\/ul>\n<div>\n<p>\u00a0 \u00a0If we allow duplicates in union (and remove them later) we can<\/p>\n<ul>\n<li>copy R1 to R3 in O(N)<\/li>\n<li>insert R2 in R3 in O(M)<\/li>\n<\/ul>\n<p>If we have an index and don&#8217;t want duplicates we can<\/p>\n<ul>\n<li>copy R1 to R3 in O(N)<\/li>\n<li>for each tuple in R2 (which is O(M))<\/li>\n<li>use index to lookup tuples in R1 with the same index value O(1)<\/li>\n<li>if R2 tuple equals some such R1 tuple, don&#8217;t add R2 tuple to R3<\/li>\n<\/ul>\n<p>Intersection and set difference have corresponding implementations.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Implementing Projection<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>To implement projection we must<\/p>\n<ul>\n<li>\u00a0process every tuple in the relation<\/li>\n<li>remove any duplicates that result To avoid duplicates we can<\/li>\n<li>sort the result and remove consecutive tuples that are equal<\/li>\n<li>requires time O(N log N) where N is the size of the original relation<\/li>\n<li>implement the result as a set<\/li>\n<li>set insertion guarantees no duplicates<\/li>\n<li>by using a hash table, insertion is O(1), so projection is O(N)<\/li>\n<\/ul>\n<p><strong>\u00a0 Implementing Selection<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>In the absence of an index we<\/p>\n<ul>\n<li>apply the predicate to every tuple in the relation<\/li>\n<li>insert matches in the resulting relation<\/li>\n<li>duplicates can&#8217;t occur<\/li>\n<li>take O(N) time<\/li>\n<\/ul>\n<p>Given an index, and a predicate that uses the index key, we<\/p>\n<ul>\n<li>Lookup tuples using the key<\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">evaluate only those tuples with the predicate<\/span><\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">take O(K) time, where K tuples match the key<\/span><\/li>\n<\/ul>\n<\/div>\n<div>\n<p><strong>\u00a0 \u00a0Implementing Join with Nested Loops<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">A <em>nested loop join<\/em> on relations R1 (with N domains) and R2 (with M domains), considers all |R1| x |R2| pairs of tuples.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>R3= join(R1,Ai,R2,Bj)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>for each tuple t in R1 do<\/strong><\/p>\n<p><strong>for each tuple s in R2 do<\/strong><\/p>\n<p><strong>if t.Ai = s.Bj then<\/strong><\/p>\n<p><strong>insert(R3, t.A1, t.A2, &#8230;, t.AN,<\/strong><\/p>\n<p><strong>s.B1, &#8230;, s.B(j-1), s.B(j 1), &#8230;, s.BM)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>This implementation takes time O(|R1|*|R2|).<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Index Join<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">An <em>index join<\/em> exploits the existence of an index for one of the domains used in the join to find matching tuples more quickly.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>R3= join(R1,Ai,R2,Bj)<\/strong><\/p>\n<p><strong>for each tuple t in R1 do<\/strong><\/p>\n<p><strong>for each tuple s in R2 at index(t.Ai) do<\/strong><\/p>\n<p><strong>insert(R3, t.A1, t.A2, &#8230;, t.AN,<\/strong><\/p>\n<p><strong>s.B1, &#8230;, s.B(j-1), s.B(j 1), &#8230;, s.BM)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>We could choose to use an index for R2, and reverse the order of the loops.<\/p>\n<p>The decision on which index to use depends on the number of tuples in each relation.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Sort Join<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">If we don&#8217;t have an index for a domain in the join, we can still improve on the nested-loop join using <em>sort join<\/em>.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>R3= join(R1,Ai,R2,Bj)<\/strong><\/p>\n<ul>\n<li>Merge the tuples of both relations into a single list<\/li>\n<li>list elements must identify the original relation<\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">Sort the list based on the value in the join domains Ai and Bj<\/span><\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">all tuples on the sorted list with a common value for the join domains are consecutive<\/span><\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">Pair all (consecutive) tuples from the two relations with the same value in the join domains<\/span><\/li>\n<\/ul>\n<\/div>\n<div>\n<p><strong>\u00a0 \u00a0Comparison of Join Implementations<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Assumptions<\/p>\n<ul>\n<li>Join R1 and R2 (on domain D) producing R3<\/li>\n<li>R1 has i tuples, R2 has j tuples<\/li>\n<li>|R3| = m, 0 &lt;= m &lt;= i * j<\/li>\n<li>Every implementation takes at least time O(m)<\/li>\n<\/ul>\n<p>Comparison<\/p>\n<ul>\n<li>Nested-loop join takes time O(i * j)<\/li>\n<li>Index join (using R2 index) takes time O(i m)<\/li>\n<li>lookup is O(1) for each tuple in R1<\/li>\n<li>at most O(m) tuples match<\/li>\n<li>Sort join takes time O(m (i j)log(i j))<\/li>\n<li>O(i j) to merge the tuples in R1 and R2<\/li>\n<li>O((i j) log (i j)) to sort the list<\/li>\n<li>O(m) to produce the output (0 &lt;= m &lt;= i*j)<\/li>\n<\/ul>\n<p><strong>\u00a0 \u00a0Expressing Queries in Relational Algebra<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Relational algebra is an unambiguous notation (or formalism) for expressing queries.<\/p>\n<p>Queries are simply expressions in relational algebra.<\/p>\n<p style=\"text-align: justify\">Expressions can be manipulated symbolically to produce simpler expressions according to the laws of relational algebra.<\/p>\n<p style=\"text-align: justify\">Expression simplification is an important query optimization technique, which can affect the running time of queries by an order of magnitude or more.<\/p>\n<ul>\n<li>early &#8220;selection&#8221; reduces the number of tuples<\/li>\n<li>early &#8220;projection&#8221; reduces the number of domains<\/li>\n<\/ul>\n<\/div>\n<p><strong style=\"text-align: initial;font-size: 1em\">\u00a0 \u00a0 Algebraic Laws for Join<\/strong><\/p>\n<div>\n<p>\u00a0 \u00a0 \u00a0 Commutativity (assuming order of columns doesn&#8217;t matter)<strong>\u00a0join(R1, Ai, R2, Bj) = join(R2, Bj, R1, Ai)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Nonassociativity<strong>\u00a0 join (join(R1, Ai, R2, Bj),Bj,R3,Ck)\u00a0<\/strong>is not the same as<strong>\u00a0 join (R1,Ai,join(R2, Bj, R3, Ck),Bj)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Algebraic Laws for Selection<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Commutativity<\/p>\n<p><strong>\u00a0 \u00a0select(select(R1,P1),P2) = select(select(R1,P2),P1)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Selection pushing<\/p>\n<ul>\n<li>if P contains attributes of R<\/li>\n<\/ul>\n<p><strong>\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 select(join(R,Ai,S,Bj),P) = join(select(R,P),Ai,S,Bj)<\/strong><\/p>\n<ul>\n<li>if P contains attributes of S<\/li>\n<\/ul>\n<p><strong>\u00a0 \u00a0 \u00a0selection (join(R,Ai,S,Bj),P) = join(R,Ai,select(S,P),Bj)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Selection Splitting (where P = A and B)<\/p>\n<p>&nbsp;<\/p>\n<p><strong>select(R,P) = select(select(R,A),B)<\/strong><\/p>\n<p><strong>select(R,P) = select(select(R,B),A)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Example: Selection Pushing and Splitting<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Consider the following 4 relation database<\/p>\n<ul>\n<li>CSG: Course-StudentID-Grade<\/li>\n<li>SNAP: StudentID-Name-Address-Phone<\/li>\n<li>CDH: Course-Day-Hour<\/li>\n<li>CR: Course-Room<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>Implement the query &#8220;Where is Amy at Noon on Monday?&#8221;<\/p>\n<p>Let P be (Name=&#8221;Amy&#8221; and Day=&#8221;Monday&#8221; and Hour=&#8221;Noon&#8221;)<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">We can use a brute-force approach that <em>joins<\/em> all the data in the relations into a single large relation, <em>selects <\/em>those tuples that meet the query criteria, and then isolates the answer field using<em> projection<\/em>.<\/p>\n<ul>\n<li>\u00a0R1 = join(CSG,SNAP)<\/li>\n<li>\u00a0R2 = join(R1,CDH)<\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">\u00a0R3 = join(R2,CR)<\/span><\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">\u00a0R4 = select(R3,P)<\/span><\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">\u00a0R5 = project(R4,Room)<\/span><\/li>\n<\/ul>\n<\/div>\n<div>\n<p>\u00a0 \u00a0 project(select(join(join(join(CSG,SNAP),CDH),CR),P),Room)<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Selection Pushing and Splitting (cont)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The selection uses only Name, Day, and Hour attributes (and not Course or Room), so we can push the selection inside the outermost join.<\/p>\n<ul>\n<li>R1 = join(CSG,SNAP)<\/li>\n<li>R2 = join(R1,CDH)<\/li>\n<li>R3 = select(R2,P)<\/li>\n<li>R4 = join(R3,CR)<\/li>\n<li>R5 = project(R4,Room)<\/li>\n<\/ul>\n<p style=\"text-align: justify\">\u00a0 \u00a0We cannot push selection further, because the predicate involves attributes from both operands of the next innermost join (R1,CDH).<\/p>\n<p>&nbsp;<\/p>\n<p>We can split the selection into two, one based on Name, and the other based on Day-Hour.<\/p>\n<ul>\n<li>\u00a0 R1 = join(CSG,SNAP)<\/li>\n<li>\u00a0 R2 = join(R1,CDH)<\/li>\n<li>\u00a0 R3 = select(R2,Day=&#8221;Monday&#8221; and Hour=&#8221;Noon&#8221;)<\/li>\n<li>\u00a0 R4 = select(R3,Name=&#8221;Amy&#8221;)<\/li>\n<li>\u00a0 R5 = join(R4,CR)<\/li>\n<li>\u00a0 R6 = project(R5,Room)<\/li>\n<\/ul>\n<p><strong>\u00a0 \u00a0Selection Pushing and Splitting (cont 2)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Now we can push the first selection inside the join, since it involves only attributes from the CDH relation.<\/p>\n<ul>\n<li>\u00a0R1 = join(CSG,SNAP)<\/li>\n<li>\u00a0R2 = select(CDH,Day=&#8221;Monday&#8221; and Hour=&#8221;Noon&#8221;)<\/li>\n<li>\u00a0R3 = join(R1,R2)<\/li>\n<li>\u00a0R4 = select(R3,Name=&#8221;Amy&#8221;)<\/li>\n<li>\u00a0R5 = join(R4,CR)<\/li>\n<li>\u00a0R6 = project(R5,Room)<\/li>\n<\/ul>\n<p style=\"text-align: justify\">\u00a0 Similarly we can push the second selection inside the preceding join, since it involves only attributes from R1 (ie, Name).<\/p>\n<ul>\n<li><span style=\"text-align: initial;font-size: 1em\">R1 = join(CSG,SNAP)<\/span><\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">R2 = select(CDH,Day=&#8221;Monday&#8221; and Hour=&#8221;Noon&#8221;)<\/span><\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">R3 = select(R1,Name=&#8221;Amy&#8221;)<\/span><\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">R4 = join(R2,R3)<\/span><\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">R5 = join(R4,CR)\u00a0<\/span><\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">R6 = project(R5,Room)<\/span><\/li>\n<\/ul>\n<\/div>\n<div>\n<p>\u00a0 \u00a0Continuing to push the second select inside the first join<\/p>\n<ul>\n<li>R1 = select(SNAP,Name=&#8221;Amy&#8221;)<\/li>\n<li>R2 = join(CSG,R1)<\/li>\n<li>R3 = select(CDH,Day=&#8221;Monday&#8221; and Hour=&#8221;Noon&#8221;)<\/li>\n<li>R4 = join(R2,R3)<\/li>\n<li>R5 = join(R4,CR)<\/li>\n<li>R6 = project(R5,Room)<\/li>\n<\/ul>\n<p><strong>\u00a0 \u00a0Algebraic Laws for Projection<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Projection pushing<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">To push a projection operation inside a join requires that the result of the projection contain the attributes used in the join.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>project(join(R,Ai,S,Bj),D1,D2,&#8230;Dn)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>In this case, we know that the domains in the projection will exist in the relation that results from the join.<\/p>\n<p>In performing projection first (on the two join relations)<\/p>\n<ul>\n<li>we should only project on those domains that exist in each of the two relations<\/li>\n<li>we must ensure that the join domains Ai and Bj exist in the resulting two relations Let PDR = {D|D domain in R, D in {D1&#8230;Dn}} U Ai<\/li>\n<\/ul>\n<p>Let PDS = {D|D domain in S, D in {D1&#8230;Dn}} U Bi<\/p>\n<p>&nbsp;<\/p>\n<p><strong>R1 = project(R,PDR)<\/strong><\/p>\n<p><strong>R2 = project(S,PDS)<\/strong><\/p>\n<p><strong>R3 = join(R1,Ai,R2,Bj) = project(join(R,Ai,S,Bj),D1,D2,&#8230;Dn)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Example: Projection Pushing<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Implement the query &#8220;Where is Amy at Noon on Monday?&#8221;<\/p>\n<ul>\n<li>R1 = select(SNAP,Name=&#8221;Amy&#8221;)<\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">R2 = join(CSG,R1)<\/span><\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">R3 = select(CDH,Day=&#8221;Monday&#8221; and Hour=&#8221;Noon&#8221;)<\/span><\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">R4 = join(R2,R3)<\/span><\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">R5 = join(R4,CR)\u00a0<\/span><\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">R6 = project(R5,Room)<\/span><\/li>\n<\/ul>\n<\/div>\n<div>\n<p>\u00a0 \u00a0 \u00a0This approach carries along unnecessary attributes every step of the way.<\/p>\n<ul>\n<li><span style=\"font-size: 1em\">R1 carries Address and Phone attributes<\/span><\/li>\n<li><span style=\"font-size: 1em\">R4 carries Grade attribute<\/span><\/li>\n<\/ul>\n<p>We use projection pushing to eliminate unnecessary attributes early in the implementation.<\/p>\n<ul>\n<li>R1 = select(SNAP,Name=&#8221;Amy&#8221;)<\/li>\n<li>R2 = join(CSG,R1)<\/li>\n<li>R3 = select(CDH,Day=&#8221;Monday&#8221; and Hour=&#8221;Noon&#8221;)<\/li>\n<li>R4 = join(R2,R3)<\/li>\n<li>R5 = project(CR, Course, Room)<\/li>\n<li>R6 = project(R4, Course)<\/li>\n<li>R7 = join(R5,R6)<\/li>\n<li>R8 = project(R7,Room)<\/li>\n<\/ul>\n<p>Note that R5 is unnecessary, since the domains in the projection are all the domains of CR.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Projection Pushing (cont)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Implement the query &#8220;Where is Amy at Noon on Monday?&#8221;<\/p>\n<ul>\n<li>R1 = select(SNAP,Name=&#8221;Amy&#8221;)<\/li>\n<li>R2 = join(CSG,R1)<\/li>\n<li>R3 = select(CDH,Day=&#8221;Monday&#8221; and Hour=&#8221;Noon&#8221;)<\/li>\n<li>R4 = join(R2,R3)<\/li>\n<li>R5 = project(R4, Course)<\/li>\n<li>R6 = join(CR,R5)<\/li>\n<li>R7 = project(R6,Room)<\/li>\n<\/ul>\n<p>We can continue pushing the projection on Course below the join for R4.<\/p>\n<ul>\n<li>R1 = select(SNAP,Name=&#8221;Amy&#8221;)<\/li>\n<li>R2 = join(CSG,R1)<\/li>\n<li>R3 = select(CDH,Day=&#8221;Monday&#8221; and Hour=&#8221;Noon&#8221;)<\/li>\n<li>R4 = project(R2,Course)<\/li>\n<li>R5 = project(R3,Course)<\/li>\n<li>R6 = join(R4,R5)<\/li>\n<li>R7 = join(CR,R6)<\/li>\n<li><span style=\"text-align: initial;font-size: 1em\">R8 = project(R7,Room)<\/span><\/li>\n<\/ul>\n<\/div>\n<div>\n<p><strong>\u00a0 Projection Pushing (cont2)<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>We can continue pushing the projection on Course for R4 below the join for R2.<\/p>\n<ul>\n<li>R1 = select(SNAP,Name=&#8221;Amy&#8221;)\\<\/li>\n<li>R2 = project(CSG,Course,StudentID)<\/li>\n<li>R3 = project(R1,StudentID)<\/li>\n<li>R4 = join(R2,R3)<\/li>\n<li>R5 = project(R4,Course)<\/li>\n<li>R6 = select(CDH,Day=&#8221;Monday&#8221; and Hour=&#8221;Noon&#8221;)<\/li>\n<li>R7 = project(R6,Course)<\/li>\n<li>R8 = join(R6,R7)<\/li>\n<li>R9 = join(CR,R8)<\/li>\n<li>R10 = project(R9,Room)<\/li>\n<\/ul>\n<p style=\"text-align: justify\">A <strong>query language<\/strong> is a language in which user requests information from the database. it can be categorized as either <strong>procedural<\/strong> or <strong>nonprocedural.<\/strong> In a procedural language the user instructs the system to do a sequence of operations on database to compute the desired result. In non procedural language the user describes the desired information without giving a specific procedure for obtaining that information.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The relational algebra is a procedural query language. It consists of a set of operations that take one or two relations as input and produces a new relation as output.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Fundamental Operations<\/strong><\/p>\n<ul>\n<li>SELECT<\/li>\n<li>PROJECT<\/li>\n<li>UNION<\/li>\n<li>SET DIFFERENCE<\/li>\n<li>CARTESIAN PRODUCT<\/li>\n<li>RENAME<\/li>\n<\/ul>\n<\/div>\n<div>\n<p style=\"text-align: justify\">Select and project operations are unary operation as they operate on a single relation.Union, set difference, Cartesian product and rename operations are binary operations as they operate on pairs of relations.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Other Operations<\/strong><\/p>\n<ul>\n<li>SET INTERSECTION<\/li>\n<li>NATURAL JOIN<\/li>\n<li>DIVISION<\/li>\n<li>ASSIGNMENT<\/li>\n<\/ul>\n<p style=\"text-align: justify\"><strong>\u00a0 \u00a0The select operation<\/strong>: &#8211; to identify a set of tuples which is a part of a relation and to extract only these tuples out. The select operation selects tuples that satisfy a given predicate or condition.<\/p>\n<ul>\n<li>It is a unary operation defined on a single relation.<\/li>\n<li>It is denoted as <strong>\u03c3<\/strong>.<\/li>\n<\/ul>\n<p style=\"text-align: justify\"><strong>\u00a0 \u00a0The union operation: <\/strong>&#8211; is used when we need some attributes that appear in either or both of the two relations.<\/p>\n<ul>\n<li>It is denoted as <strong>U<\/strong>.<\/li>\n<\/ul>\n<p><strong>\u00a0 \u00a0example:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Borrower (customer-name, loan-number)<\/p>\n<p>Depositor (customer-name, account-number)<\/p>\n<p>Customer (customer-name, street-number, customer-city)<\/p>\n<p>&nbsp;<\/p>\n<p>For a union operation <strong>r U s<\/strong> to be valid, two conditions must hold:<\/p>\n<ul>\n<li>\u00a0The relation r and s must be of the same arity, i.e. they must have the same number of attributes.<\/li>\n<li>The domains of the ith attribute of r and the ith attribute of s must be the same for all i.<\/li>\n<\/ul>\n<p><strong>\u00a0 \u00a0 The set difference operation: &#8211; <\/strong>finds tuples in one relation but not in other.<\/p>\n<ul>\n<li>It is denoted as \u2013<\/li>\n<\/ul>\n<p><strong>\u00a0 \u00a0 The Cartesian product operation: &#8211; <\/strong>allows combining information from two relations.<\/p>\n<ul>\n<li>It is denoted as <strong>r X s<\/strong> where r and s are relations.<\/li>\n<\/ul>\n<p>If relation r has n1 tuples and relation s has n2 tuples then <strong>r X s<\/strong> has n1*n2 tuples.<\/p>\n<\/div>\n<p><span style=\"text-align: initial;font-size: 1em\">\u00a0 \u00a0<strong>Example:<\/strong><\/span><\/p>\n<div>\n<p>\u00a0 \u00a0 \u00a0Borrower (customer-name, loan-number)<\/p>\n<p>Loan (loan-number, branch-name, city, amount)<\/p>\n<p>&nbsp;<\/p>\n<p><strong>The rename operation: &#8211; <\/strong>used to rename.<\/p>\n<ul>\n<li>It is denoted as <strong>\u03c1<\/strong>.<\/li>\n<\/ul>\n<p>E <strong>:<\/strong> relational algebra expression<\/p>\n<p>&nbsp;<\/p>\n<p>\u03c1\u00a0 <strong>x (E): <\/strong>returns the result of expression E under the name x.<\/p>\n<p><strong>\u00a0<\/strong><\/p>\n<p>\u03c1\u00a0\u00a0 <strong>x (A1, A2, A3\u2026 An) (E): <\/strong>returns the result of expression E under the name x with attributes renamed to A1, A2, A3\u2026 An.<\/p>\n<p><strong>\u00a0<\/strong><\/p>\n<p><strong>The set intersection operation: &#8211; <\/strong>finds tuples in both the relations.<\/p>\n<ul>\n<li>It is denoted as \u2229.<\/li>\n<\/ul>\n<p><strong>\u00a0 \u00a0 Example:<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p>Borrower (customer-name, loan-number)<\/p>\n<p>Depositor (customer-name, account-number)<\/p>\n<p>Customer (customer-name, street-number, customer-city)<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>The natural join operation: &#8211; <\/strong>it is a binary operation and a combination of certain selections and a Cartesian product into one operation.<\/p>\n<ul>\n<li>\u00a0It is denoted as |X| .<\/li>\n<li>It is associative.<\/li>\n<\/ul>\n<p>It forms a Cartesian product of its two arguments.<\/p>\n<p>Then performs a selection forcing equality on those attributes those appear in both the relations.<\/p>\n<p>And finally removes duplicates attributes.<\/p>\n<p>&nbsp;<\/p>\n<p>r(R): r is a relation with attributes R.<\/p>\n<p>s(S): s is a relation with attributes S.<\/p>\n<p>If R \u2229 S = \u0424 i.e. they have no attributes in common then <strong>r |X| s = r X s<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p><strong>The division \/ quotient operation: &#8211;<\/strong><\/p>\n<ul>\n<li>It is denoted as \u00f7. Letr(R) and s(S) be relations<\/li>\n<\/ul>\n<\/div>\n<p style=\"text-align: justify\"><strong style=\"text-align: initial;font-size: 1em\">\u00a0 \u00a0 r \u00f7 s: &#8211; <\/strong><span style=\"text-align: initial;font-size: 1em\">the result consists of the restrictions of tuples in r to the attribute names unique to R, i.e. in the Header of r but not in the Header of s, for which it holds that all their combinations with tuples in s are present in r.<\/span><\/p>\n<div>\n<p><strong>\u00a0 \u00a0 Extended Relational Algebra Operations<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>GENERALIZED PROJECTION: &#8211; <\/strong>It extends the projection operation by allowing arithmetic functions to be used in projection list.<\/p>\n<p>\u03a0\u00a0 <strong>F1,F2 \u2026 Fn <\/strong><strong>(E)<\/strong><\/p>\n<p>Where E: relational algebra expression<\/p>\n<p>Fi: arithmetic expression<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>AGGREGATE FUNCTION:-<\/strong>It takes a collection of values and returns a single value as a result.<\/p>\n<p>Limitations Of Relational Algebra<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">Although relational algebra seems powerful enough for most practical purposes, there are some simple and natural operators on relations which cannot be expressed by relational algebra. The transitive closure of a binary relation is one of them.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Relational Algebra Implemented In SQL<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">SQL (Structured query Language) is the most popular computer language used to create, modify, retrieve data from relational database management system.The basic structure of an SQL expression consists of three clauses:<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>SELECT: &#8211; <\/strong>This clause corresponds to the projection operation of the relational algebra. It is used to list the attributes of the result of a query.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>FROM: <\/strong>-It corresponds to the Cartesian product operation of the relational algebra. It lists the relations scanned in the evaluation of an expression.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\"><strong>WHERE<\/strong>: &#8211; This clause corresponds to selection predicate of relational algebra. It consists of a predicate involving attributes of the relations that appear in the FROM clause.<\/p>\n<p>&nbsp;<\/p>\n<p>SQL QUERY FORM:<\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">Select A1, A2\u2026.An<\/span><\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">From r1, r2\u2026rm<\/span><\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">Where P<\/span><\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">Ai : attribute<\/span><\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">Ri : relation<\/span><\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">P : predicate<\/span><\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">SELECT clause- specifies the table columns retrieved.<\/span><\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">FROM clause- specifies the tables to be accessed.<\/span><\/p>\n<p><span style=\"text-align: initial;font-size: 1em\">WHERE clause- which rows in the FROM tables to use.<\/span><\/p>\n<\/div>\n<p><strong>\u00a0 \u00a0Joining Tables<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">The FROM clause allows more than 1 table in its list. The rows from one table must be correlated with the rows of the others. This correlation is known as joining.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Set Operations<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">UNION, INTERSECT and EXCEPT operations can be done in SQL corresponding to their operations U, \u2229 and \u2013 in relational algebra only if the domains of the attributes of the relations match and the relations have same arity i.e same number of attributes.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-62 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-14.png\" alt=\"\" width=\"631\" height=\"313\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-14.png 631w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-14-300x149.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-14-65x32.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-14-225x112.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-14-350x174.png 350w\" sizes=\"auto, (max-width: 631px) 100vw, 631px\" \/><\/p>\n<\/div>\n","protected":false},"author":4,"menu_order":5,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":["dr-r-baskaran"],"pb_section_license":""},"chapter-type":[],"contributor":[58],"license":[],"class_list":["post-58","chapter","type-chapter","status-publish","hentry","contributor-dr-r-baskaran"],"part":3,"_links":{"self":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters\/58","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/users\/4"}],"version-history":[{"count":6,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters\/58\/revisions"}],"predecessor-version":[{"id":295,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters\/58\/revisions\/295"}],"part":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/parts\/3"}],"metadata":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters\/58\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/media?parent=58"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapter-type?post=58"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/contributor?post=58"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/license?post=58"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}