{"id":172,"date":"2018-07-19T05:39:42","date_gmt":"2018-07-19T05:39:42","guid":{"rendered":"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/?post_type=chapter&#038;p=172"},"modified":"2018-07-19T05:42:19","modified_gmt":"2018-07-19T05:42:19","slug":"deductive-databases","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/chapter\/deductive-databases\/","title":{"rendered":"Deductive Databases"},"content":{"raw":"<ul>\r\n \t<li>SQL-92 cannot express some queries:<\/li>\r\n \t<li>Are we running low on any parts needed to build a ZX600 sports car?<\/li>\r\n \t<li>What is the total component and assembly cost to build a ZX600 at today's part prices?<\/li>\r\n \t<li>Can we extend the query language to cover such queries?<\/li>\r\n \t<li>Yes, by adding recursion.<\/li>\r\n<\/ul>\r\n<strong>What is a deductive database system?<\/strong>\r\n\r\n&nbsp;\r\n<p style=\"text-align: justify\">A deductive database can be defined as an advanced database augmented with an inference system.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: center\"><img class=\"size-full wp-image-173 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-73.png\" alt=\"\" width=\"599\" height=\"116\" \/><\/p>\r\n&nbsp;\r\n<p style=\"text-align: justify\">\u00a0By evaluating rules against facts, new facts can be derived, which in turn can be used to answer queries. It makes a database system more powerful.<\/p>\r\n<p style=\"text-align: justify\"><strong>Some basic concepts from logic<\/strong><\/p>\r\n<p style=\"text-align: justify\">To understand the deductive database system well, some basic concepts from mathematical logic are needed.<\/p>\r\n\r\n<ul style=\"text-align: justify\">\r\n \t<li>- term<\/li>\r\n \t<li>- n-ary predicate<\/li>\r\n \t<li>- literal<\/li>\r\n \t<li>- (well-formed) formula<\/li>\r\n \t<li>- clause and Horn-clause<\/li>\r\n \t<li>- facts<\/li>\r\n \t<li>- logic program<\/li>\r\n<\/ul>\r\n<ul style=\"text-align: justify\">\r\n \t<li>Term<\/li>\r\n<\/ul>\r\n<p style=\"text-align: justify\">\u00a0 \u00a0 \u00a0A term is a constant, a variable or an expression of the form <em>f<\/em>(t1, t2, ..., tn), where t1, t2, ..., tn are terms and <em>f<\/em> is a function symbol.<\/p>\r\n<p style=\"text-align: justify\">Example: a, b, c, <em>f<\/em>(a, b),<\/p>\r\n\r\n<ul style=\"text-align: justify\">\r\n \t<li>n-ary predicate<\/li>\r\n<\/ul>\r\n<p style=\"text-align: justify\">\u00a0 \u00a0 An n-ary predicate symbol is a symbol <em>p<\/em> appearing in an expression of the form <em>p<\/em>(t1, t2, ..., tn), called an atom, where t1, t2, ..., tn are terms. <em>p<\/em>(t1, t2, ..., tn) can only evaluate to <em>true<\/em> or <em>false<\/em>.<\/p>\r\n<p style=\"text-align: justify\">Example: <em>p<\/em>(a, b), <em>q<\/em>(a, <em>f<\/em>(a, b)), <em>p<\/em>(<em>x<\/em>, <em>y<\/em>)<\/p>\r\n\r\n<ul style=\"text-align: justify\">\r\n \t<li>Clause<\/li>\r\n<\/ul>\r\n<p style=\"text-align: justify\">\u00a0 \u00a0-A clause is an expression of the following form:<\/p>\r\n<p style=\"text-align: justify\">\u00d8A1 \u00da \u00d8A2 \u00da ... \u00da \u00d8An \u00da B1 \u00da ... \u00da Bm<\/p>\r\n<p style=\"text-align: justify\">where Ai and Bj are atoms.<\/p>\r\n<p style=\"text-align: justify\">-The above expression can be written in the following equivalent form:<\/p>\r\n<p style=\"text-align: justify\">B1 \u00da ... \u00da Bm \u00ac A1 \u00d9 ... \u00d9 An<\/p>\r\n<p style=\"text-align: justify\">or<\/p>\r\n<p style=\"text-align: justify\">B1, ..., Bm \u00ac A1 , ..., An<\/p>\r\n\r\n<ul>\r\n \t<li>Clause<\/li>\r\n<\/ul>\r\n<p style=\"text-align: center\"><img class=\"size-full wp-image-174 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-74.png\" alt=\"\" width=\"573\" height=\"228\" \/><\/p>\r\n\r\n<ul>\r\n \t<li>Horn clause<\/li>\r\n<\/ul>\r\nA Horn clause is a clause with the head containing only one positive atom.\r\n\r\nBm \u00ac A1 , ..., An\r\n<ul>\r\n \t<li>Fact<\/li>\r\n<\/ul>\r\nA fact is a special Horn clause of the following form:\r\n\r\nB \u00ac with all variables in B being instantiated.\r\n\r\n(B \u00ac can be simply written as B.)\r\n<ul>\r\n \t<li>logic program<\/li>\r\n<\/ul>\r\nA logic program is a set of Horn clauses.\r\n\r\n&nbsp;\r\n<p style=\"text-align: center\"><img class=\"size-full wp-image-175 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-75.png\" alt=\"\" width=\"913\" height=\"374\" \/><\/p>\r\n\r\n<ul>\r\n \t<li style=\"text-align: justify\">SQL queries can be read as follows:<\/li>\r\n \t<li style=\"text-align: justify\">\u201cIf some tuples exist in the From tables that satisfy the Where conditions,then the Select tuple is in the answer.\u201d<\/li>\r\n \t<li style=\"text-align: justify\">Datalog is a query language that has the same if-then flavor:<\/li>\r\n \t<li style=\"text-align: justify\">New: The answer table can appear in the From clause, i.e., be defined recursively.<\/li>\r\n \t<li style=\"text-align: justify\">Prolog style syntax is commonly used.<\/li>\r\n<\/ul>\r\n<p style=\"text-align: center\"><img class=\"size-full wp-image-176 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-76.png\" alt=\"\" width=\"857\" height=\"390\" \/><\/p>\r\n\r\n<ul>\r\n \t<li>Find the components of a trike?<\/li>\r\n \t<li>We can write a relational algebra query to compute the answer on <strong><em>the given instance of Assembly<\/em>.<\/strong><\/li>\r\n \t<li>But there is no R.A. (or SQL-92) query that computes the answer on <strong><em>all Assembly instances<\/em><\/strong>.<\/li>\r\n \t<li>Intuitively, we must join Assembly with itself to deduce that trike contains spoke and tire.<\/li>\r\n \t<li>Takes us one level down Assembly hierarchy.<\/li>\r\n \t<li>To find components that are one level deeper (e.g., rim), need another join.<\/li>\r\n \t<li>To find all components, need as many joins as there are levels in the given instance!<\/li>\r\n \t<li>For any relational algebra expression, we can create an Assembly instance for which some answers are not computed by including more levels than the number of joins in the expression!<\/li>\r\n<\/ul>\r\n<p style=\"text-align: center\"><img class=\"size-full wp-image-177 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-77.png\" alt=\"\" width=\"770\" height=\"183\" \/><\/p>\r\nCan read the second rule as follows:\r\n\r\n&nbsp;\r\n\r\n\u201c<strong>For all<\/strong> values of Part, Subpt and Qty,\r\n\r\n<strong>if <\/strong>there is a tuple (Part, Part2, Qty) in Assembly<strong> and <\/strong>a tuple (Part2, Subpt) in Comp,\r\n\r\n<strong>then <\/strong>there must be a tuple (Part, Subpt) in Comp.\u201d\r\n<ul>\r\n \t<li style=\"text-align: justify\">Each rule is a <strong><em>template<\/em>:<\/strong> by assigning constants to the variables in such a way that each body \u201cliteral\u201d is a tuple in the corresponding relation, we identify a tuple that must be in the head relation.<\/li>\r\n \t<li style=\"text-align: justify\">By setting Part=trike, Subpt=wheel, Qty=3 in the first rule, we can deduce that the tuple &lt;trike,wheel&gt; is in the relation Comp.<\/li>\r\n \t<li style=\"text-align: justify\">This is called an <strong>inference<\/strong> using the rule.<\/li>\r\n \t<li style=\"text-align: justify\">Given a set of tuples, we <strong>apply<\/strong> the rule by making all possible inferences with these tuples in the body.<\/li>\r\n<\/ul>\r\n<p style=\"text-align: justify\">For any instance of Assembly, we can compute all Comp tuples by repeatedly applying the two rules. (Actually, we can apply Rule 1 just once, then apply Rule 2 repeatedly.)<\/p>\r\n&nbsp;\r\n<p style=\"text-align: center\"><img class=\"alignnone size-full wp-image-178\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-78.png\" alt=\"\" width=\"615\" height=\"314\" \/><\/p>\r\n<p style=\"text-align: justify\">Don\u2019t let the rule syntax of Datalog fool you: a collection of Datalog rules can be rewritten in SQL syntax, if recursion is allowed.<\/p>\r\n&nbsp;\r\n\r\n<strong>WITH RECURSIVE <\/strong><strong>Comp(Part, Subpt)<\/strong><strong> AS<\/strong>\r\n\r\n<strong>(<\/strong><strong>SELECT<\/strong> <strong>A1.Part, A1.Subpt<\/strong> <strong>FROM<\/strong> <strong>Assembly A1<\/strong><strong>)<\/strong>\r\n\r\n<strong>UNION<\/strong>\r\n\r\n<strong>(<\/strong><strong>SELECT<\/strong> <strong>A2.Part, C1.Subpt<\/strong>\r\n\r\n<strong>FROM <\/strong><strong>Assembly A2, Comp C1<\/strong>\r\n\r\n<strong>WHERE <\/strong><strong>A2.Subpt=C1.Part<\/strong><strong>)<\/strong>\r\n\r\n<strong>SELECT <\/strong><strong>*<\/strong><strong> FROM <\/strong><strong>Comp C2<\/strong>\r\n\r\n&nbsp;\r\n<ul>\r\n \t<li style=\"text-align: justify\">Let f be a function that takes values from domain D and returns values from D. A value v in D is a fixpoint of f if f(v)=v.<\/li>\r\n \t<li style=\"text-align: justify\">Consider the fn <em>double+<\/em>, which is applied to a set of integers and returns a set of integers (I.e., D is the set of all sets of integers).<\/li>\r\n \t<li style=\"text-align: justify\">E.g., <em>double+({1,2,5})={2,4,10} Union {1,2,5}<\/em><\/li>\r\n \t<li style=\"text-align: justify\">The set of all integers is a fixpoint of <em>double+.<\/em><\/li>\r\n \t<li style=\"text-align: justify\">The set of all even integers is another fixpoint of <em>double+<\/em>; it is smaller than the first fixpoint.<\/li>\r\n \t<li style=\"text-align: justify\">The least fixpoint of a function \u201c<em>f\u201d<\/em> is a fixpoint \u201c<em>v\u201d<\/em> of \u201c<em>f\u201d<\/em> such that every other fixpoint of \u201c<em>f\u201d<\/em> is smaller than or equal to \u201c<em>v\u201d<\/em>.<\/li>\r\n \t<li style=\"text-align: justify\">In general, there may be no least fixpoint (we could have two minimal fixpoints, neither of which is smaller than the other).<\/li>\r\n \t<li style=\"text-align: justify\">If we think of a Datalog program as a function that is applied to a set of tuples and returns another set of tuples, this function always has a least fixpoint.<\/li>\r\n<\/ul>\r\n<strong>\u00a0 \u00a0 Big(Part) :- Assembly(Part, Subpt, Qty), Qty &gt;2, <\/strong><strong>not<\/strong><strong> Small(Part).<\/strong>\r\n\r\n<strong>Small(Part) :- Assembly(Part, Subpt, Qty), <\/strong><strong>not<\/strong><strong> Big(Part).<\/strong>\r\n<ul>\r\n \t<li style=\"text-align: justify\">If rules contain <strong>not<\/strong> there may not be a least fixpoint. Consider the Assembly instance; trike is the only part that has 3 or more copies of some subpart. Intuitively, it should be in Big, and it will be if we apply Rule 1 first.<\/li>\r\n \t<li style=\"text-align: justify\">But we have Small(trike) if Rule 2 is applied first!<\/li>\r\n \t<li style=\"text-align: justify\">There are two minimal fixpoints for this program: Big is empty in one, and contains trike in the other (and all other parts are in Small in both fixpoints).<\/li>\r\n \t<li style=\"text-align: justify\">T depends on S if some rule with T in the head contains S or (recursively) some predicate that depends on S, in the body.<\/li>\r\n \t<li style=\"text-align: justify\">Stratified program: If T depends on <strong>not<\/strong> S, then S cannot depend on T (or <strong>not<\/strong> T).<\/li>\r\n \t<li style=\"text-align: justify\">If a program is stratified, the tables in the program can be partitioned into strata:<\/li>\r\n \t<li style=\"text-align: justify\">Stratum 0: All database tables.<\/li>\r\n \t<li style=\"text-align: justify\">Stratum I: Tables defined in terms of tables in Stratum I and lower strata.<\/li>\r\n \t<li style=\"text-align: justify\">If T depends on <strong>not<\/strong> S, S is in lower stratum than T.<\/li>\r\n<\/ul>\r\n<p style=\"text-align: justify\">\u00a0 \u00a0 \u00a0 Repeated inferences: When recursive rules are repeatedly applied in the na\u00efve way, we make the same inferences in several iterations.<\/p>\r\n<p style=\"text-align: justify\">Unnecessary\u00a0 inferences:\u00a0 Also,\u00a0 if\u00a0 we\u00a0 just\u00a0 want\u00a0 to\u00a0 find\u00a0 the components\u00a0 of\u00a0 a\u00a0 particular\u00a0 part,\u00a0 say\u00a0 wheel,\u00a0 computing\u00a0 the fixpoint of the Comp program and then selecting tuples with wheel in the first column is wasteful, in that we compute many irrelevant facts.<\/p>\r\n&nbsp;\r\n<p style=\"text-align: center\"><img class=\"size-full wp-image-182 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-79.png\" alt=\"\" width=\"640\" height=\"316\" \/><\/p>","rendered":"<ul>\n<li>SQL-92 cannot express some queries:<\/li>\n<li>Are we running low on any parts needed to build a ZX600 sports car?<\/li>\n<li>What is the total component and assembly cost to build a ZX600 at today&#8217;s part prices?<\/li>\n<li>Can we extend the query language to cover such queries?<\/li>\n<li>Yes, by adding recursion.<\/li>\n<\/ul>\n<p><strong>What is a deductive database system?<\/strong><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">A deductive database can be defined as an advanced database augmented with an inference system.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-173 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-73.png\" alt=\"\" width=\"599\" height=\"116\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-73.png 599w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-73-300x58.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-73-65x13.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-73-225x44.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-73-350x68.png 350w\" sizes=\"auto, (max-width: 599px) 100vw, 599px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: justify\">\u00a0By evaluating rules against facts, new facts can be derived, which in turn can be used to answer queries. It makes a database system more powerful.<\/p>\n<p style=\"text-align: justify\"><strong>Some basic concepts from logic<\/strong><\/p>\n<p style=\"text-align: justify\">To understand the deductive database system well, some basic concepts from mathematical logic are needed.<\/p>\n<ul style=\"text-align: justify\">\n<li>&#8211; term<\/li>\n<li>&#8211; n-ary predicate<\/li>\n<li>&#8211; literal<\/li>\n<li>&#8211; (well-formed) formula<\/li>\n<li>&#8211; clause and Horn-clause<\/li>\n<li>&#8211; facts<\/li>\n<li>&#8211; logic program<\/li>\n<\/ul>\n<ul style=\"text-align: justify\">\n<li>Term<\/li>\n<\/ul>\n<p style=\"text-align: justify\">\u00a0 \u00a0 \u00a0A term is a constant, a variable or an expression of the form <em>f<\/em>(t1, t2, &#8230;, tn), where t1, t2, &#8230;, tn are terms and <em>f<\/em> is a function symbol.<\/p>\n<p style=\"text-align: justify\">Example: a, b, c, <em>f<\/em>(a, b),<\/p>\n<ul style=\"text-align: justify\">\n<li>n-ary predicate<\/li>\n<\/ul>\n<p style=\"text-align: justify\">\u00a0 \u00a0 An n-ary predicate symbol is a symbol <em>p<\/em> appearing in an expression of the form <em>p<\/em>(t1, t2, &#8230;, tn), called an atom, where t1, t2, &#8230;, tn are terms. <em>p<\/em>(t1, t2, &#8230;, tn) can only evaluate to <em>true<\/em> or <em>false<\/em>.<\/p>\n<p style=\"text-align: justify\">Example: <em>p<\/em>(a, b), <em>q<\/em>(a, <em>f<\/em>(a, b)), <em>p<\/em>(<em>x<\/em>, <em>y<\/em>)<\/p>\n<ul style=\"text-align: justify\">\n<li>Clause<\/li>\n<\/ul>\n<p style=\"text-align: justify\">\u00a0 \u00a0-A clause is an expression of the following form:<\/p>\n<p style=\"text-align: justify\">\u00d8A1 \u00da \u00d8A2 \u00da &#8230; \u00da \u00d8An \u00da B1 \u00da &#8230; \u00da Bm<\/p>\n<p style=\"text-align: justify\">where Ai and Bj are atoms.<\/p>\n<p style=\"text-align: justify\">-The above expression can be written in the following equivalent form:<\/p>\n<p style=\"text-align: justify\">B1 \u00da &#8230; \u00da Bm \u00ac A1 \u00d9 &#8230; \u00d9 An<\/p>\n<p style=\"text-align: justify\">or<\/p>\n<p style=\"text-align: justify\">B1, &#8230;, Bm \u00ac A1 , &#8230;, An<\/p>\n<ul>\n<li>Clause<\/li>\n<\/ul>\n<p style=\"text-align: center\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-174 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-74.png\" alt=\"\" width=\"573\" height=\"228\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-74.png 573w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-74-300x119.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-74-65x26.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-74-225x90.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-74-350x139.png 350w\" sizes=\"auto, (max-width: 573px) 100vw, 573px\" \/><\/p>\n<ul>\n<li>Horn clause<\/li>\n<\/ul>\n<p>A Horn clause is a clause with the head containing only one positive atom.<\/p>\n<p>Bm \u00ac A1 , &#8230;, An<\/p>\n<ul>\n<li>Fact<\/li>\n<\/ul>\n<p>A fact is a special Horn clause of the following form:<\/p>\n<p>B \u00ac with all variables in B being instantiated.<\/p>\n<p>(B \u00ac can be simply written as B.)<\/p>\n<ul>\n<li>logic program<\/li>\n<\/ul>\n<p>A logic program is a set of Horn clauses.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-175 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-75.png\" alt=\"\" width=\"913\" height=\"374\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-75.png 913w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-75-300x123.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-75-768x315.png 768w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-75-65x27.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-75-225x92.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-75-350x143.png 350w\" sizes=\"auto, (max-width: 913px) 100vw, 913px\" \/><\/p>\n<ul>\n<li style=\"text-align: justify\">SQL queries can be read as follows:<\/li>\n<li style=\"text-align: justify\">\u201cIf some tuples exist in the From tables that satisfy the Where conditions,then the Select tuple is in the answer.\u201d<\/li>\n<li style=\"text-align: justify\">Datalog is a query language that has the same if-then flavor:<\/li>\n<li style=\"text-align: justify\">New: The answer table can appear in the From clause, i.e., be defined recursively.<\/li>\n<li style=\"text-align: justify\">Prolog style syntax is commonly used.<\/li>\n<\/ul>\n<p style=\"text-align: center\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-176 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-76.png\" alt=\"\" width=\"857\" height=\"390\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-76.png 857w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-76-300x137.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-76-768x349.png 768w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-76-65x30.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-76-225x102.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-76-350x159.png 350w\" sizes=\"auto, (max-width: 857px) 100vw, 857px\" \/><\/p>\n<ul>\n<li>Find the components of a trike?<\/li>\n<li>We can write a relational algebra query to compute the answer on <strong><em>the given instance of Assembly<\/em>.<\/strong><\/li>\n<li>But there is no R.A. (or SQL-92) query that computes the answer on <strong><em>all Assembly instances<\/em><\/strong>.<\/li>\n<li>Intuitively, we must join Assembly with itself to deduce that trike contains spoke and tire.<\/li>\n<li>Takes us one level down Assembly hierarchy.<\/li>\n<li>To find components that are one level deeper (e.g., rim), need another join.<\/li>\n<li>To find all components, need as many joins as there are levels in the given instance!<\/li>\n<li>For any relational algebra expression, we can create an Assembly instance for which some answers are not computed by including more levels than the number of joins in the expression!<\/li>\n<\/ul>\n<p style=\"text-align: center\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-177 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-77.png\" alt=\"\" width=\"770\" height=\"183\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-77.png 770w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-77-300x71.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-77-768x183.png 768w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-77-65x15.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-77-225x53.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-77-350x83.png 350w\" sizes=\"auto, (max-width: 770px) 100vw, 770px\" \/><\/p>\n<p>Can read the second rule as follows:<\/p>\n<p>&nbsp;<\/p>\n<p>\u201c<strong>For all<\/strong> values of Part, Subpt and Qty,<\/p>\n<p><strong>if <\/strong>there is a tuple (Part, Part2, Qty) in Assembly<strong> and <\/strong>a tuple (Part2, Subpt) in Comp,<\/p>\n<p><strong>then <\/strong>there must be a tuple (Part, Subpt) in Comp.\u201d<\/p>\n<ul>\n<li style=\"text-align: justify\">Each rule is a <strong><em>template<\/em>:<\/strong> by assigning constants to the variables in such a way that each body \u201cliteral\u201d is a tuple in the corresponding relation, we identify a tuple that must be in the head relation.<\/li>\n<li style=\"text-align: justify\">By setting Part=trike, Subpt=wheel, Qty=3 in the first rule, we can deduce that the tuple &lt;trike,wheel&gt; is in the relation Comp.<\/li>\n<li style=\"text-align: justify\">This is called an <strong>inference<\/strong> using the rule.<\/li>\n<li style=\"text-align: justify\">Given a set of tuples, we <strong>apply<\/strong> the rule by making all possible inferences with these tuples in the body.<\/li>\n<\/ul>\n<p style=\"text-align: justify\">For any instance of Assembly, we can compute all Comp tuples by repeatedly applying the two rules. (Actually, we can apply Rule 1 just once, then apply Rule 2 repeatedly.)<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-178\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-78.png\" alt=\"\" width=\"615\" height=\"314\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-78.png 615w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-78-300x153.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-78-65x33.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-78-225x115.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-78-350x179.png 350w\" sizes=\"auto, (max-width: 615px) 100vw, 615px\" \/><\/p>\n<p style=\"text-align: justify\">Don\u2019t let the rule syntax of Datalog fool you: a collection of Datalog rules can be rewritten in SQL syntax, if recursion is allowed.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>WITH RECURSIVE <\/strong><strong>Comp(Part, Subpt)<\/strong><strong> AS<\/strong><\/p>\n<p><strong>(<\/strong><strong>SELECT<\/strong> <strong>A1.Part, A1.Subpt<\/strong> <strong>FROM<\/strong> <strong>Assembly A1<\/strong><strong>)<\/strong><\/p>\n<p><strong>UNION<\/strong><\/p>\n<p><strong>(<\/strong><strong>SELECT<\/strong> <strong>A2.Part, C1.Subpt<\/strong><\/p>\n<p><strong>FROM <\/strong><strong>Assembly A2, Comp C1<\/strong><\/p>\n<p><strong>WHERE <\/strong><strong>A2.Subpt=C1.Part<\/strong><strong>)<\/strong><\/p>\n<p><strong>SELECT <\/strong><strong>*<\/strong><strong> FROM <\/strong><strong>Comp C2<\/strong><\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li style=\"text-align: justify\">Let f be a function that takes values from domain D and returns values from D. A value v in D is a fixpoint of f if f(v)=v.<\/li>\n<li style=\"text-align: justify\">Consider the fn <em>double+<\/em>, which is applied to a set of integers and returns a set of integers (I.e., D is the set of all sets of integers).<\/li>\n<li style=\"text-align: justify\">E.g., <em>double+({1,2,5})={2,4,10} Union {1,2,5}<\/em><\/li>\n<li style=\"text-align: justify\">The set of all integers is a fixpoint of <em>double+.<\/em><\/li>\n<li style=\"text-align: justify\">The set of all even integers is another fixpoint of <em>double+<\/em>; it is smaller than the first fixpoint.<\/li>\n<li style=\"text-align: justify\">The least fixpoint of a function \u201c<em>f\u201d<\/em> is a fixpoint \u201c<em>v\u201d<\/em> of \u201c<em>f\u201d<\/em> such that every other fixpoint of \u201c<em>f\u201d<\/em> is smaller than or equal to \u201c<em>v\u201d<\/em>.<\/li>\n<li style=\"text-align: justify\">In general, there may be no least fixpoint (we could have two minimal fixpoints, neither of which is smaller than the other).<\/li>\n<li style=\"text-align: justify\">If we think of a Datalog program as a function that is applied to a set of tuples and returns another set of tuples, this function always has a least fixpoint.<\/li>\n<\/ul>\n<p><strong>\u00a0 \u00a0 Big(Part) :- Assembly(Part, Subpt, Qty), Qty &gt;2, <\/strong><strong>not<\/strong><strong> Small(Part).<\/strong><\/p>\n<p><strong>Small(Part) :- Assembly(Part, Subpt, Qty), <\/strong><strong>not<\/strong><strong> Big(Part).<\/strong><\/p>\n<ul>\n<li style=\"text-align: justify\">If rules contain <strong>not<\/strong> there may not be a least fixpoint. Consider the Assembly instance; trike is the only part that has 3 or more copies of some subpart. Intuitively, it should be in Big, and it will be if we apply Rule 1 first.<\/li>\n<li style=\"text-align: justify\">But we have Small(trike) if Rule 2 is applied first!<\/li>\n<li style=\"text-align: justify\">There are two minimal fixpoints for this program: Big is empty in one, and contains trike in the other (and all other parts are in Small in both fixpoints).<\/li>\n<li style=\"text-align: justify\">T depends on S if some rule with T in the head contains S or (recursively) some predicate that depends on S, in the body.<\/li>\n<li style=\"text-align: justify\">Stratified program: If T depends on <strong>not<\/strong> S, then S cannot depend on T (or <strong>not<\/strong> T).<\/li>\n<li style=\"text-align: justify\">If a program is stratified, the tables in the program can be partitioned into strata:<\/li>\n<li style=\"text-align: justify\">Stratum 0: All database tables.<\/li>\n<li style=\"text-align: justify\">Stratum I: Tables defined in terms of tables in Stratum I and lower strata.<\/li>\n<li style=\"text-align: justify\">If T depends on <strong>not<\/strong> S, S is in lower stratum than T.<\/li>\n<\/ul>\n<p style=\"text-align: justify\">\u00a0 \u00a0 \u00a0 Repeated inferences: When recursive rules are repeatedly applied in the na\u00efve way, we make the same inferences in several iterations.<\/p>\n<p style=\"text-align: justify\">Unnecessary\u00a0 inferences:\u00a0 Also,\u00a0 if\u00a0 we\u00a0 just\u00a0 want\u00a0 to\u00a0 find\u00a0 the components\u00a0 of\u00a0 a\u00a0 particular\u00a0 part,\u00a0 say\u00a0 wheel,\u00a0 computing\u00a0 the fixpoint of the Comp program and then selecting tuples with wheel in the first column is wasteful, in that we compute many irrelevant facts.<\/p>\n<p>&nbsp;<\/p>\n<p style=\"text-align: center\"><img loading=\"lazy\" decoding=\"async\" class=\"size-full wp-image-182 aligncenter\" src=\"http:\/\/csp4.epgpbooks.inflibnet.ac.in\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-79.png\" alt=\"\" width=\"640\" height=\"316\" srcset=\"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-79.png 640w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-79-300x148.png 300w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-79-65x32.png 65w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-79-225x111.png 225w, https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-content\/uploads\/sites\/47\/2018\/07\/a2-79-350x173.png 350w\" sizes=\"auto, (max-width: 640px) 100vw, 640px\" \/><\/p>\n","protected":false},"author":4,"menu_order":22,"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-172","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\/172","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":3,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters\/172\/revisions"}],"predecessor-version":[{"id":183,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapters\/172\/revisions\/183"}],"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\/172\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/media?parent=172"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/pressbooks\/v2\/chapter-type?post=172"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/contributor?post=172"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/ebooks.inflibnet.ac.in\/csp4\/wp-json\/wp\/v2\/license?post=172"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}