DatalogLogic As a Query LanguageA Logical RuleAnatomy of a RuleSlide 5sub-goals Are AtomsExample: AtomSlide 8Interpreting RulesSlide 10Example: InterpretationSlide 12Arithmetic sub-goalsExample: ArithmeticSlide 15Negated sub-goalsSlide 17Algorithms for Applying RulesExample: Variable-Based --- 1Example: Variable-Based; x=1, z=2Slide 21Example: Variable-Based; x=2, z=3Slide 23Tuple-Based AssignmentExample: Tuple-BasedSlide 26Datalog ProgramsEvaluating Datalog ProgramsExample: Datalog ProgramExpressive Power of DatalogSlide 31Recursive Example: Generalized CousinsRecursive ExampleDefinition of RecursionExample: Dependency GraphsEvaluating Recursive RulesThe “Naïve” Evaluation AlgorithmExample: Evaluation of CousinSemi-naive EvaluationSlide 40Parent Data: Parent Above ChildSlide 42Round 1Round 2Round 3Round 4Done!Recursion Plus NegationSlide 49Problematic Recursive NegationStratified NegationWhy Stratified Negation?Safe RulesExample: Unsafe RulesSlide 55StrataSlide 57Stratum GraphStratified Negation DefinitionExampleAnother ExampleSlide 62The Stratum GraphModelsSlide 65Minimal ModelsSlide 67The Stratified ModelExample: Multiple Models --- 1Slide 70Example: Multiple Models --- 2SQL-99 RecursionExample: SQL Recursion --- 1Example: SQL Recursion --- 2Example: SQL Recursion --- 3Form of SQL Recursive QueriesPlan to Explain Legal SQL RecursionMonotonicityExample: NonmonotonicitySQL Stratum Graph --- 2Slide 81Example: Stratum GraphThe GraphNonmonotone ExampleSlide 85NOT Doesn’t Mean NonmonotoneExample: Revised CousinS2 Still Monotone in Cousin1DatalogLogical RulesRecursionSQL-99 Recursion2Logic As a Query LanguageIf-then logical rules have been used in many systems.Most important today: EII (Enterprise Information Integration).Nonrecursive rules are equivalent to the core relational algebra.Recursive rules extend relational algebra --- have been used to add recursion to SQL-99.3A Logical RuleOur first example of a rule uses the relations:Frequents(customer,rest),Likes(customer,soda), andSells(rest,soda,price).The rule is a query asking for “happy” customers --- those that frequent a rest that serves a soda that they like.4Anatomy of a RuleHappy(c) <- Frequents(c,rest) ANDLikes(c,soda) AND Sells(rest,soda,p)5Anatomy of a RuleHappy(c) <- Frequents(c,rest) ANDLikes(c,soda) AND Sells(rest,soda,p)Body = “antecedent” =AND of sub-goals.Head = “consequent,”a single sub-goalRead thissymbol “if”6sub-goals Are AtomsAn atom is a predicate, or relation name with variables or constants as arguments.The head is an atom; the body is the AND of one or more atoms.Convention: Predicates begin with a capital, variables begin with lower-case.7Example: AtomSells(rest, soda, p)8Example: AtomSells(rest, soda, p)The predicate= name of arelationArguments arevariables9Interpreting RulesA variable appearing in the head is called distinguished ;otherwise it is nondistinguished.10Interpreting RulesRule meaning:The head is true of the distinguished variablesif there exist values of the nondistinguished variablesthat make all sub-goals of the body true.11Example: InterpretationHappy(c) <- Frequents(c,rest) ANDLikes(c,soda) AND Sells(rest,soda,p)Interpretation: customer d is happy if there exista rest, a soda, and a price p such that c frequents the rest, likes the soda, and the rest sells the soda at price p.12Example: InterpretationHappy(c) <- Frequents(c,rest) ANDLikes(c,soda) AND Sells(rest,soda,p)DistinguishedvariableNondistinguishedvariablesInterpretation: customer d is happy if there exista rest, a soda, and a price p such that c frequents the rest, likes the soda, and the rest sells the soda at price p.13Arithmetic sub-goalsIn addition to relations as predicates, a predicate for a sub-goal of the body can be an arithmetic comparison.We write such sub-goals in the usual way, e.g.: x < y.14Example: ArithmeticA soda is “cheap” if there are at least two rests that sell it for under $1.Figure out a rule that would determine whether a soda is cheap or not.15Example: ArithmeticCheap(soda) <- Sells(rest1,soda,p1) ANDSells(rest2,soda,p2) ANDp1 < 1.00 ANDp2 < 1.00 AND rest1 <> rest216Negated sub-goalsWe may put “NOT” in front of a sub-goal, to negate its meaning.17Negated sub-goalsExample:Think of Arc(a,b) as arcs in a graph.S(x,y) says the graph is not transitive from x to y ; i.e., there is a path of length 2 from x to y, but no arc from x to y.S(x,y) <- Arc(x,z) AND Arc(z,y)AND NOT Arc(x,y)18Algorithms for Applying RulesTwo approaches:1. Variable-based : Consider all possible assignments to the variables of the body. If the assignment makes the body true, add that tuple for the head to the result.2. Tuple-based : Consider all assignments of tuples from the non-negated, relational sub-goals. If the body becomes true, add the head’s tuple to the result.19Example: Variable-Based --- 1S(x,y) <- Arc(x,z) AND Arc(z,y)AND NOT Arc(x,y)Arc(1,2) and Arc(2,3) are the only tuples in the Arc relation.Only assignments to make the first sub-goal Arc(x,z) true are:1. x = 1; z = 22. x = 2; z = 320Example: Variable-Based; x=1, z=2S(x,y) <- Arc(x,z) AND Arc(z,y) AND NOT Arc(x,y) 1 1 2 2 121Example: Variable-Based; x=1, z=2S(x,y) <- Arc(x,z) AND Arc(z,y) AND NOT Arc(x,y) 1 1 2 2 13 3 33 is the only value of y that makes allthree sub-goals true.Makes S(1,3) a tupleof the answer22Example: Variable-Based; x=2, z=3S(x,y) <- Arc(x,z) AND Arc(z,y) AND NOT Arc(x,y) 2 2 3 3 223Example: Variable-Based; x=2, z=3S(x,y) <- Arc(x,z) AND Arc(z,y) AND NOT Arc(x,y) 2 2 3 3 2No value of ymakes Arc(3,y)true.Thus, no contributionto the head tuples;S = {(1,3)}24Tuple-Based AssignmentStart with the non-negated, relational sub-goals only.Consider all assignments of tuples to these sub-goals.Choose tuples only from the corresponding relations.If the assigned tuples give a consistent value to all variables and make the other sub-goals true, add the head tuple to the result.25Example: Tuple-BasedS(x,y) <- Arc(x,z) AND Arc(z,y) AND NOT Arc(x,y)Only possible values Arc(1,2), Arc(2,3)Four possible assignments to first two sub-goals:Arc(x,z) Arc(z,y) (1,2) (1,2) (1,2) (2,3) (2,3) (1,2)
View Full Document