精华内容
下载资源
问答
  • 关系代数 关系代数(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

    展开全文
  • 关系代数五个基本操作可直接转换成元组关系演算表达式,它们是:并、差、笛卡尔积、投影和选择。 口诀:选择选行,投影选列,连接合并去残,笛卡尔积两两交合,自然连接笛卡尔积后选择等值然后去掉重复属性。 ...

    关系代数的五个基本操作可直接转换成元组关系演算表达式,它们是:并、差、笛卡尔积、投影和选择。

    口诀:选择选行,投影选列,连接合并去残,笛卡尔积两两交合,自然连接笛卡尔积后选择等值然后去掉重复属性。

    转载于:https://www.cnblogs.com/dyc-1234/p/6794856.html

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

    千次阅读 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))
    在这里插入图片描述

    展开全文
  • 数据库中存储了大量关系(表)之后,要对其进行增删查改等操作,其一般通过SQL类语言来实现,而语言实现基础就是对关系进行一定集合(关系代数)或逻辑处理(关系演算、域演算),然后返回处理结果。...

    数据库中存储了大量的关系(表)之后,要对其进行增删查改等操作,其一般通过SQL类语言来实现,而语言实现的基础就是对关系进行一定的集合(关系代数)或逻辑处理(关系演算、域演算),然后返回处理结果。

    1、关系代数:以并、差、笛卡尔积、选择、投影、更名为基本操作,以交、连接、关系除为扩展操作。

    连接是比较复杂且重要的一个概念,有以下几个形式:

    ①、theta连接,theta为判断条件。eg:(其中theta为大于、小于、等于、不等于、大于等于、小于等于)

    ②、自然连接。eg:(theta连接中的默认等值连接,但是会删除RS中的相同属性栏)


    ③、外链接。


    另一个需要说明的是除操作:

    A/B,两个关系相除的前提是B是A的真子集,返回关系为A中包含关系B中的元组。


    2、元组演算:

    基本形式:{ t | P(t)},其中 t 为元组, P(t)为元组公式,包含3种最基本公式:

    t[a] theta c,  t[a] theta t1[b]  ,  t 属于 关系R

    这三种公式可以采用(按优先级排序)括号、theta、存在量词、全称量词、非、与、或,进行扩展,以实现高级操作。


    3、域演算:

    域演算与元组演算类似,不过谓词为域(属性)的集合,eg:

    {<a,b,c,d> | P(<a,b,c,d>)}

    其三种基本公式与元组演算相似,扩展操作相同。

    eg:

    值得注意的是,以上三种操作是可以等价互换的,其唯一不同的是谓词分别为关系、元组和域。

    举一个列子来说明以上操作的组合和互换如下:(分别使用了关系代数和元组演算实现)



    展开全文
  • 数据库基础之关系代数和关系演算

    千次阅读 2016-04-05 16:10:54
    连接运算,用来将两个关系中的相关元组组合成单个“更长的元组”,这个运算可以处理关系间的联系。  连接运算可以分解为:先进性一个笛卡尔积,接着再进行一个选择运算,其一般形式为 …AND…AND…。  连接运算...
  • 第2章 关系数据库

    2021-03-30 01:12:11
    文章目录2.1 关系数据结构及形式化定义2.1.1 关系域笛卡尔积关系2.1.2关系模式...关系运算选择投影连接除运算2.5 关系演算2.5.1 元组关系语言ALPHA检索操作更改操作2.5.2 元组关系演算2.5.3 域关系演算语言检索操
  • 关系操作: 常用关系操作: 查询操作:选择、投影、连接、除、并、...元组关系演算语言 谓词变元基本对象是元组变量 代表:APLHA, QUEL 域关系演算语言 谓词变元基本对象是域变量 代表:QBE 具有关系代数和关.
  • 关系代数 关系代数表达式 附加关系代数运算 不增强表达式能力 集合交 自然连接 赋值运算 外连接 ...元组关系演算 域关系演算 以上三种能力等价 SQL基于关系代数,QBE,Datalog基于后两种 ...
  • 能坚持看到最后朋友可以评论区打卡哦 数据库2_2——关系代数1. 关系操作2. 关系完整性2.1 实体完整性2.2 参照完整性2.2.1 关系间引用2.2.2 外码(Foreign Key)2.2.3 参照完整性规则2.3...元组关系演算语言 谓词变
  • 文章目录6.1 关系代数6.1.1 基本运算6.1.2 关系代数形式化定义6.1.3 附加关系代数运算6.1.4 扩展关系代数运算6.2 元组关系演算6.2.1 查询示例6.2.2 形式化定义6.2.3 表达式安全性6.2.4 语言表达能力6.3 域...
  • 关系代数基本运算 选择运算:选出满足给定谓词的元组。 例:选择instructor关系中属于physics系的元组 投影运算: ...元组关系运算查询实例形式化定义表达式的安全性语言的表达能力域关系演算形式化定义查询
  • 关系演算语言:元组关系演算语言和域关系演算语言 关系代数语言:通过关系代数运算符完成运算,包括集合运算符、专门关系运算符,有并、差、交、笛卡尔积、选择、投影、连接、除。 SQL语言:具有关系代数和关系...
  • 数据库关系模型与关系运算,关系代数运算,元组演算,域演算,设计一个数据库,能用这三种分别描述任何一种操作,则证明此数据库设计是良好,关系代数操作用,投影,更名,选择连接,自然连接,外连接,左外右外...
  • 数据库设计原理基础知识点

    千次阅读 2020-05-12 11:45:16
    元组关系演算 SQL 规范化理论 部分函数依赖:AB->C, A->C 传递函数依赖:A->B, B->C(B-/>A) 超键:唯一标识元组(可以是一个属性,也可以是多个属性,切可能存在冗余属性) 候选键:唯一标识...
  • 关系演算语言:元组关系演算语言和域关系演算语言。 SQL:具有关系代数和关系演算双重特点语言。 这些关系数据语言共同特点是,语言具有完备表达能力,是非过程化集合操作语言,功能强,能够嵌入高级语言中...
  • 关系演算语言:元组关系演算语言和域关系演算语言。 SQL:具有关系代数和关系演算双重特点语言。 这些关系数据语言共同特点是,语言具有完备表达能力,是非过程化集合操作语言,功能强,能够嵌入高级语言中...
  • 5、外连接(左外连接、右外连接、全外连接) 上面的含义要理解,还要能看懂其关系代数的表现形式还要看懂其元组演算表达式,拿连接举例分别如下所示: 认真掌握连接的三种形式和外连接的三种形式及两者的区别。...
  • 数据库 1、E-R图 2、键 超键 候选键 主键 外键 主属性(所有候选键中所有属性) 非码属性 3、关系代数 4、范式 1NF 每列原子性 2NF 没有部份依赖 3NF 没有传递依赖 5、无损连接 ...6、元组演算 ...
  • 数据库复习(二)

    2019-06-22 13:03:08
    sql复习(2)关系模型基本概念基本术语键关系模型三类完整性规则关系代数投影选择连接自然连接除法关系代数7个扩充操作关系演算 关系模型基本概念 基本术语 关系模型( Relational Model):用二维表格表示...
  • 6.6.2 元组关系演算表达式与公式 134 6.6.3 存在量词与全称量词 134 6.6.4 使用存在量词查询示例 135 6.6.5 查询图表示法 136 6.6.6 全称量词与存在量词转换 137 6.6.7 使用全称...
  • 关系模式2关系操作3关系完整性4关系代数5关系演算三、关系数据库标准语言sql1数据定义模式定义表定义视图定义索引定义2数据查询单表查询选择若干列选择若干元组order by排序聚集函数(统计值)group by连接...
  • 关系模型叙述错误是 用二维表表示关系模型是其一大特点 微机 DBMS 绝大部分采取关系数据模型 不具有连接操作 DBMS 也可以是关系数据库系统 建立在严格数学理论集合论和谓词演算公式基础之上 在数据库关系...
  • 9.4.2 使用半连接的分布式查询处理 191 9.4.3 查询和更新分解 191 9.5 分布式数据库中并发控制和恢复概述 193 9.5.1 基于识别数据项副本的分布式并发控制 194 9.5.2 基于投票方法的分布式并发...
  • 数据库系统导论(第7版)

    热门讨论 2011-09-19 10:23:22
    7.4 关系演算与关系代数比较 149 7.5 计算能力 152 7.6 域演算 153 7.7 SQL语言 155 7.8 小结 162 练习 163 参考文献和简介 165 部分练习答案 167 第8章 完整性 179 8.1 引言 179 8.2 类型约束 180 8.3 属性约束 ...
  • 7.4 关系演算与关系代数比较 149 7.5 计算能力 152 7.6 域演算 153 7.7 SQL语言 155 7.8 小结 162 练习 163 参考文献和简介 165 部分练习答案 167 第8章 完整性 179 8.1 引言 179 8.2 类型约束 180 8.3 属性约束 ...
  • 7.4 关系演算与关系代数比较 149 7.5 计算能力 152 7.6 域演算 153 7.7 SQL语言 155 7.8 小结 162 练习 163 参考文献和简介 165 部分练习答案 167 第8章 完整性 179 8.1 引言 179 8.2 类型约束 180 8.3 属性约束 ...
  • 7.4 关系演算与关系代数比较 149 7.5 计算能力 152 7.6 域演算 153 7.7 SQL语言 155 7.8 小结 162 练习 163 参考文献和简介 165 部分练习答案 167 第8章 完整性 179 8.1 引言 179 8.2 类型约束 180 8.3 属性约束 ...
  • 语言是一种介于关系代数与关系演算之间语言,其功能主要包括数据定义、查询 操纵和控制四个方面,通过各种不同语句米实现。按照所实现功能, 语句分 为以下几种 数据库、登录、用户、模式、基表、视图、索引...
  • 哈工大数据库系统 上 学习笔记专用名词介绍什么是数据库管理系统关系 (不同的数据组合后形成的东西 )关系模型什么是关系关系特性关系上的重要概念总结关系演算 (取出你想要的元组和属性)关系代数自然连接关系元祖...

空空如也

空空如也

1 2
收藏数 29
精华内容 11
关键字:

连接的元组关系演算