精华内容
下载资源
问答
  • 关系代数中各个运算符所含的属性个数和元组个数 关系代数操作 属性个 元组个数 R r m S s n RS r(要求r=s) ≤(m+n) R-S r(要求r=s) ≤m R×S r+s m×n ...

    关系代数中各个运算符所含的属性个数和元组个数

    关系代数操作 属性个数 元组个数
    R r m
    S s n
    R∪S r(要求r=s) ≤(m+n)
    R-S r(要求r=s) ≤m
    R×S r+s m×n
    π属性集(R) ≤r ≤m
    σF(R) r ≤m
    R∩S r(要求r=s) ≤ min(m,n)
    R÷S r-s ≤m
    R⋈S ≤r+s ≤m×n
    R⋈S
    F
    r+s

    ≤m×n

    展开全文
  • 关系运算及元组演算

    千次阅读 2019-10-10 15:51:11
    计算两关系在集合理论上的并集,即给出关系R和S(两者有相同元/列),R∪S元组包括R和S所有元组的集合,形式定义如下: 式中 t是元组变量(下同)。显然,R∪S=S∪R。 (2)差。计算两关系的区别...

    写了半天,不知道这些有什么用,好繁琐,不知道从这些东西可以用在什么地方,有哪些场景。


    1. 关系运算

    关系代数的基本运算主要有并、交、差、笛卡尔积、选择、投影、连接和除法运算。
    (1)并。计算两个关系在集合理论上的并集,即给出关系R和S(两者有相同元/列数),R∪S的元组包括R和S所有元组的集合,形式定义如下:
    在这里插入图片描述
    式中 t是元组变量(下同)。显然,R∪S=S∪R。

    (2)差。计算两个关系的区别的集合,即给出关系R和S(两者有相同元/列数),R-S的元组包
    括R中有而S中没有的元组的集合,形式定义如下:
    在这里插入图片描述
    通俗点说,就是属于R但是属于S的元素。

    针对这种差运算的应用场景,举个例子来说,就两只股票组合,一个组合包含“东阿阿胶”,“涪陵榨菜”,“同仁堂”。
    而另一个组合只包括“东阿阿胶”,“涪陵榨菜”。那这两个的差就是“同仁堂”

    (3)交。计算两个关系集合理论上的交集,即给出关系R和S(两者有相同元/列数),R∩S的元组包括R和S相同元组的集合,形式定义如下:
    在这里插入图片描述
    显然,R∩S=R-(R-S)和R∩S=S-(S-R)成立。

    (4)笛卡尔积。计算两个关系的笛卡尔乘积,令R为有m元的关系,S为有n元的关系,则R×S是m+n元的元组的集合,其前m个元素来自R的一个元组,而后n个元素来自S的一个元组。形成定义如下:

    在这里插入图片描述
    若R有u个元组,S有v个元组,则R×S有u×v个元组。

    要记住笛卡尔积的数量是两者的乘积即可,相当于两者排列组合。

    (5)投影。从一个关系中抽取指明的属性(列)。令R为一个包含属性A的关系,则

    在这里插入图片描述

    (6)θ连接。θ连接从两个关系的笛卡儿积中选取属性之间满足一定条件的元组,记作:
    在这里插入图片描述

    其中A和B分别为R和S上元数相等且可比的属性组。θ为“=”的连接,称为等值连接,记作:
    在这里插入图片描述

    如果两个关系中进行比较的分量必须是相同的属性组,并且在结果中将重复的属性去掉,则称为自然连接,记作:
    在这里插入图片描述
    θ连接是对笛卡尔积进行处理,虽然现在我还不知道这个到底是干什么用的。

    二、元祖演算

    在元组演算中,元组演算表达式简称为元组表达式,其一般形式为{t|P(t)},其中,t是元组变
    量,表示一个元数固定的元组;P是公式,在数理逻辑中也称为谓词,也就是计算机语言中的条件表
    达式。{t|P(t)}表示满足公式P的所有元组t的集合。

    在元组表达式中,公式由原子公式组成,原子公式有下列两种形式:
    (1)R(s),其中R是关系名,s是元组变量。其含义是“s是关系R的一个元组”。
    (2)s[i]θu[j],其中s和u是元组变量,θ是算术比较运算符,s[i]和u[j]分别是s的第i个分量和u的第j个分量。原子公式s[i]θu[j]表示“元组s的第i个分量与元组u的第j个分量之间满足θ运算”。例如,“t[2]<u[3]”表示元组t的第2个分量小于元组u的第3个分量。这个原子公式的一种简化形式是s[i]θa或aθu[j],其中a为常量。例如,“t[4]=3”表示t的第4个分量等于3。

    在一个公式中,如果元组变量未用存在量词“ ”或全称量词“ ”等符号定义,那么称为自由元组变量,否则称为约束元组变量。公式的递归定义如下。

    (1)每个原子是一个公式,其中的元组变量是自由变量。
    (2)如果P1和P2是公式,那么, P1、P1∨P2、P1∧P2和P1→P2也是公式。
    (3)如果P1是公式,那么( s)(P1)和( s)(P1)也都是公式。
    (4)公式中各种运算符的优先级从高到低依次为θ、 和 、 、∧和∨、→。在公式外还可以加括号,以改变上述优先顺序。
    (5)公式只能由上述四种形式构成,除此之外构成的都不是公式。

    在元组演算的公式中,有下列四个等价的转换规则:
    (1)P1∧P2等价于 ( P1∨ P2)。
    (2)P1∨P2等价于 ( P1∧ P2)。
    (3)( s)(P1(s))等价于 ( s)( P1(s));( s)(P1(s))等价于 ( s)( P1(s))。
    (4)P1→P2等价于 P1∨P2。
    关系代数表达式可以转换为元组表达式,例如,R∪S可用{t|R(t)∨S(t)}表示,R-S可用{t|R(t)∧S(t)}表示

    看了上面的这么一段话,完全不懂元祖演算是什么玩意,哈哈哈。

    测试习题

    试题1
    若对关系R(A,B,C,D)进行π1.3(R)运算,则该关系运算与__B__等价,表示__B__。
    A.πA=1,C=3(R) B.πA=1∧C=3(R) C.πA,C(R) D.πA=1∨C=3(R)

    A.属性A和C的值分别等于1和3的元组为结果集
    B.属性A和C的值分别等于1和3的两列为结果集
    C.对R关系进行A=1、C=3的投影运算
    D.对R关系进行属性A和C的投影运算

    试题2
    若关系R、S如图5-3所示,则R与S自然连接后的属性列数和元组个数分别为__B__;
    π1,4(σ3=6(R×S))B
    图5-3关系R与S
    (3)A.4和3 B.4和6 C.6和3 D.6和6
    (4)A.πA,D(σC=D(R×S))B.πA,R.D(σS.C=R.D(R×S))
    C.πA,R.D(σR.C=S.D(R×S))D.πR.A,R.D(σS.C=S.D(R×S))
    在这里插入图片描述

    展开全文
  • 关系代数 关系代数(relational algebra):一种过程化查询语言。包括一运算的集合,集合中...关系运算的结果自身也是一个关系,可用一个关系运算表达式作为另一个关系运算的参数,因此可以把多个关系代数运算组...

    关系代数

    关系代数(relational algebra):一种过程化查询语言。包括一个运算的集合,集合中运算以一个或两个关系为输入,产生一个新的关系作为结果。

    关系代数的基本运算包括:选择、投影、并、集合差、笛卡尔积、更名。

    其他运算:集合交、自然连接、赋值,可用基本运算来定义。

    关系运算的结果自身也是一个关系,可用一个关系运算表达式作为另一个关系运算的参数,因此可以把多个关系代数运算组合成一个关系代数表达式(relational-algebra expression

     

    关系代数定义了一套在表上运算且输出结果也是表的代数运算。这些运算可以混合使用来得到表达所希望查询的表达式。关系代数定义了关系查询语言中使用的基本运算。

    关系代数运算可分为:基本运算、附加的运算(可用基本运算表达)、扩展的运算(其中一些扩展了关系代数的表达能力)。

    关系代数是一种简介的、形式化的语言,不适用于那些偶尔使用数据库系统的用户,因此商用数据库系统采用有更多“语法修饰”的语言。(SQL基于关系代数)

     

    1. 基本运算

    一元运算:对一个关系进行运算,包括选择、投影、更名运算。

    二元运算:对两个关系进行运算,包括并、集合差、笛卡尔积运算。

     

    选择(select)运算选出满足给定谓词的元组,用小写sigma(σ)表示,下标为谓词,括号中为参数关系。

    e.g. 找出关系instructor中属于物理系的所有教师

    σdept_name=”Physics”(instructor)

    e.g. 找出工资额大于90000美元的所有教师

    σsalary>90000(instructor)

    可用连词and(∧)、or(∨)、not(¬)将多个谓词合并为一个较大的谓词。

    e.g. 找出属于物理系且工资大于90000美元的所有教师

    σdept_name=”Physic”salary>90000(instructor)

    选择谓词中可包括两个属性的比较。

    e.g. 找出所有系名与楼名相同的系

    σdept_name=building(department)

    注意:关系代数中的属于select与SQL中的关键词select含义不同,关系代数中属于select对应SQL中的where。

     

    投影(project)运算:返回作为参数的关系,但把某些属性排除在外,所有重复行均被去除。用大写pi(Π)表示,下标为在结果中出现的属性,括号中为参数关系。

    e.g. 列出所有教师的ID、name和salary,而不关系dept_name。

    ΠID, name, salary(instructor)

    e.g. 找出物理系所有教师的名字

    Πnamedept_name=”Physics”(instructor))

     

    并(union)运算: 可将两个集合并起来,找出出现在两个集合之一或同时出现在两个集合中的所有元组。用表示。

    e.g. 找出开设在2009年秋季学期或者2010年春季学期或者这二者皆开的所有课程的集合。

    Πcourse_idsemester=”Fall”year=2009(section))∪Πcourse_idsemester=”Spring”year=2010(section))

    /*注意:结果中重复值只留下单个元组。*/

    必须保证做并运算的关系是相容的,否则运算结果没有意义。要使并运算rs有意义(rs可以是数据库关系或作为关系代数表达式结果的临时关系),要求以下两个条件同时成立:

    a. 关系r和s必须是同元的(属性数目相同)。

    b. 对所有的i,r的第i个属性的域必须和s的第i个属性的域相同。

     

    集合差(set-difference)运算:表达式r-s包含所有在r中而不在s中的元组的关系。

    e.g. 找出所有开设在2009年秋季学期但是在2010年春季学期不开的课程。

    Πcourse_idsemester=”Fall”year=2009(section))-Πcourse_idsemester=”Spring”year=2010(section))

    类似并运算,必须保证做集合叉运算的关系是相容的,否则运算结果没有意义。要使集合差运算r-s有意义,要求一下两个条件同时成立:

    a. 关系r和s必须是同元的。

    b. 对所有的i,r的第i个属性的域必须和s的第i个属性的域相同。

     

    笛卡尔积(Cartesian-product)运算:将任意两个关系的信息组合在一起,结果中包含所有可能的元组对。关系r1和r2的笛卡尔积写作r1×r2,假如r1有n1个元组,r2有n2个元组,则可由n1×n2种方式选择元组对。

    由于相同的属性名可能同时出现在r1和r2中,需要一个命名机制来区别这些属性。可采用把属性所来自的关系名称附加到该属性上的方法。

    e.g. r = instructor×teaches的关系模式

    (instructor.ID, instructor.name, instructor.dept_name, instructor.salary, teaches.ID, teaches.course_id, teaches.sec_id, teaches.semeser, teaches.year)

    /*对于只在两个关系模式之一出现的属性,通常省略其关系名前缀。因此可将r的关系模式写作:*/

    (instructor.ID, name, dept_name, salary, teaches.ID, course_id, sec_id, semester, year)

    注意:该命名规则规定作为笛卡尔积运算参数的关系名称必须不同,因此当某个关系要与自身做笛卡尔积或在笛卡尔积中使用关系代数表达式结果时可能产生问题,可通过更名运算给关系一个名字以引用其属性来解决。

    e.g. 找出物理系中的所有教师,以及他们所教授的所有课程。

    /* σdept_name=”Physics”(instructor×teaches)只包含物理系的教师的元组,但course_id列可能包含并非这些教师所教授的课程;

    σinstructor.ID=teaches.IDdept_name=”Physics”(instructor×teaches))包含物理系教师以及他们所教的课程的元组;

    Πname, course_idinstructor.ID=teaches.IDdept_name=”Physics”(instructor×teaches)))投影得到需要的教师名字列和corse_id列。*/

    Πname, course_idinstructor.ID=teaches.IDdept_name=”Physics”(instructor×teaches)))

    /*用关系代数表达查询的方法并不唯一,也可采用如下等价查询:*/

    Πname, course_idinstructor.ID=teaches.ID((σdept_name=”Physics”(instructor))×teaches))

     

    更名(rename)运算:给关系代数表达式的结果赋上名字以供引用,用小写rho(ρ)表示。

    表达式ρx(E)返回给定关系代数表达式E的结果并把名字x赋给它。更名运算也可用于关系,可得到具有新名字的一个相同的关系。

    更名运算的另一形式:ρx(A1, A2, …, An)(E)。假设关系代数表达式E是n元的,运算返回表达式E的结果,并把名字x赋给它,同时将各属性更名为A1, A2, …, An

    e.g. 找出大学里的最高工资

    /*步骤1:计算出一个由非最高工资组成的临时关系。

    首先通过更名运算引用其中一个instructor关系以便计算笛卡尔积instructor×instructor,再构造选择运算比较任意两个出现在同一元组中的salary选择较低的元组。通过投影选取instructor.salary列得到非最高工资构成的临时关系*/

    Πinstructor.salaryinstructor.salary<d.salary(instructor×ρd(instructor)))

    /*步骤2:计算关系Πsalary (instructor)和刚才计算出的非最高工资构成的临时关系的集合差,得到结果。*/

    Πsalary (instructor)-Πinstructor.salaryinstructor.salary<d.salary(instructor×ρd(instructor)))

     

    更名运算不是必须的,因为可以用位置标记隐含地作为关系(或关系代数表达式运算的结果)的属性名,用$1、$2、…指代第一个属性、第二个属性…以此类推。

    e.g. 用位置标记来计算大学里的非最高工资构成的临时关系

    /*在笛卡尔积(instructor×instructor)中,$4代表第一个instructor的属性salary,$8代表第二个instructor的属性salary。*/

    Π$4$4<$8(instructor×instructor))

    如果一个二元运算需要区分其运算对象的两个关系,也可使用为指标及作为关系的名称。E.g. $R1指代第一个作为运算对象的关系,$R2指代第二个关系。

     

     

    2. 关系代数的形式化定义

    关系代数中基本的表达式是以下二者之一:a. 数据库中的一个关系;b. 一个常数关系。

     

    常数关系:可在{}内列出其元组来表示。

    E.g. {(22222, Einstein, Physics, 95000), (76543, Singh, Finance, 80000)}

     

    设E1和E2都是关系代数表达式,则以下这些都是关系代数表达式:

    ·E1∪E2

    ·E1-E2

    ·E1×E2

    ·σp(E1),P为E1属性上的谓词。

    ·ΠS(E1),S为E1上某些属性的列表。

    ·ρx(E1),x为E1结果的新名字。

     

     

    3. 附加的关系代数表达式

    关系代数的基本运算足以表达任何关系代数查询。附加的关系代数运算不能增强关系代数的表达能力,但可以简化一些常用的查询。

     

    集合交(intersection)运算 ()

    e.g. 找出在2009年秋季和2010年春季都开设的课程

    Πcourse_idsemester=”Fall”year=2009(section))∩Πcourse_idsemester=”Spring”year=2010(section))

    任何使用了集合交的关系代数表达式都可以通过一对集合差运算替代重写:

    r∩s=r-(r-s)

     

    自然连接(natural join)运算 ():首先形成两个参数关系的笛卡尔积,然后基于两个关系模式中都出现的属性上的相等性进行选择(只考虑两个关系在所有相同属性有相同值的元组组成的元组对),最后去除重复属性(并不重复记录在两个关系模式中都出现的属性)。

    自然连接的形式化定义:

    设r(R)和s(S)(模式分别为R和S的两个关系),其自然连接的结果r ⋈ s是模式R∪S上的一个关系。

    r ⋈ s = ΠRSr.A1=s.A1r.A2=s.A2r.An=s.An(r×s)),其中R∩S={A1, A2, …, An}。

    如果r和s不含有任何相同属性,即R∩S=∅,则r ⋈ s = r×s。

    所列出的属性的顺序:两个关系模式的相同属性排在最前,只属于第一个关系模式的属性其次,只属于第二个关系模式的属性最后。

    e.g. 找出所有教师的姓名,连同他们教的所有课程的course_id。

    /*instructor和teaches自然连接的结果模式为(ID, name, dept_name, salary, course_id),投影后得到模式为(name, course_id)的关系。*/

    Πname, course_id(instructor ⋈ teaches)

     考虑两个关系模式R和S,可将关系模式看作集合:用R∩S表示同时出现在R和S中的属性名,用R∪S表示出现在R中、S中或在二者中都出现的属性名,用R-S表示出现在R中而不出现在S中的属性名,用S-R表示出现在S中而不出现在R中的属性名。

    自然连接时可结合的(associative)。

    e.g. 找出计算机系的所有教师,以及他们教授的所有课程的名称。

    /* 自然连接instructor ⋈ teaches ⋈ course的执行顺序可能为

    (instructor ⋈ teaches) ⋈ course 或 instructor ⋈ (teaches ⋈ course),二者是等价的。*/

    Πname, titledept_name=”Comp.Sci.”(instructor ⋈ teaches ⋈ course))

     theta连接(theta join)运算:是自然连接的扩展。

    考虑关系r(R)和s(S),θ是模式R∪S的属性上的谓词。r ⋈θ s = σθ(r×s)

     

    赋值(assignment)运算 ():可用于给临时关系变量赋值,便于写关系代数表达式。

    e.g. 自然连接运算r ⋈s的定义可写作

    temp1←r×s

    temp2←σr.A1=s.A1r.A2=s.A2r.An=s.An(temp1)

    result = ΠRS(temp2)

    对关系代数查询而言,赋值必须是赋给一个临时关系变量。对永久关系的赋值形成了对数据库的修改。

     

    外连接(outer-join)运算:连接运算的扩展,可处理缺失的信息(因为不满足自然连接条件而不能在自然连接结果中找到的元组),避免信息的丢失。

    外连接运算与自然连接运算类似,不同之处在于外连接在连接计算结果中添加额外的带空值的元组,以此保留在连接中丢失的元组。

    外连接运算有三种形式:

    左外连接(left outer join)():取出左侧关系中所有与右侧关系的任一元组都不匹配的元组,用空值填充所有来自右侧关系的属性,再把产生的元组加到自然连接的结果中。所有来自左侧关系的信息在左外连接结果中都得到保留。

    右外连接(right outer join)():与左外连接相对称,用空值填充来自右侧关系的所有与左侧关系任一元组都不匹配的元组,将结果加到自然连接的结果中。所有来自右侧关系的信息在右外连接中都得到保留。

    全外链接(full outer join)():既做左外连接又做右外连接,既填充左侧关系中与右侧关系的任一元组都不匹配的元组,又填充右侧关系中与左侧关系任一元组都不匹配的元组,并把结果都加到连接的结果中。

    注意:外连接运算可用基本关系代数运算表示。E.g. 左外连接运算r⟕s可写作

    /*其中常数关系{(null, …, null)}的模式为S-R。*/

    (r ⋈ s)∪(r - ΠR(r ⋈ s)) × {(null, …, null)}

     

     

    4. 扩展的关系代数运算

    扩展的关系代数(extended relational-algebra)运算可实现一些不能用基本的关系代数运算来表达的查询

     

    广义投影(generalized-projection):通过允许在投影列表使用算术运算和字符串函数等来对投影进行扩展。

    运算形式:

    ΠF1, F2, …, Fn(E)

    其中E为任意关系代数表达式,F1, F2, …, Fn都是涉及常量以及E的模式中属性的算术表达式。

    最基本情况下算术表达式可以仅仅是一个属性或常量,在表达式中可使用对数值属性或产生数值结果的表达式的+、-、*、/等代数运算。广义投影还允许其他数据类型上的运算(如字符串的串接)。

    e.g. 查询每个教师的ID、name、dept_name以及每月的工资

    ΠID, name, dept_name, salary/12(instructor)

     

    聚集运算(?)

    聚集函数(aggregate function):输入值的一个汇集,将单一值作为结果返回。E.g. 聚集函数sum、avg、count、min、max。

    e.g. 使用聚集查询所有教师的工资总和的关系代数表达式

    ? sum(salary)(instructor)

     

    在计算聚集函数前如果想去除重复,可使用连字符将distinct附加在函数名后。

    e.g. 找出在2010年春季学期教课的教师数(每名教师只应计算一次,而不管他教了几门课程。)

    /*聚集函数count-distinct确保:即使某位教师授课多于一门,在结果中也只对他计数一次。*/

    ? count-distinct(ID)semester=”Spring”year=2010(teaches) )

     

    可对一组元组集合(而不是单个元组集合)执行聚集函数。

    聚集运算的通常形式为:

    G1, G2, …, Gn? F1(A1), F2(A2), …, Fm(Am)(E)

    其中E为任意关系代数表达式,G1, G2, …, Gn是用于分组的一系列属性,每个Fi是一个聚集函数,每个Ai是一个属性名。表达式E的结果中的元组被分成若干组,各组用属性G1, G2, …, Gn上的值唯一标识。

    属性列G1, G2, …, Gn可以为空,则唯一一组包含关系中所有的元组(相当于没有分组)。

    e.g. 分别查询a. 每个系教师的平均工资 b. 所有教师的平均工资

    /*先通过dept_name属性对关系instructor进行分组,再对每个分组执行指定查询。*/

    dept_name ? average(salary)(instructor)

    /*从运算符?左边去掉了属性dept_name,整个关系被当做单个组来执行聚集。*/

    ? average(salary)(instructor)

     

    多重集(multiset):使用聚集函数对其进行操作的汇集中,一个值可以出现多次,值出现的顺序是无关紧要的,这样的汇集称为多重集。集合(set)是多重集的特例,其中每个值都只出现一次。

    多重集关系代数(multiset relational algebra):SQL与关系代数不同,允许在输入关系以及查询结果汇总存在元组的多重拷贝。为了映射SQL的这种模式,我们定义了多重集关系代数来对多重集进行操作。

    多重集关系代数基本运算的定义:

    1. 如果在r1元组t1有c1份拷贝,并且t1满足选择σθ,那么在σθ(r1)中元组t1有c1份拷贝;

    2. 对于r1中元组t1的每份拷贝,在ΠA(r1)中都有一个与之对应的ΠA(t1),表示单个元组t1的投影。

    3. 如果在r1中元组t1有c1份拷贝,在r2中元组t2有c2份拷贝,那么在r1×r2中就有元组t1t2的c1*c2份拷贝。

    按照SQL中的相应含义,还可用相似方法定义多重集的并、交、集合差运算。(聚集运算在多重集定义下没有变化)

     

     

    元组关系演算

    不同于关系代数表达式,元组关系演算(tuple relational calculus非过程化的(nonprocedural)查询语言,只描述所需信息,而不给出获得该信息的具体过程。

    元组关系演算中的查询表达为:{ t | P(t) }。含义:所有使谓词P为真的元组t的集合。

     

    1. 查询示例

    e.g. 找出工资大于80000美元的所有教师的ID

    /*所有满足如下条件的元组t的集合:在关系instructor中存在元组s使t和s在属性ID上的值相等,且s在属性salary上的值大于80000美元。

    因为ID属性是对t进行限制的条件所涉及的唯一属性,因此结果只得到ID列上的关系。*/

    { t| ∃s∈instructor( t[ID] = s[ID] ∧ s[salary] >80000 ) }

    e.g. 找出位置在Watson楼的系中的所有教师姓名

    /*元组变量u保证该系位于Watson楼,元组变量s被限制到与u的dept_name相同。结果得到name列上的关系。*/

    { t | ∃s∈instructor( t[name] = s[name]

    ∧∃u∈department( u[dept_name] = s[dept_name]

                         ∧ u[building] = ‘Watson’ ) ) }

    e.g. 找出在2009年秋季学期或2010年春季学期或这两个学期都开设的所有课程的course_id

    /*给出至少满足下面两个条件之一的couse_id元组的集合:

    ·在关系section中满足semester=Fall且year=2009的某个元组包含该course_id;

    ·在关系section中满足semester=Spring且year=2010的某个元组包含该course_id。*/

    { t | ∃s∈section ( t[course_id] = s[course_id] )

         ∧s[semester] = “Fall”∧s[year] = 2009 )

    ∨∃u∈section (u[course_id] = t[course_id] )

         ∧u[semester] = “Spring”∧u[year] = 2010 )

    e.g. 找出只在2009年秋季和2010年春季两个学期都开设的所有课程的course_id

    { t | ∃s∈section ( t[course_id] = s[course_id] )

         ∧s[semester] = “Fall”∧s[year] = 2009 )

    ∧∃u∈section (u[course_id] = t[course_id] )

         ∧u[semester] = “Spring”∧u[year] = 2010 )

    e.g. 找出2009年秋季开设而2010年春季不开的所有课程的course_id

    /*从2009年秋季开设的课程中去掉那些在2010年春季开设的课程*/

    { t | ∃s∈section ( t[course_id] = s[course_id] )

         ∧s[semester] = “Fall”∧s[year] = 2009 )

    ∧¬∃u∈section (u[course_id] = t[course_id] )

         ∧u[semester] = “Spring”∧u[year] = 2010 )

    e.g. 找出所有那些选了生物系全部课程的学生

    /*所有满足如下条件的ID列上的元组t的集合:

    对关系course中所有元组u,如果u在dept_name属性上的值是’Biology’,那么在关系takes中一定存在一个包含该学生ID以及该课程course_id的元组。

    注意:如果生物系没有开设任何课程,则所有学生ID都满足条件。该情况下,∃r∈student ( r[ID] = t[ID] )保证结果是关系student里的学生ID的值。*/

    { t | ∃r∈student ( r[ID] = t[ID] ) ∧

      ∀u∈course (u[dept_name] = “Biology”⇒

    ∃s∈takes ( t[ID] = s[ID]

    ∧s[course_id] = u[course_id] ) ) }

     

     

    形式化定义

    元组关系演算表达式的形式:{ t | P(t) }

    P为一个公式,公式中可出现多个元组变量,如果元组变量不被∃或∀修饰则称为自由变量,否则称为受限变量

    公式由原子构成。原子可以为如下形式之一:

    ·s∈r,其中s为元组变量,r为关系;

    ·s[x] ? u[y],其中s、u为元组变量,x为s所基于的关系模式中的一个属性,y为u所基于的关系模式中的一个属性,?为比较运算符(<, ≤, =, ≠, >, ≥)(要求x和y所属域成员可用?比较);

    ·s[x] ? c,其中s为元组变量,x为s所基于的关系模式中的一个属性,c是属性x所属域中的常量。

    根据如下规则用原子构造公式:

    ·原子是公式;

    ·如果P1是公式,则¬P1和(P1)也都是公式;

    ·如果P1和P2是公式,则P1∨P2、P1∧P2和P1⇒P2也都是公式;

    ·如果P1(s)是包含自由元组变量s的公式,r为关系,则∃s∈r(P1(s))和∀s∈(P1(s))也都是公式。

     

    元组关系演算中的等价性规则:

    ·P1∧P2等价¬(¬(P1)∨¬(P2));

    ·∀t∈r(P1(t))等价¬∃t∈r(¬P1(t));

    ·P1⇒P2等价¬(P1)∨P2

     

     

    元组关系演算表达式的安全性

    为避免元组关系演算表达式产生一个无限的关系,需对元组关系演算进行限制。

    域(domain):元组关系公式P的域用dom(P)表示,是P所引用的所有值的集合。它既包括P自身用到的值,又包括P中所涉及的关系的元组中出现的所有值。(i.e. P中显式出现的值,以及名称出现在P中的那些关系的所有值的集合)。

    如果出现在表达式{ t | P(t) }结果中的所有值均来自dom(P),则表达式是安全的,安全的表达式一定包含有限的结果。

     

    语言表达能力

    限制在安全表达式范围内的元组关系演算和基本关系代数(不包括扩展的关系代数运算符)具有相同的表达能力。

    因此:

    对于每个只运用基本操作的关系代数表达式,都有与之等价的元组关系演算表达式;

    对于每个元组关系演算表达式,也都有与之等价的关系代数表达式。

     

     

    域关系演算

    域关系演算(domain relational calculus):关系演算的另一种形式,使用从属性域中取值的域变量,而不是整个元组的值。

     

    1. 形式化定义

    域关系演算中的表达式形式:

    { <x1, x2, …, xn> | P(x1, x2, …, xn) }

    其中x1, x2, …, xn代表域变量,P代表由原子构成的公式。

    原子可以为如下形式之一:

    ·<x1, x2, …, xn>∈r,其中r为n个属性上的关系,x1, x2, …, xn为域变量或域常量;

    ·x?y,其中x和y为域变量,?为比较运算符(要求属性x和y所属域可用?比较);

    ·x?c,其中x为域变量,c是x作为域变量的那个属性域中的常量。

    根据如下规则用原子构造公式:

    ·原子是公式;

    ·如果P1是公式,则¬P1和(P1)也都是公式;

    ·如果P1和P2是公式,则P1∨P2、P1∧P2和P1⇒P2也都是公式;

    ·如果P1(x)是包含自由域变量x的公式,则∃x(P1(x))和∀x(P1(x))也都是公式。

    我们把∃a,b,c(P(a,b,c))作为a(∃b(∃c(P(a,b,c))))的简写。

     

    2. 查询示例

    e.g. 找出工资在80000美元以上的教师的ID、name、dept_name和salary。

    { <i, n, d, s> | <i, n, d, s>∈instructor∧s>80000 }

    e.g. 找出工资大于80000美元的所有教师的姓名

    { < i > | ∃n, d, s (<i, n, d, s>∈instructor∧s>80000) }

    e.g. 找出在物理系的所有教师的姓名,以及他们教授的所有课程的course_id。

    { <n, c> | ∃i, a, s, y (<I, c, a, s, y>∈teaches

       ∧∃d, s(<i, n, d, s>∈instructor∧d=”Physics”) ) }

    e.g. 找出在2009年秋季学期或2010年春季学期或这两个学期都开设的所有课程的集合

    { < c > | ∃a, s, y, b, r, t(<c, a, s, y, b, r, t>∈section

         ∧s=”Fall”∧y=”2009”)

       ∨∃a, s, y, b, r, t(<c, a, s, y, b, r, t>∈section

         ∧s=”Spring”∧y=”2010”) }

    e.g. 找出选了生物系开设的全部课程的所有学生

    /*如果生物系没开设任何课程,结果将包含所有学生。*/

    { < i > | ∃n, d, tc(<i, n, d, tc>∈student) ∧

      ∀ci, ti, dn, cr(<ci, ti, dn, cr>∈course ∧ dn=“Biology” ⇒

      ∃si, se, y, g(<I, ci, si, se, y, g>∈takes) ) }

     

    表达式的安全性

    不安全的域关系演算表达式的结果中会出现不在表达式域中的值。

    如果下列条件同时成立,则认为表达式{ <x1, x2, …, xn> | P(x1, x2, …, xn) }是安全的:

    1. 表达式的元组中所有值均来自dom(P);

    2. 对每个形如∃x(P1(x))的子公式,子公式为真当且仅当dom(P1)中有某个值x使P1(x)为真;

    3. 对每个形如∀x(P1(x))的子公式,子公式为真当且仅当P1(x)对dom(P1)中所有值x均为真。

     

    语言表达能力

    限制在安全表达式范围内的域关系演算和限制在安全表达范围内的元组关系演算具有相同的表达能力(因此也与基本关系代数的表达能力等价)。

    注意:没有任何一个域关系演算等价于聚集运算,但它可以扩展以支持聚集。

     

    元组关系演算和域关系演算是非过程化语言,代表了关系查询语言所需的基本能力。基本关系代数是一种过程化的语言,在能力上等价于被限制在安全表达式范围内的关系演算的这两种形式。

    关系演算是简介的、形式化的语言,不适合于那些偶尔使用数据库系统的用户。(QBE和Datalog基于元祖关系演算和域关系演算)

    转载于:https://www.cnblogs.com/RDaneelOlivaw/p/8149086.html

    展开全文
  • 数据库 元组关系演算

    千次阅读 2019-02-17 21:47:37
    数据库 元组关系演算
                   

    元组关系演算


        之前学习了一下关系代数表达式,现在再学习一下元组关系的演算,这样就全了。这篇东西的符号打出来费了好多时间,比较麻烦,还好看着还能看懂,关键是全文本的,好下面开始正文。


        为了讨论方便,先允许关系的基数是无限的。然后再对这种情况下定义的演算作适当的修改,保证关系演算中的每一个公式表示的是有限关系。


        在元组关系演算系统中,称 {t|Φ(t)} 为元组演算表达式。其中 t 是元组变量, Φ(t) 为元组关系演算公式,简称公式。 
    它由原子公式和运算符组成。

     

         原子公式有三类:

     

        (1) R(t)

            R 是关系名, t 是元组变量。 R(t) 表示 t 是 R 中的元组。于是,关系 R 可表示为: {t|R(t)}

        (2) t[i] θ u[j]

            t 和 u 是元组变量, θ 是算术比较运算符。 t[i] θ u[j] 表示断言 “ 元组 t 的第 i 个分量与元组 u 的第 j 个分量满足比较关系 θ ” 。例如, t[2] < u[3] 表示元组 t 的第 2 个分量小于元组 u 的第 3 个分量。

        (3) t[i] θ c 或  c θ t[i] 
            这里 c 是常量,该公式表示 “t 的第 i 个分量与常量 C 满足比较关系 θ” 。例如: t[4]=3 表示元组 t 的第 4 个分量等于 3 。

     

         在关系演算中定义了 “ 自由元组变量 ” 和 “ 约束元组变量 ” 的概念。这些概念和谓词演算中的概念完全一样。若公式中的一个元组变量前有 “ 全称量词 ” 或 “ 存在量词 ” ,则称该变量为约束元组变量,否则称自由元组变量。

     

        公式可以递归定义如下:

     

        (l) 每个原子公式是公式。 
        (2) 如果 Φ 1 和 Φ 2 是公式,则 Φ 1 ∧ Φ 2 、 Φ 1 ∨ Φ 2 、 ﹁ Φ1 也是公式。分别表示: 
            ① 如果 Φ 1 和 Φ 2 同时为真。则 Φ 1 ∧ Φ 2 才为真,否则为假; 
            ② 如果 Φ 1 和 Φ 2 中一个或同时为真,则 Φ 1 ∨ Φ 2 为真,仅 Φ 1 和 Φ 2 同时为假时, Φ 1 ∨ Φ 2 才为假; 
            ③ 如果 Φ 1 真,则 ﹁ Φ 1 为假。 
        (3) 若 Φ 是公式,则 ∃ t(Φ) 也是公式。其中符号 ∃ 是存在量词符号, ∃ t(Φ) 表示: 
            若有一个 t 使 Φ 为真,则 ∃ t(Φ) 为真,否则 ∃ t(Φ) 为假。 
        (4) 若 Φ 是公式,则 ∀ t( Φ ) 也是公式。其中符号 ∀ 是全称量词符号, ∀ t( Φ ) 表示: 
            如果对所有 t ,都使 Φ 为真,则 ∀ t( Φ ) 必为真,否则 ∀ t( Φ ) 为假。 
        (5) 在元组演算公式中,各种运算符的优先次序为: 
            ① 算术比较运算符最高; 
            ② 量词次之,且 ∃ 的优先级高于 ∀ 的优先级; 
            ③ 逻辑运算符最低,且 ﹁ 的优先级高于 ∧ 的优先级, ∧ 的优先级高于 ∨ 的优先级; 
            ④ 加括号时,括号中运算符优先,同一括号内的运算符之优先级遵循 ①②③ 各项。 
        (6) 有限次地使用上述五条规则得到的公式是元组关系演算公式,其他公式不是元组关系演算公式。

     

        一个元组演算表达式 {t|Φ(t)} 表示了使 Φ(t) 为真的元组集合。 
        关系代数的运算均可以用关系演算表达式来表示 ( 反之亦然 ) 。下面用关系演算表达式来表示五种基本运算:

     

        (1) 并

            R ∪ S={t|R(t) ∨ S(t)}

        (2) 差

            R - S={t|R(t) ∧ ﹁ S(t)}

        (3) 笛卡尔积

            R×S={t (n+m) |( ∃ u (n) )( ∃ v (m) )(R(u) ∧ S(v) ∧ t[1]=u[1] ∧ ... ∧ t[n]=u[n] ∧ t[n+1]=v[1] ∧ ... ∧ t[n+m]=v[m])}

            注: t (n+m) 表示 t 有目数 (n+m)

        (4) 投影

            π t1,t2,...,tk (R)={t (k) |( ∃ u )(R(u) ∧ t[1]=u[i1] ∧ ...t[k]=u[ik] )}

        (5) 选择

            σ F (R)={t|R(t) ∧ F}

            注: F 是公式。 F 用 t[i] 代替 运 算 对 象 i 得到的等价公式。

     

         例 1 查询信息系 (IS 系 ) 全体学生: 
            S IS ={Student(t) ∧ t[5]='IS'}  
         例 2 查询年龄小于 20 岁的学生。 
            S 20 ={Student(t) ∧ t[4]<20}

         例 3 查询学生的姓名和所在系。 
            S={t (2) |( ∃ u)(Student(u) ∧ t[1]=u[2] ∧ t[2]=u[5])}


        上面定义的关系演算允许出现无限关系。例如 {t| ﹁ R(t)} 表示所有不属于 R 的元组 ( 元组的目数等于 R 的目数 ) 。要求出这些可能的元组是做不到的,所以必须排除这类无意义的表达式。把不产生无限关系的表达式称为安全表达式,所采取的措施称为安全限制。安全限制通常是定义一个有限的符号集 dom(Φ) , dom(Φ) 一定包括出现在 Φ 以及中间结果和最后结果的关系中的所有符号 ( 实际上是各列中值的汇集 ) 。 dom(Φ) 不必是最小集。

     

         当满足下列条件时,元组演算表达式 {t|Φ(t)} 是安全的: 
        ( 1 )如果 t 使 Φ(t) 为真,则 t 的每个分量是 dom(Φ) 中的元素。 
        ( 2 )对于 Φ 中每一个形如 ( ∃ t)(W(u)) 的子表达式,若 u 使 W(u) 为真,则 u 的每个分量是 dom(Φ) 中的元素。 
        ( 3 )对于 Φ 中每一个形如 ( ∀ t)(W(u)) 的子表达式,若 u 使 W(u) 为假,则 u 的每个分量必属于 dom(Φ) 。换言之,若 u 某一分量不属于 dom(Φ) ,则 W(u) 为真。

     

         例 4 设有关系 R 如图 2.8(a) , S={t| ﹁ R(t)} ,若不进行安全限制,则可能是一个无限关系。所以定义

            dom(Φ)= π A (R) ∪ π B (R) ∪ π C (R)

                  ={{a1,a2},{b1,b2},{c1,c2}}


         则 S 是 dom(Φ) 中各域值中元素的笛卡儿积与 R 的差集。结果如图 2.8(b) 。注意,在做笛卡儿积时各个域中的元素不能搞混。

     

        元组.jpg

     

     

    附:其他类型举例:

    -----------------------------------------------------------------------------------------

     

    1 、下列等式中恒等的是:

     

    ① π A1,A2 ( σ F (E))≡ σ F ( π A1,A2 (E))

    ② σ F (E 1 × E 2 )≡ σ F (E 1 ) ×σ F (E 2 )

    ③ σ F (E 1 -E 2 )≡ σ F (E 1 )- σ F (E 2 )

    ④ π A1,A2,B1,B2 (ECROSS.gifE)≡ π A1,A2 (E) CROSS.gifπ B1,B2 (E)

     

    ① 当 F 包含 A1,A2 以外的限制 时 ,不恒等

    ② 当 F 包含大于 E1( 或 E2) 个数 的限制 时 ,不恒等

    ③ 恒等

    ④ 等式不可能成立,右 边没 有相同 属 性

     

    2 、以下元 组 的意 义 :

     

    {t|( ∃ u)((R(u) ∨ S(u)) ∧ ( ∀ v)(T(v)→( ∃ w)((R(w) ∨ S(w)) ∧ w[1]=u[1] ∧ w[2]=v[1] ∧ w[3]=v[2])) ∧ t[1]=u[1]}

     

    据 说 是表示 R ∪ S ÷ T 的意思,但是我 实 在是看不 懂 。

     

    3 、以下元 组 表 达 式 转换为关 系代 数 表 达 式

     

    {t| ∃ u ∃ v(R(u) ∧ S(v) ∧ u[3]=v[1] ∧ u[4]=v[2] ∧ u[1]>v[3] ∧ t[1]=u[2])}

    其中 R(A,B,C,D) S(C,D,E)

     

    关 系代 数 表 达 式 为 : π B ( σ A>E (RCROSS.gifS))

     

    4 、把下列 关 系代 数 表 达 式 转换为 元 组 表 达 式

     

    π 1,4 (RCROSS.gifS)

    其中 R(A,B,C) S(B,D)

     

    元 组 演算表 达 式 为 : {t| ∃ u ∃ v(R(u) ∧ S(v) ∧ u[2]=v[1] ∧ t[1]=u[1] ∧ t[2]=v[2])}

     

    5 、 关 系代 数 表 达 式 → 元 组 演算表 达 式

     

    π 1,5,6 ( σ 1>5 (R×S)) -- 注意中 间 是乘法不是自然 连 接

    其中 R(A,B,C) S(A,B,C)

     

    {t| ∃ u ∃ v(R(u) ∧ S(v) ∧ u[1]>v[2] ∧ t[1]=u[1] ∧ t[2]=v[2] ∧ t[3]=v[3])}

     

    6 、下列 查询 效率最高的一 组 是:

     

    ① E1= π A,D ( σ B<'2007' ∧ R.C=S.C ∧ E='80' (R × S))

    ② E2= π A,D ( σ R.C=S.C ( σ B<'2007' (R) ×σ E='80' (S)))

    ③ E3= π A,D ( σ B<'2007' (R) CROSS.gifσ E='80' (S))

    ④ E4= π A,D ( σ B<'2007' ∧ E='80' (RCROSS.gifS))

     

    答案是 ③ ,很明 显 自然 连 接要 优 于笛卡尔 积 ,先 运 算再投影 优 于 先投影再 计 算


               

    再分享一下我老师大神的人工智能教程吧。零基础!通俗易懂!风趣幽默!还带黄段子!希望你也加入到我们人工智能的队伍中来!https://blog.csdn.net/jiangjunshow

    展开全文
  • 候选码(Candidate Key):能唯一标识关系元组的一属性或属性集 性质:唯一性,最小性 二、关系的主码外码 主码(Primary Key):从多候选码中选择一作为查询、插入或删除元组的操作变量,被选用的候选码...
  • 关系元组演算

    2016-10-20 21:12:00
    s∈R,表示元组s属于关系R s[A] ⊙ c,,⊙是运算符 s[A]⊙ u[B] 下面是关于原子公式的例子 存在量词与全称量词的运用 全称存在量词在涉及到多表的操作时需要用到 存在量词...
  • 元组关系演算和域关系运算

    千次阅读 2009-10-19 13:40:00
    v在元组演算中,元组关系演算系演算表达式(简称为元组表达式)是以元组变量为单位。记作: {t|Φ(t)} v其中t是元组变量,Φ(t)是由原子公式运算符组成的公式。 v如果元组变量前有“全称量词”... t是关系R中的元组
  • 元组关系的演算

    2014-02-26 17:13:00
    然后再对这种情况下定义的演算作适当的修改,保证关系演算中的每一公式表示的是有限关系。 在元组关系演算系统中,称 {t|Φ(t)} 为元组演算表达式。其中 t 是元组变量, Φ(t) ...
  • 元组关系演算 之前学习了一下关系代数表达式,现在再学习一下元组关系的演算,这样就全了。这篇东西的符号打出来费了好多时间,比较麻烦,还好看着还能看懂,关键是全文本的,好下面开始正文。 为了讨论方便,先...
  • 元组和列表

    2019-04-16 10:01:40
    元组和列表一、序列类型1、序列2、序列类型的6通用操作符3、序列类型的6通用函数4、可变与不可变数据类型二、元组1、元组2、元组的用法3、元组的应用场景三、列表1、列表2、列表类型操作函数方法3、列表推导式...
  • 关系T的元 = r+s
  • Python中的基本数字类型包括:数字(整形、浮点、布尔、复数),字符串,元组,列表,集合,字典... // 与分母分子的数据类型有关系,不一定是整数类型的 整型浮点型混合计算后,结果为浮点型 在交互模式中,最后
  • 离散数学入门级概念:集合、关系元组 习题 1: { 0 , 1 , { 0 , 1 } , { 1 , 2 } } {0, 1, {0, 1}, {1, 2}}{0,1,{0,1},{1,2}} 有几元素? 机器学习中, 这类形式的集合有什么优点缺点? 有4元素
  • 数据库中元组关系演算 table, th, td { border: 1px solid black; } table, th, td { border: 1px solid black; } Tuple Relational Calculus is a non-procedural and declarative query language. The ...
  • 概念的内涵外延:任何一概念都有内涵外延,这是概念的基本特征。外延指所反应对象的具体范围、具体事物。内涵指概念所反应的特征本质属性。 习题 1: { 0 , 1 , { 0 , 1 } , { 1 , 2 } } 有几元素? 机器...
  • 列表、元组和字典

    2020-07-15 21:29:38
    python内置常用的数据结构,列表和元组相似,它们都顺序保存元素,每元素都有自己的索引,列表元素通过索引来访问元素。区别元组不可修改,列表可以修改。字典是key-value形式保存数据。 3.1序列 序列指的是一种...
  • 解释下述名词关系模型,关系模式,关系实例,属性,域, 元组,超键,候选键,主键,实体完整性规则,参照完整性规则,过程性语言,非过程性语言,无限关系,无穷验证。2. 为什么关系中的元组没有先后顺序?3. 为...
  • 离散的含义是指不同的连接在一起的元素,主要是研究基于离散量的结构相互间的关系,其对象一般是有限或可数个元素。 集合 习题 1: { 0 , 1 , { 0 , 1 } , { 1 , 2 } } 有几元素? 机器学习中, 这类形式的集合有...
  • 机器学习中, 这类形式的集合有什么优点缺点?习题2:∅ 的基数是多少? { ∅ }呢?习题5: 多标签学习中, 输出为一向量,相应的学习器算不算函数呢?习题 6: 元组只能表达对象的数据部分, 还是可以完整地表达 (既...
  • 关系模型 1.关系数据结构 铺垫: 域:具有相同数据类型的值的集合 笛卡尔积:所有域取值的任意组合 a....) b....行→元组 ...介绍关系及各类定义: ...(3)属性(n目关系有n属性) 例:表格的列 (4)码 候...
  • 1、并:设有两个关系R和S,它们具有相同的结构。R和S的并是由属于R或属于S元组组成的集合,运算符为∪。记为T=R∪S。2、差:R和S的差是由属于R但不属于S元组组成的集合,运算符为-。记为T=R-S。3、交:R和S的...
  • python中str(字符串)、list(列表)、tuple(元组)、dict(字典)相互转化关系及字典键-值遍历 #!/usr/bin/env python #coding=utf-8 def main(): strs = "this is a cjh's str" lst = ['this', 'is', 'a', ...
  • 5. 列表、元组和集合

    2020-02-27 21:19:38
    5. 列表、元组和集合 文章目录5. 列表、元组和集合1. 序列类型2. 序列类型:列表2.1 用下标取得列表中的单个值2.2 负数下标2.3 利用切片取得子列表2.4 用len()取得列表的长度2.5 用下标切片改变列表中的值2.6 列表...
  • 列表、元组和字符串

    2020-07-28 23:01:43
    元组<class 'tuple'> 字典<class 'dict'> 集合<class 'set'> 字符串<class 'str'> 1. 列表的定义 列表是有序集合,没有固定大小,能够保存任意数量任意类型的 Python 对象,语
  • 前面一张主要学习了Python的安装,以及第一程序helloword的编写,以及简单的输入输出函数,这章主要介绍序列,列表,元组 序列  这章主要介绍的是列表和元组,而列表和元组是序列的六种内型中的两种,主要区别...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 24,700
精华内容 9,880
关键字:

关系r和关系s的元组个数