《数据库系统概念 Database System Concepts》原书教学资源（第五版，PPT课件讲稿，英文版）Chapter 5 Other Relational Languages

Chapter 5:Other Relational Languages Tuple Relational Calculus Domain Relational Calculus Query-by-Example(QBE) Datalog Database System Concepts-5th Edition,July 8,2005 5.2 @Silberschatz,Korth and Sudarshan

Database System Concepts - 5 5.2 ©Silberschatz, Korth and Sudarshan th Edition, July 8, 2005 Chapter 5: Other Relational Languages Tuple Relational Calculus Domain Relational Calculus Query-by-Example (QBE) Datalog

Tuple Relational Calculus A nonprocedural query language,where each query is of the form tP(t)) It is the set of all tuples t such that predicate P is true for f t is a tuple variable,t [A]denotes the value of tuple t on attribute A t e r denotes that tuple t is in relation r P is a formula similar to that of the predicate calculus Database System Concepts-5th Edition,July 8,2005 5.3 ©Silberschat乜，Korth and Sudarshan

Database System Concepts - 5 5.3 ©Silberschatz, Korth and Sudarshan th Edition, July 8, 2005 Tuple Relational Calculus A nonprocedural query language, where each query is of the form {t | P (t ) } It is the set of all tuples t such that predicate P is true for t t is a tuple variable, t [A ] denotes the value of tuple t on attribute A t  r denotes that tuple t is in relation r P is a formula similar to that of the predicate calculus

Predicate Calculus Formula 1.Set of attributes and constants 2.Set of comparison operators:(e.g,，≥) 3.Set of connectives:and (A),or (v),not ( 4.Implication(→：x→y,if x if true,then y is true X→y≡XVy 5.Set of quantifiers: 3ter(Q(t))="there exists"a tuple in t in relation r such that predicate Q(t)is true ∀ter(Q(t)≡Q is true“for all"tuples t in relation r Database System Concepts-5th Edition,July 8,2005 5.4 @Silberschatz,Korth and Sudarshan

Database System Concepts - 5 5.4 ©Silberschatz, Korth and Sudarshan th Edition, July 8, 2005 Predicate Calculus Formula 1. Set of attributes and constants 2. Set of comparison operators: (e.g., , , =, , , ) 3. Set of connectives: and (), or (v)‚ not () 4. Implication (): x  y, if x if true, then y is true x  y  x v y 5. Set of quantifiers:   t  r (Q (t ))  ”there exists” a tuple in t in relation r such that predicate Q (t ) is true  t  r (Q (t ))  Q is true “for all” tuples t in relation r

Banking Example branch (branch name,branch city,assets customer(customer name,customer street,customer city account (account_number,branch_name,balance loan(loan number,branch name,amount depositor(customer name,account number borrower (customer name,loan number Database System Concepts-5th Edition,July 8,2005 5.5 @Silberschatz,Korth and Sudarshan

Database System Concepts - 5 5.5 ©Silberschatz, Korth and Sudarshan th Edition, July 8, 2005 Banking Example branch (branch_name, branch_city, assets ) customer (customer_name, customer_street, customer_city ) account (account_number, branch_name, balance ) loan (loan_number, branch_name, amount ) depositor (customer_name, account_number ) borrower (customer_name, loan_number )

Example Queries Find the loan number,branch name,and amount for loans of over $1200 {t tE loan ^t [amount ]1200) Find the loan number for each loan of an amount greater than $1200 {t |3s e loan (t [loan_number ]s [loan_number ]^s [amount ]>1200)} Notice that a relation on schema [loan number is implicitly defined by the query Database System Concepts-5th Edition,July 8,2005 5.6 ©Silberschat乜，Korth and Sudarshan

Database System Concepts - 5 5.6 ©Silberschatz, Korth and Sudarshan th Edition, July 8, 2005 Example Queries Find the loan_number, branch_name, and amount for loans of over $1200 Find the loan number for each loan of an amount greater than $1200 {t |  s  loan (t [loan_number ] = s [loan_number ]  s [amount ]  1200)} Notice that a relation on schema [loan_number ] is implicitly defined by the query {t | t  loan  t [amount ]  1200}

Example Queries Find the names of all customers having a loan,an account,or both at the bank (t|3s e borrower (t [customer_name ]=s [customer_name ] v 3u e depositor (t [customer name ]u [customer_name ] Find the names of all customers who have a loan and an account at the bank (t|3s e borrower (t [customer_name ]=s [customer_name ] ^3u e depositor t [customer_name ]u [customer_name] Database System Concepts-5th Edition,July 8,2005 5.7 @Silberschatz,Korth and Sudarshan

Database System Concepts - 5 5.7 ©Silberschatz, Korth and Sudarshan th Edition, July 8, 2005 Example Queries Find the names of all customers having a loan, an account, or both at the bank {t | s  borrower ( t [customer_name ] = s [customer_name ])  u  depositor ( t [customer_name ] = u [customer_name] ) Find the names of all customers who have a loan and an account at the bank {t | s  borrower ( t [customer_name ] = s [customer_name ])  u  depositor ( t [customer_name ] = u [customer_name ])

Example Queries Find the names of all customers having a loan at the Perryridge branch (t|3s e borrower(t [customer_name ]=s [customer_name A3u∈loan(u[branch_name]=“Perryridge” ^u [loan_number ]=s [loan_number ])) Find the names of all customers who have a loan at the Perryridge branch,but no account at any branch of the bank {t3s e borrower (t [customer_name ]=s [customer_name A3u∈loan(u[branch_name]=“Perryridge” ^u [loan_number ]=s [loan_number ]) not 3ve depositor(v[customer_name ] t [customer_name ]) Database System Concepts-5th Edition,July 8,2005 5.8 @Silberschatz,Korth and Sudarshan

Database System Concepts - 5 5.8 ©Silberschatz, Korth and Sudarshan th Edition, July 8, 2005 Example Queries Find the names of all customers having a loan at the Perryridge branch {t | s  borrower (t [customer_name ] = s [customer_name ]  u  loan (u [branch_name ] = “Perryridge”  u [loan_number ] = s [loan_number ]))  not v  depositor (v [customer_name ] = t [customer_name ])} Find the names of all customers who have a loan at the Perryridge branch, but no account at any branch of the bank {t | s  borrower (t [customer_name ] = s [customer_name ]  u  loan (u [branch_name ] = “Perryridge”  u [loan_number ] = s [loan_number ]))}

Example Queries Find the names of all customers having a loan from the Perryridge branch,and the cities in which they live {tl3s∈loan(s[branch_name]=“Perryridge” ^3u E borrower (u [loan_number ]=s [loan_number t [customer_name ]u [customer_name ] ^3v e customer (u [customer_name ]=v [customer_name ^t [customer_city ]=v[customer_city ]))) Database System Concepts-5th Edition,July 8,2005 5.9 @Silberschatz,Korth and Sudarshan

Database System Concepts - 5 5.9 ©Silberschatz, Korth and Sudarshan th Edition, July 8, 2005 Example Queries Find the names of all customers having a loan from the Perryridge branch, and the cities in which they live {t | s  loan (s [branch_name ] = “Perryridge”  u  borrower (u [loan_number ] = s [loan_number ]  t [customer_name ] = u [customer_name ])   v  customer (u [customer_name ] = v [customer_name ]  t [customer_city ] = v [customer_city ])))}

Example Queries Find the names of all customers who have an account at all branches located in Brooklyn: (t3r e customer (t [customer_name ]=r[customer_name ] (Vu∈branch(u[branch_city]=“Brooklyn”→ 3s e depositor(t [customer_name =s [customer_name 3w e account w[account_number ]=s [account_number (w[branch_name ]u [branch_name ])))) Database System Concepts-5th Edition,July 8,2005 5.10 @Silberschatz,Korth and Sudarshan

Database System Concepts - 5 5.10 ©Silberschatz, Korth and Sudarshan th Edition, July 8, 2005 Example Queries Find the names of all customers who have an account at all branches located in Brooklyn: {t |  r  customer (t [customer_name ] = r [customer_name ])  (  u  branch (u [branch_city ] = “Brooklyn”   s  depositor (t [customer_name ] = s [customer_name ]   w  account ( w[account_number ] = s [account_number ]  ( w [branch_name ] = u [branch_name ]))))}

Safety of Expressions It is possible to write tuple calculus expressions that generate infinite relations. For example,{tter}results in an infinite relation if the domain of any attribute of relation ris infinite To guard against the problem,we restrict the set of allowable expressions to safe expressions. An expression {t|P(t )in the tuple relational calculus is safe if every component of t appears in one of the relations,tuples,or constants that appear in P NOTE:this is more than just a syntax condition. E.g.{tt[A]=5 v true is not safe---it defines an infinite set with attribute values that do not appear in any relation or tuples or constants in P. Database System Concepts-5th Edition,July 8,2005 5.11 @Silberschatz,Korth and Sudarshan

Database System Concepts - 5 5.11 ©Silberschatz, Korth and Sudarshan th Edition, July 8, 2005 Safety of Expressions It is possible to write tuple calculus expressions that generate infinite relations. For example, { t |  t  r } results in an infinite relation if the domain of any attribute of relation r is infinite To guard against the problem, we restrict the set of allowable expressions to safe expressions. An expression {t | P (t )} in the tuple relational calculus is safe if every component of t appears in one of the relations, tuples, or constants that appear in P NOTE: this is more than just a syntax condition.  E.g. { t | t [A] = 5  true } is not safe --- it defines an infinite set with attribute values that do not appear in any relation or tuples or constants in P