Datalog Logical Rules Recursion SQL 99 Recursion 1 Logic As a Query Language If 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 2 A Logical Rule Our first example of a rule uses the relations Frequents customer rest Likes customer soda and Sells rest soda price The rule is a query asking for happy customers those that frequent a rest that serves a soda that they like 3 Anatomy of a Rule Happy c Frequents c rest AND Likes c soda AND Sells rest soda p 4 Anatomy of a Rule Happy c Frequents c rest AND Likes c soda AND Sells rest soda p Head consequent a single sub goal Body antecedent AND of sub goals Read this symbol if 5 sub goals Are Atoms An 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 lowercase 6 Example Atom Sells rest soda p 7 Example Atom Sells rest soda p The predicate name of a relation Arguments are variables 8 Interpreting Rules A variable appearing in the head is called distinguished otherwise it is nondistinguished 9 Interpreting Rules Rule meaning The head is true of the distinguished variables if there exist values of the nondistinguished variables that make all sub goals of the body true 10 Example Interpretation Happy c Frequents c rest AND Likes c soda AND Sells rest soda p Interpretation customer d is happy if there exist a 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 11 Example Interpretation Happy c Frequents c rest AND Likes c soda AND Sells rest soda p Distinguished variable Nondistinguished variables Interpretation customer d is happy if there exist a 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 12 Arithmetic sub goals In addition to relations as predicates a predicate for a subgoal of the body can be an arithmetic comparison We write such sub goals in the usual way e g x y 13 Example Arithmetic A 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 14 Example Arithmetic Cheap soda Sells rest1 soda p1 AND Sells rest2 soda p2 AND p1 1 00 AND p2 1 00 AND rest1 rest2 15 Negated sub goals We may put NOT in front of a sub goal to negate its meaning 16 Negated sub goals Example 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 17 Algorithms for Applying Rules Two 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 18 Example Variable Based 1 S 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 2 2 x 2 z 3 19 Example Variable Based x 1 z 2 S x y Arc x z AND Arc z y AND NOT Arc x y 1 12 2 1 20 Example Variable Based x 1 z 2 S x y Arc x z AND Arc z y AND NOT 3Arc x y 3 3 1 12 2 1 3 is the only value of y that makes all three sub goals true Makes S 1 3 a tuple of the answer 21 Example Variable Based x 2 z 3 S x y Arc x z AND Arc z y AND NOT Arc x y 2 23 3 2 22 Example Variable Based x 2 z 3 S x y Arc x z AND Arc z y AND NOT Arc x y 2 23 3 2 Thus no contribution to the head tuples S 1 3 No value of y makes Arc 3 y true 23 Tuple Based Assignment Start with the non negated relational subgoals 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 24 Example Tuple Based S 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 Arc x z Arc z y sub goals 1 2 1 2 2 3 2 3 1 2 2 3 1 2 2 3 25 Example Tuple Based S 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 Only assignment Arc x z Arc z y sub goals with consistent These two rows are invalid since z can t be 3 and 1 or 3 and 2 simultaneously 1 2 1 2 2 3 2 3 1 2 2 3 1 2 2 3 z value Since it also makes NOT Arc x y true add S 1 3 to result 26 Datalog Programs A Datalog program is a collection of rules In a program predicates can be either 1 EDB Extensional Database stored table 2 IDB Intensional Database relation defined by rules Never both No EDB in heads 27 Evaluating Datalog Programs As long as there is no recursion we can pick an order to evaluate the IDB predicates so that all the predicates in the body of its rules have already been evaluated If an IDB predicate has more than one rule each rule contributes tuples to its relation 28 Example Datalog Program Using following EDB find all the manufacturers of sodas Joe doesn t sell Sells rest soda price and sodas name manf JoeSells s Sells Joe s rest s p Answer m Sodas s m AND NOT JoeSells s 29 Expressive Power of Datalog Without recursion Datalog can express all and only the queries of core relational algebra The same as SQL select from where without aggregation and grouping 30 Expressive Power of Datalog But with recursion Datalog …
View Full Document
Unlocking...