第三章数据库查询

第三章数据库查询技术

1.关系数据库中的递归查询.2.对象数据库查询语言(OQL)3.基于XML的查询技术(XSLT,Xquery)第一节数据逻辑DATALOG一演算规则：

1.比较谓词2.关系谓词导出关系谓词，基本关系谓词

3.域变量与哑元

4.规则：规则头规则体5.查询：由一组规则组成。对规则的说明：规则头：只能是导出关系谓词。规则体：原子谓词原子谓词的否定用(and)连接以上两类谓词。例如：T(x,y,z)S(x,y,z)ANDx>1R(x,y)NOTQ(x,y)规则的语义变量的作用域是一条规则。关系谓词的作用域是一个查询（全局的)每一个导出关系谓词都对应一个需要求解的关系，关系由所有满足规则体的元组构成。例10T(x,y,z)S(x,y,z)ANDx>1T:S:ABD123231ABD231又一例例10.T(x,y)S(x,y,-)R:T(x,y)R(x,z,y)

请问：T的值是多少？

S:ABC123323131ABD123231二.逻辑公式的转化1.非内置否定的转化：

NOT（AANDB）=NOTAANDNOTBOR条件的转化：

AORB转化为两条规则。如：T(x)S(x,y,z)and(x=1orx=2)变为T(x)S(x,y,z)andx=1T(x)S(x,y,z)andx=2三规则的安全性条件作用：排除无限关系。安全条件：在规则中所出现的变量必须在规则体中非否定的关系谓词中出现。如：

Q(x,y)R(x)andy>0P(x,y)notS(x,y,z)andz=1Q(x,y)R(x)四规则的求解建立各关系的笛卡尔积一致性检查。若规则体为真，将元组加入导出关系中。例12设R={<1,2>,<5,3>,<3,3>},S={<2,2>,<3,4>}求规则Q(x,y)R(x,z)andS(z,y)andx>1notS(x,y).求解过程

RS一致性X>1NOTS(x,y)(1,2)(2,2)tf(1,2)(3,4)f(5,3)(2,2)f(5,3)(3,4)ttt(3,3)(2,2)f(3,3)(3,4)???五描述关系代数并集：交集：差集：续笛卡尔集：Q(x,y,s,t)R(x,y)andS(s,t)投影：Q(x,y)R(x,y,z)自然连接：设R(A,B),S(B,C)Q(x,y,z)R(x,y)andS(y,z)其它的运算请同学自己考虑。Datalog的应用求信息和会计学院的学生求选了数据库的学生学号SJK(x)XK(x,y,-)andKC(y,z,-)andz=“数据库“

第二节关系不动点与递归查询

一.关系代数的不动点设：y=f(x)是关于x的代数式子，若有r使得r=f(r)成立，则称r为该关系式的不动点。在所有不动点中行数最小的关系称为最小不动点。例：求下列式子的不动点：

f(r)=Sr设s={<1,2>,<1,3>}，r与s同模式。则：r0=,r1=s是不动点。

DATALOG中的递归查询递归查询：在规则中，导出关系谓词在规则头和规则体中同时出现。如：Q(x,y)R(x,y)andQ(y,z)二递归查询的求解递归查询的解是其代数方程的最小不动点。求解方法：1).令r0=2).计算f(),3).若成立，则算法结束否则，继续迭代。

三求最小不动点举例

设S(A,B)={(1,2),(2,1)},R(B,C),f(r)=srs,求f(r)的最小不动点.

r1=sr2={(1,2),(2,1),(1,1),(2,2)}r3=r2r3为所求.四递归查询语句

1.递归查询语句的格式

WITH[RECURSIVE]表(属性集)

AS(子查询)….

SELECT语句；说明：1.RECURSIVE当表是递归查询时使用，作为临时表时不用。2.属性集定义表的结构。

3.子查询描述递归表的查询4.在WITH语句中可定义若干张递归表或临时表。5.With子句中定义的临时表只能在该语句内使用。

2举例

以下是各航空公司的总航班表

HBHQDZDQFSJDDSJHKGSCA1329北京广州20：0022：45国航CA174北京广州15：0017：55国航CZ3367广州武汉18：5020：10南航CZ8133广州昆明12：1013：50南航FM364武汉上海11：3013：00上航MU4316武汉昆明15：5017：45东航ZH986昆明深圳11：4013：25深航CZ6785深圳三亚15：4016：50南航

根据以上航班表，完成如下查询：求可达城市求国航的可达城市求当天的可达城市求不可达城市求武汉的可达城市求北京的不可达城市1的解WITHKDCSB（QD，ZD）AS（SELECTQD，ZDFROMHBB）；

RECURSIVE

KD（QD，ZD）AS（SELECTKD.QD,A.ZDFROMKD,KDCSBAWHEREKD.ZD=A.QDUNIONKDCSB);SELECT*FROMKD

2的解

WITHKDCSB（QD，ZD）AS（SELECTQD，ZDFROMHBBWHEREHKGS=“国航”）；

RECURSIVE

KD（QD，ZD）AS（SELECTKD.QD,A.ZDFROMKD,KDCSBAWHEREKD.ZD=A.QDUNIONKDCSB);SELECT*FROMKD

五不可终止的递归查询例：设p(x)={1,2},分析下列递归查询。

withrecursiveR(x)asselect*

fromSuionp;recursiveS(x)asselectsum(x)fromR;select*fromR.

这是不可终止的间接递归。第三节对象数据库的建立

一对象数据库模式的建立定义类及联系例：建立图书借阅模式：

classbooks(keybcode,extentbook){attributestringbcode;attributestringtitle;relationshipreaderborrowedinversereader::borrow;}

classreaders(keyrcode,extentreader){attributeintegerrcode;attributestringname;relationshipset<books>borrowinversebooks::borrowed;}

二类实例的建立1利用insert语句建立

insertintobook(bcode,title)values(“sp00001”,”datastructure”)

对象的存储示意图：

oidvalues

2.利用主语言new和makePersistent

如：booksb=newbooks();b.bcode(“sp00001”);b.title(“datastructure”);b.makePersistent()

说明：makePersistent用于使对象b成为数据库中的对象，以区别内存中的对象。1123sp00001,datastructure

三联系的实现1.建立联系方法：

addrelationship

例：张三借了datastructure一本书

r.addborrow(b)b.addborrowed(r)2联系存储形式：

R#oidB#oid第四节对象数据库查询一简单查询1.基本格式：

select目标项

from类实例[as]变量，…

where条件注意：实例变量可以成为目标项，这与关系不同。

2路径表达式：用以确定对象݈݈݈݈݈，属性值，方法的带点的式子。如：

o.p1.p2….O是实例变量代表对象。.若p1是联系名，则o.p1为被联系的对象。.若p1是属性，则o.p1的值为该对象的属性取值。.若p1是方法，则o.p1是该对象作用于p1方法的结果。例如：设o=#1123,则o.title=“datastructrue”，o.borrowed=#1234(某一读者).

3.简单查询举例例1求书名为datastructure的所有图书。

selectbfrom

bookbwhereb.title=“datastructure”

说明；产生相同书名为“datastructure”的书的oid集合。思考：若将selectb改为selectb.bcode

,结果如何？

连接查询例2.求读者张三所借的书。解一：selectbfrombookb,readerrwhere=“张三“解二：selectbfromr.borrowb,readerrwhere=“张三“思考：以上查询哪一个对，如要求所借书的书名呢？

二子查询在对象数据库中允许在查询的三要素中都引入查询。1.在select子句中引入子查询例3题目同例2。

select(selectbfromr.borrowb)fromreaderrwhere=“张三“

2在from语句中引入子查询例4求张三所借的科学出版社的书名和书号（设在books类中增加了publisher属性).

selectb.bcode,b.titlefromreaderr,(selectxfromr.borrowx

wherex.publisher=“科学出版社“)bwhere=“张三“3.在WHERE语句中引入子查询例谁借了书名为“database”的图书。

selectr.rcode,fromreaderrwherer.borrow.bcodein(selectb.bcodefrombookbwhereb.title=“database”)

三带量词的查询1存在量词的查询格式：EXISTSxINS:C(x)

说明：.S

是由路径表达式所确定的集。.X是指S中的对象变量。.C(x)指明集合S中对象应满足的条件。作用：当S中有对象满足条件C时，存在量词为真。否则为假。

例5求凡借了科学出版社出版的书的读者。

selectrfromreaderrwhereEXISTSxINr.borrow:x.publisher=“科学出版社”2.全称量词的查询格式：ALLxINS：C(x)

作用：当S集合中的所有元素都满足条件C时，ALL量词为真，否则为假。

例6求只借了科学出版社的书的读者。

selectr

fromreaderrwhereALLxINr.borrow:x.publisher=“科学出版社”

四统计查询1.常用的统计函数。与SQL相同。2.与SQL语言的区别：.查询语句可做为统计函数的参数。如：count(selectbfromreadr,r.borrowbwhere=“张三“）.在带子查询的统计中，可以省略groupby语句。

例7统计每个读者所借书中是科学出版社出版的本数。

selectr.rcode,count(selectbfromr.borrowbwhereb.publisher=“科学出版社“)

fromreaderr。

练习题：1.建立学生选课的对象数据库。2.求学号为“20021234”的同学所选课的成绩。要求输出：姓名，所在学院，课程名，成绩。3.求每门课的最高分，输出：课程名，成绩。

第五节基于XML的查询

一XSLT(ATransformationLanguageforXML),也称stylesheet.

含义：以XML的格式，实现对XML文档进行查询和格式转换的处理器器。1.查询树：XML文档在计算机内部的存放形式。

XML文档通过如下变换规则，成为查询树。

把文档中标签，属性，正文，都映射为树中的节点。用标签名或属性名标识节点名，节点之间的关系按下列规则规定。

.第一个元素标签成为根节点.直接跟在元素后面出现的元素成为它的E子女节点(元素节点）。.出现在元素中的属性，成为该节点的A子女节点(属性节点).

属性节点用@属性名，正文节点用text()表示。例8图书文档books.xml的查询树。

booklistbooktitlepublisherbookidDatabasepearsonauthor

2.Xpath:查询路径表达式作用：确定查询树中的节点集合。路径：在树中从先辈节点到后辈节点的节点序列。.绝对路径：从根节点开始的路径。如：\book,\book\author.相对路径：由当前节点开始的路径。设book为当前节点，author\name为相对路径，指向所有的作者的姓名。.短路径:在树中找指定节点。如：\\book,

注意：他不受节点层次的限制。与\book有区别。

.通配符*:表示任意节点。如：\book\*的值是book的所有节点。.属性标识符@,如：@bookid.带查询条件的路径表达式格式：xp[条件]作用：查找指定路径上满足条件的节点。如：\book[@bookid=“1234”]

\\book[author\name=“ullman”]

思考：以上两个路径表达式的值是什么？

XSLT查询的结构1.顺序结构：.复制；<xsl:copy-ofselect=路径表达式/>作用：复制指定节点以及其下属节点。例9求所有出版社。（基于book.xml)<?xmlversion=“1.0”?><publishersxmlns:xsl=/1999/xsl/Transform

xsl:version=“1.0”><xsl:copy-ofselect=“//book/publisher”/></publisher>.

.求值：<xsl:value-ofselect=路径表达式/>作用：取出节点的正文值。注意：.若节点非正文节点，其值为空.只取节点的正文内容。若例9中用<xsl:value-ofselect=//book/publisher/>代替copy-of,结果有何不同？

2.分支结构：格式；<xsl:iftest=条件>….</xsl:if>

作用：若条件为真，则执行条件标签的内容。否则，不执行。如：<xsl:iftest=/book/@bookid=“1234”><title1><xsl:copy-ofselect=“/book/title”/></title1></xsl:if>

3.循环结构格式：<xsl:for-eachselect=路径表达式>…</xsl:for-each>

作用：对路径表达式决定的所有节点，重复执行循环体的内容。例10求科学出版社出版的所有书名。

<?xmlversion=“1.0”?><titlelist

xmlns:xsl=/1999/xsl/Transform

xsl:version=“1.0”><xsl:for-eachselect=“//book”><xsl:iftest=“publisher/text()=“科学出版社””><xsl:value-ofselect=“title”/></xsl:if></xsl:for-each></titlelist>

4.XSTL的调用与执行在文档中前部加入stylesheet文件名和位置语句：<?xml-stylesheettype=“text/xsl”href=/book.xsl?>

由XML处理器按book.xsl程序进行处理，产生结果文档资料。由例10产生的结果如下：<titlelist>…一组书名….</titlelist>

三XSLT查询模板1.用于查询XML文档的XML程序，称为XML查询模板。2.构成：.XSLT的名字空间.匹配路径.结果标签.查询处理3.模板定义格式；

<xsl:templatemath=路径表达式>处理语句</xsl:template>

作用：当文档中的节点与路径表达式的节点一致时，执行处理语句。4.例11利用模板技术查询所有书名

利用模板求书名.xsl.doc递归查询定义:在模板中利用模板调用语句进行查询.

调用语句;

apply-templates

作用:.设置当前节点..对当前节点的et子女节点选择匹配模板执行.缺省模板:<xsl:templatemath=“*|/”><xsl:apply-tmplates/></xsl:template>例12以下是查询book.xml中科学出版社所出版的图书书名。

递归查询书名.xsl.doc

6.递归查询原理:.匹配.调用(匹配模板,缺省模板)，处理。

.设置当前节点..再匹配。

四Xquery

查询语言基于XML文档的类SQL语言的查询语言。1.基本格式：

FOR变量说明

WHERE条件

RETURN结果2.说明：路径变量：用以表示查询范围的变量。其值域为节点集合。格式：$变量

indocument(url)路径作用：url:XML文档所在位置，指出变量的值域为路所指定的节点集合。如：$bindocument(/book.xml)//books

查询条件：查询变量所规定的节点集合中应满足的条件。查询结果：由满足条件的结果集组成。结果集的处理方式：.路径选择：用路径表达式选择结果集节点的后辈节点$c/book/title.XML片段：<frage>……..</frage>

例13.求书号为“sp00001”的书名已知：文档名为；/book.xml

for$bindocument(/book.xml)//bookfor$b/@bookid=“sp00001”return$b/title

输出形式：<title>database</title>

若将上述查询嵌入<booktitles>….</booktitles>

应做何修改？

例14.若将例13中的输出改为书名和出版社，且输出格式为：<bookbookid=书号publisher=出版社/book>for$bindocument(/book.xml)//bookfor$b/@bookid=“sp00001”return<bookbookid=$b/title/text()publisher=$b/publisher/text()/>

注意：若要求将输出改为<book

bookid=书号><publisher>

出版社</publisher>呢？

4.Xquery中的嵌套查询格式：FOR

变量说明

WHERE条件

RETURN（FOR变量说明

WHERE

条件

RETURN结果）

Xquery嵌套是在结果查询中的嵌套。注意：外层中的变量允许在内层中使用，内层中的变量不允许在外层中使用。

例15在学生文档中，求选了每一门课的学生列表。其输出格式为：<crstakenrosters><crstakenrostercrscode=课号><studentstudid=学号><name>姓名</name></student>…</crstakenroster>…</crstakenrosters>

<crstakenrosters>for$cindistinct(document(/abc.xml)//crstaken)return(<crstakenroster

crscode=$c/@crscode>for$dindocument(/

Abc.xml)//studentwhere$d/crstaken/@crscode=$c/@crscodereturn$d/name</crstakenroster>)</crstakenrosters>

以上查询的结果为：<crstakenrosters><crstakenrostercrscode=“cs308”><name>猪八戒</name><name>孙悟空</name></crstakenroster>…</crstakenrosters>

思考：在以上输出文档中，是否会出现重复的课程号？

5.嵌套查询执行流程分析.For$c中的所有节点做

for对$d中的所有节点做如果课号相同，则输出学生姓名。

endforendfor

参见学生选课文档。思考题；如果在abc.xml中增加所在学院，在输出模板中，增加所在学院的输出，对例15应做何修改？一个学生选课XML文档2.doc

<crstakenrosters>