Introduction to Database Systems CSE 414

1 Introduction to Database SystemsCSE 414 Lecture 8: Datalog1 CSE 414 -Spring 2018 Announcements HW3 posted (1 week) Same dataset, more challenging queries We have sent out all Azure codes if you filled out the form earlier Make sure you use the cheapest tier aka READ THE HW INSTRUCTIONS You should first run on sqlitein any case!CSE 414 -Spring 20182 Class Overview Unit 1: Intro Unit 2: Relational Data Models and Query Languages Data models, SQL, Datalog, Relational Algebra Unit 3: Non-relational data Unit 4: RDMBS internals and query optimization Unit 5: Parallel query processing Unit 6: DBMS usability, conceptual design Unit 7: TransactionsCSE 414 -Spring 20183 What is Datalog?

2 Another query language for relational model Designed in the 80 s Simple, concise, elegant Extends relational queries with recursion Today is a hot topic: Souffle(we will use in HW4) Eve Differential Beyond databases in many research projects: network protocols, static program analysis4 Open-source implementation of DatalogDBMS Under active development Commercial implementations are available More difficult to set up and use sqlite of Datalog Set-based rather than bag-based Install in your VM Run sudoyum install soufflein terminal More details in upcoming HW45 Why bother with yetanother relational query language?6 CSE 414 -Spring 2018 Example: storing FB friendsCSE 414 -Spring 20187 PeterMaryJohnPhilAs a graphOr a relationWe will learn the tradeoffs of different data models later this quarterCompute your friends (p1, p2, isFriend) FROMF riends as = me 1My own FROMF riends as f1,( FROMF riends as = me 1) as = = 1My FoFWhen does it end?

3 ??Datalogallows us to writerecursive querieseasilyMy : Facts and RulesCSE 414 -Spring 20189 Facts = tuples in the databaseRules = queriesActor(id, fname, lname)Casts(pid, mid)Movie(id, name, year)SchemaDatalog: Facts and RulesCSE 414 -Spring 201810 Facts = tuples in the databaseRules = queriesActor(id, fname, lname)Casts(pid, mid)Movie(id, name, year).declActor(id:number, fname:symbol, lname:symbol).declCasts(id:number, mid:number).declMovie(id:number, name:symbol, year:number)Actor(344759, Douglas , Fowley ).Casts(344759, 29851).Casts(355713, 29000).Movie(7909, A Night in Armour , 1910).Movie(29000, Arizona , 1940).Movie(29445, Ave Maria , 1940).

4 Table declarationTypes in Souffle:numbersymbol (aka varchar)Insert dataDatalog: Facts and RulesCSE 414 -Spring 201811 Facts = tuples in the databaseRules = queriesActor(id, fname, lname)Casts(pid, mid)Movie(id, name, year)Actor(344759, Douglas , Fowley ).Casts(344759, 29851).Casts(355713, 29000).Movie(7909, A Night in Armour , 1910).Movie(29000, Arizona , 1940).Movie(29445, Ave Maria , 1940).Q1(y) :-Movie(x,y,z), z= : Facts and RulesCSE 414 -Spring 201812 Facts = tuples in the databaseRules = queriesFind Movies made in 1940 Actor(id, fname, lname)Casts(pid, mid)Movie(id, name, year)Actor(344759, Douglas , Fowley ).Casts(344759, 29851).Casts(355713, 29000).

5 Movie(7909, A Night in Armour , 1910).Movie(29000, Arizona , 1940).Movie(29445, Ave Maria , 1940).Q1(y) :-Movie(x,y,z), z= : Facts and RulesCSE 414 -Spring 201813 Facts = tuples in the databaseRules = queriesFind Movies made in 1940 Actor(id, fname, lname)Casts(pid, mid)Movie(id, name, year)Actor(344759, Douglas , Fowley ).Casts(344759, 29851).Casts(355713, 29000).Movie(7909, A Night in Armour , 1910).Movie(29000, Arizona , 1940).Movie(29445, Ave Maria , 1940).Q1(y) :-Movie(x,y,z), z= = 1940 SQLD atalog: Facts and RulesCSE 414 -Spring 201814 Facts = tuples in the databaseRules = queriesFind Movies made in 1940 Actor(id, fname, lname)Casts(pid, mid)Movie(id, name, year)Actor(344759, Douglas , Fowley ).

6 Casts(344759, 29851).Casts(355713, 29000).Movie(7909, A Night in Armour , 1910).Movie(29000, Arizona , 1940).Movie(29445, Ave Maria , 1940).Q1(y) :-Movie(x,y,z), z= of variable matters!Datalog: Facts and RulesCSE 414 -Spring 201815 Facts = tuples in the databaseRules = queriesFind Movies made in 1940 Actor(id, fname, lname)Casts(pid, mid)Movie(id, name, year)Actor(344759, Douglas , Fowley ).Casts(344759, 29851).Casts(355713, 29000).Movie(7909, A Night in Armour , 1910).Movie(29000, Arizona , 1940).Movie(29445, Ave Maria , 1940).Q1(y) :-Movie(iDontCare,y,z), z= : Facts and RulesCSE 414 -Spring 201816 Facts = tuples in the databaseRules = queriesFind Movies made in 1940 Actor(id, fname, lname)Casts(pid, mid)Movie(id, name, year)Actor(344759, Douglas , Fowley ).

7 Casts(344759, 29851).Casts(355713, 29000).Movie(7909, A Night in Armour , 1910).Movie(29000, Arizona , 1940).Movie(29445, Ave Maria , 1940).Q1(y) :-Movie(_,y,z), z= = don t care variablesDatalog: Facts and RulesCSE 414 -Spring 201817 Facts = tuples in the databaseRules = queriesActor(id, fname, lname)Casts(pid, mid)Movie(id, name, year)Actor(344759, Douglas , Fowley ).Casts(344759, 29851).Casts(355713, 29000).Movie(7909, A Night in Armour , 1910).Movie(29000, Arizona , 1940).Movie(29445, Ave Maria , 1940).Q1(y) :-Movie(x,y,z), z= (f,l) :-Actor(z,f,l), Casts(z,x),Movie(x,y,1940).Datalog: Facts and RulesCSE 414 -Spring 201818 Facts = tuples in the databaseRules = queriesFind Actors who acted in Movies made in 1940 Actor(id, fname, lname)Casts(pid, mid)Movie(id, name, year)Actor(344759, Douglas , Fowley ).

8 Casts(344759, 29851).Casts(355713, 29000).Movie(7909, A Night in Armour , 1910).Movie(29000, Arizona , 1940).Movie(29445, Ave Maria , 1940).Q1(y) :-Movie(x,y,z), z= (f,l) :-Actor(z,f,l), Casts(z,x),Movie(x,y,1940).Datalog: Facts and RulesCSE 414 -Spring 201819 Facts = tuples in the databaseRules = queriesActor(id, fname, lname)Casts(pid, mid)Movie(id, name, year)Actor(344759, Douglas , Fowley ).Casts(344759, 29851).Casts(355713, 29000).Movie(7909, A Night in Armour , 1910).Movie(29000, Arizona , 1940).Movie(29445, Ave Maria , 1940).Q3(f,l) :-Actor(z,f,l), Casts(z,x1), Movie(x1,y1,1910),Casts(z,x2), Movie(x2,y2,1940).Q1(y) :-Movie(x,y,z), z= (f,l) :-Actor(z,f,l), Casts(z,x),Movie(x,y,1940).

9 Datalog: Facts and RulesCSE 414 -Spring 201820 Facts = tuples in the databaseRules = queriesFind Actors who acted in a Movie in 1940 and in one in 1910 Actor(id, fname, lname)Casts(pid, mid)Movie(id, name, year)Actor(344759, Douglas , Fowley ).Casts(344759, 29851).Casts(355713, 29000).Movie(7909, A Night in Armour , 1910).Movie(29000, Arizona , 1940).Movie(29445, Ave Maria , 1940).Q3(f,l) :-Actor(z,f,l), Casts(z,x1), Movie(x1,y1,1910),Casts(z,x2), Movie(x2,y2,1940).Q1(y) :-Movie(x,y,z), z= (f,l) :-Actor(z,f,l), Casts(z,x),Movie(x,y,1940).Datalog: Facts and RulesCSE 414 -Spring 201821 Actor(344759, Douglas , Fowley ).Casts(344759, 29851).Casts(355713, 29000).

10 Movie(7909, A Night in Armour , 1910).Movie(29000, Arizona , 1940).Movie(29445, Ave Maria , 1940).Facts = tuples in the databaseRules = queriesQ3(f,l) :-Actor(z,f,l), Casts(z,x1), Movie(x1,y1,1910),Casts(z,x2), Movie(x2,y2,1940).Extensional Database Predicates = EDB = Actor, Casts, MovieIntensionalDatabase Predicates = IDB = Q1, Q2, Q3 Actor(id, fname, lname)Casts(pid, mid)Movie(id, name, year)Q1(y) :-Movie(x,y,z), z= (f,l) :-Actor(z,f,l), Casts(z,x),Movie(x,y,1940).Datalog: TerminologyCSE 414 -Spring 201822Q2(f, l) :-Actor(z,f,l), Casts(z,x), Movie(x,y,1940).bodyheadatomatomatom (aka subgoal)f, l= head variablesx,y,z= existential variablesMore DatalogTerminology Ri(argsi) called an atom, or a relational predicate Ri(argsi) evaluates to true when relation Ricontains the tuple described by argsi.