Lecture 10: Relational Algebra (continued), DatalogOutlineRelational AlgebraComplex QueriesExpression TreeExercisesOperations on Bags (and why we care)Rationale of Relational AlgebraGlimpse Ahead: Different Implementations of OperatorsGlimpse Ahead: Join-order OptimizationFinally: RA has Limitations !DatalogDatalog Example 1Datalog Example 2Datalog Example 3PowerPoint PresentationDatalog DefinitionsSlide 18Anonymous VariablesAnonymous Variables ContinuedSafe Datalog RulesMeaning of a Safe Datalog RuleMultiple Datalog RulesSlide 24Negation in DatalogNegation in Datalog (continued)Relational Algebra and DatalogFrom Relational Algebra to DatalogFrom RA to Datalog (cont’d)From (non-recursive) Datalog to RASlide 31Recursive Datalog ProgramsLecture 10: Relational Algebra (continued), DatalogMonday, October 16, 2000Outline•Really finish Relational Algebra (4.1)•Datalog (4.2-4.4)Relational Algebra•Five basic operators, many derived•Combine operators in order to construct queries: relational algebra expressions, usually shown as treesComplex QueriesProduct ( pid, name, price, category, maker-cid)Purchase (buyer-ssn, seller-ssn, store, pid)Company (cid, name, stock price, country)Person(ssn, name, phone number, city)Note:• in Purchase: buyer-ssn, seller-ssn are foreign keys in Person, pid is foreign key in Product; • in Product maker-cid is a foreign key in CompanyFind phone numbers of people who bought gizmos from Fred.Find telephony products that somebody boughtExpression Tree Person Purchase Person Productname=fredname=gizmo pid ssnseller-ssn=ssnseller-ssn=ssnbyuer-ssn=ssn nameExercises Product ( pid, name, price, category, maker-cid)Purchase (buyer-ssn, seller-ssn, store, pid)Company (cid, name, stock price, country)Person(ssn, name, phone number, city)Ex #1: Find people who bought telephony products.Ex #2: Find names of people who bought American productsEx #3: Find names of people who bought American products and did not buy French productsEx #4: Find names of people who bought American products and they live in Seattle.Ex #5: Find people who bought stuff from Joe or bought products from a company whose stock prices is more than $50.Operations on Bags (and why we care)•Union: {a,b,b,c} U {a,b,b,b,e,f,f} = {a,a,b,b,b,b,b,c,e,f,f}–add the number of occurrences•Difference: {a,b,b,b,c,c} – {b,c,c,c,d} = {a,b,b,d}–subtract the number of occurrences•Intersection: {a,b,b,b,c,c} {b,b,c,c,c,c,d} = {b,b,c,c}–minimum of the two numbers of occurrences•Selection: preserve the number of occurrences•Projection: preserve the number of occurrences (no duplicate elimination)•Cartesian product, join: no duplicate eliminationReading assignment: 4.6.2 - 4.6.6Rationale of Relational Algebra•Why bother ? Can write any RA expression directly in C++/Java, seems easy.•Two reasons:–Each operator admits sophisticated implementations (think of , C)–Expressions in relational algebra can be rewritten: optimizedGlimpse Ahead: Different Implementations of Operators• (age >= 30 AND age <= 35)(Employees)–Method 1: scan the file, test each employee–Method 2: use an index on age–Which one is better ? Depends a lot…•Employees Relatives–Many implementation methods (some researchers built careers out of that)Glimpse Ahead: Join-order OptimizationProduct ( pid, name, price, category, maker-cid)Purchase (buyer-ssn, seller-ssn, store, pid)Person(ssn, name, phone number, city)•Find people living in Seattle, buying>$100:price>100(Product) (Purchase city=seaPerson)price>100(Product) Purchase) city=seaPerson•Which is better ? Depends…Finally: RA has Limitations !•Cannot compute “transitive closure”•Find all direct and indirect relatives of Fred–Answer: Mary, Joe, Bill•Cannot express in RA !!! Need to write C programName1 Name2 RelationshipFred Mary FatherMary Joe CousinMary Bill SpouseNancy Lou SisterDatalog•RA is good because it can express different implementations•RA is unfriendly for writing queries•Logic is friendlier for writing queries•First Order Logic:•Datalog: a subset, friendlier but as powerful•SQL is based on logic (following lectures) ,,,,,Datalog Example 1Product ( pid, name, price, category, maker-cid)Purchase (buyer-ssn, seller-ssn, store, pid)Company (cid, name, stock price, country)Person(ssn, name, phone number, city)•Find all products over $99.99:•a selection: price>99.99(Product)S(i,n,p,c,m) Product(i,n,p,c,m) AND p>99.99S(i,n,p,c,m) Product(i,n,p,c,m) AND p>99.99Datalog Example 2Product ( pid, name, price, category, maker-cid)Purchase (buyer-ssn, seller-ssn, store, pid)Company (cid, name, stock price, country)Person(ssn, name, phone number, city)•Find the names of all products over $99.99:a selection-projection: nameprice>99.99(Product)S(n) Product(i,n,p,c,m) AND p>99.99S(n) Product(i,n,p,c,m) AND p>99.99Datalog Example 3Product ( pid, name, price, category, maker-cid)Purchase (buyer-ssn, seller-ssn, store, pid)Company (cid, name, stock price, country)Person(ssn, name, phone number, city)•Find store names where Fred bought:a selection-projection-join: storename=“Fred”(Person) ssn=buyer-ssnPurchaseS(n) Person(s,”Fred”,t,c) AND Purchase(s,l,n,p)S(n) Person(s,”Fred”,t,c) AND Purchase(s,l,n,p)•Datalog is really friendly•Let’s see the formal definitions, then more examplesDatalog Definitions•A predicate P is a relation name–E.g. Product–E.g. Company•An atom is P(x,y,z,…), with P a predicate and x,y,z variables or constants–E.g. Product(i,n,p,c,m)–E.g. Product(i,”gizmo”,p,”electronics”,”gizmoWorks”)–Given a database instance, an atom is true or false•Arithmetic atoms–E.g. x > 5–E.g. y <= z–Are true or false independent on the database instance•A datalog rule:•E.g.: S(n) Person(s, n, p, t, c) AND Purchase (b, s, “Gizmo Store”, i)•Datalog program = a collection of rules (later)Datalog Definitionsatom atom1 AND … AND atomnatom atom1 AND … AND atomnheadSubgoals: may be preceded by NOTbodyAnonymous VariablesProduct ( pid, name, price, category, maker-cid)Purchase (buyer-ssn, seller-ssn, store, pid)Company (cid, name, stock price, country)Person(ssn, name, phone number, city)Find names of people
View Full Document
Unlocking...