数据结构与算法“数据结构应用”教学设计 北京大学信息科学技术学院高军 1.数据结构应用在课程中的定位和前测知识点 数据结构应用将运用所学习的数据结构的知识,解决实际问题,其目的是加深学生对数 据结构基本理论的认识和理解,综合运用所学的知识,增强学生分析问题、解决问题的能力。 数据结构应用一章主要介绍关系数据库连接算法和XML数据查询算法。希望学生能够 理解两种数据模型,掌握数据模型之上的核心操作,进行代价分析,并学会实验性能比较方 法。根据数据分布特点和处理要求,编写合适的排序算法。 前测知识点要求如下,可以根据需要给学生补充 (1)B+树、Hash表概念 (2)缓存管理的概念; (3) XPath查询的概念 (4)DOM树、SAX解析的概念 2.学习目标 (1)提高根据客观需求,综合运用多种数据结构解决客观问题的能力 (2)熟悉数据库连接操作各种算法,比较他们在最坏、最好、平均情况下的复杂度 (3)熟悉ⅹML数据解析的两种主要技术,熟悉两种解析方式下的查询处理算法 3.知识点和学时分配 理论授课2学时,建议安排实验4学时 以下内容是本课程要求的基本教学内容,在授课中必须完全涵盖,主讲教师可以根据学 生的状况、教师的科研背景等在某些方面进行扩展和对学生进行引导,以扩大适当学生的涉 猎面 各知识点建议授课时间如下: 数据库连接算法 小时 XML数据查询算法1小时 4.重点和难点 数据结构应用的重点如下 (1)数据库中的块嵌套连接算法 (2)数据库中的哈希连接算法 (3)数据库中的归并连接算法 (4)数据库中的索引嵌套连接算法 (5)XML的DOM树解析和 XPath的执行算法 (6)XML的SAX解析和 XPath的执行算法 内排序难点如下 (1)索引连接算法
数据结构与算法“数据结构应用”教学设计 北京大学信息科学技术学院 高军 1. 数据结构应用在课程中的定位和前测知识点 数据结构应用将运用所学习的数据结构的知识，解决实际问题，其目的是加深学生对数 据结构基本理论的认识和理解，综合运用所学的知识，增强学生分析问题、解决问题的能力。 数据结构应用一章主要介绍关系数据库连接算法和 XML 数据查询算法。希望学生能够 理解两种数据模型，掌握数据模型之上的核心操作，进行代价分析，并学会实验性能比较方 法。根据数据分布特点和处理要求，编写合适的排序算法。 前测知识点要求如下，可以根据需要给学生补充 （1）B+树、Hash 表概念； （2）缓存管理的概念； （3）XPath 查询的概念； （4）DOM 树、SAX 解析的概念； 2．学习目标 （1）提高根据客观需求，综合运用多种数据结构解决客观问题的能力； （2）熟悉数据库连接操作各种算法，比较他们在最坏、最好、平均情况下的复杂度； （3）熟悉 XML 数据解析的两种主要技术，熟悉两种解析方式下的查询处理算法。 3. 知识点和学时分配 理论授课 2 学时，建议安排实验 4 学时。 以下内容是本课程要求的基本教学内容，在授课中必须完全涵盖，主讲教师可以根据学 生的状况、教师的科研背景等在某些方面进行扩展和对学生进行引导，以扩大适当学生的涉 猎面。 各知识点建议授课时间如下： 数据库连接算法 1 小时 XML 数据查询算法 1 小时 4．重点和难点 数据结构应用的重点如下： （1） 数据库中的块嵌套连接算法 （2） 数据库中的哈希连接算法 （3） 数据库中的归并连接算法 （4） 数据库中的索引嵌套连接算法 （5） XML 的 DOM 树解析和 XPath 的执行算法 （6） XML 的 SAX 解析和 XPath 的执行算法 内排序难点如下： （1） 索引连接算法
(2)各种连接算法的稳定性和时间复杂度 (3)DOM树中递归执行 XPath的算法 (4)SAX解析模型中的 XPath查询执行算法 5.授课提示 开展研究型教学,挖掘知识背后的内容,通过提出问题、探讨方法、研究思想、比较性 能,培养学生的创新意识、创新能力 下面是数据库应用的重点和难点内容的讲授注意事项。 (1)数据库的连接算法 数据库的连接算法是数据库运算过程中代价较高的操作。目前,已经提出了多种经典算 法 块嵌套连接循环调入外关系中数据块,通过循环访问内关系中的每一数据块,判定连连 接条件成立,输出连接结果。 索引嵌套连适应等值连接或自然连接;索引嵌套连接需要在内关系的连接属性上存在索 引,或者动态为连接操作而构造一个索引;对外关系r的每个元组tr,利用索引查找内关系 s的与t满足连接条件的元组。 归并连接将两个关系在连接属性上排序,其连接步骤类似于排序-归并算法的归并阶段 主要不同在于连接属性中重复值的处理;归并连接只能用于等值连接和自然连接;每个块只 需要读一次。 哈希连接适合等值连接和自然连接;Hash函数h用来划分参与连接的两个关系;h的 输入是Join4mrs:输出{0,1,…,n},其中Joi4mrs表示参与连接关系的属性;rr,,rn表 示r元组的划分,i=h( JoinAttrs/),元组l∈r属于划分r;sbs,Sn表示s元组集 合的划分,i=h( s / JoinAttrs,元组l∈s属于划分s;在分组之上实现连接操作 连接操作的执行代价需要考虑内外存数据交换的次数。选择合适的连接算法需要考虑数 据的分布情况。 (2)XML数据解析的DOM解析 文档对象模型DOM( document object model)是由W3C制定的XML树状结构模型和标准 操作接口规范。DOM解析根据ⅹML文档的结构将其转换为树状结构的文档对象模型。用 户通过对该对象模型的访问,可以动态地创建文档,遍历文档结构,对ⅩML文档中的数据 进行修改、移动、删除和插入等操作。 DOM解析器提供了基于文档对象模型的AP来解析和操纵XML文档。它把ⅩML文档 内容看作树,而每个元素( Element)用结点表示,称为 DOM Node。程序可以从根结点开始以 一种导航的方式来访问文档的组成部分。 基于DOM解析的优点:支持通过DOM接口实现XML文档的数据和结构的更改;支 持在任何时候在树中做任意方向的导航;支持简单有效地实现XML查询。 基于DOM解析的缺点:由于DOM解析需要在内存中表示ⅩML文档中元素、文本 属性等,所以DOM解析的时间和空间代价昂贵 (3)XML数据解析的DOM解析 SAX是基于事件的XML文档顺序访问的一组AP接口。相对于DOM解析方式,SAX 是读取和操作XML数据的更快速、更轻量的方法。SAX的API基于事件处理程序的概念 构建,是由与语法分析实际相关联的用户指定函数构成。语法分析事件对应文档组成部分的 识别:例如,当找到一个元素的开始标签的时候产生一个事件,而当找到结束标签时又产生
（2） 各种连接算法的稳定性和时间复杂度 （3） DOM 树中递归执行 XPath 的算法 （4） SAX 解析模型中的 XPath 查询执行算法； 5．授课提示 开展研究型教学，挖掘知识背后的内容，通过提出问题、探讨方法、研究思想、比较性 能，培养学生的创新意识、创新能力。 下面是数据库应用的重点和难点内容的讲授注意事项。 （1）数据库的连接算法 数据库的连接算法是数据库运算过程中代价较高的操作。目前，已经提出了多种经典算 法。 块嵌套连接循环调入外关系中数据块，通过循环访问内关系中的每一数据块，判定连连 接条件成立，输出连接结果。 索引嵌套连适应等值连接或自然连接；索引嵌套连接需要在内关系的连接属性上存在索 引，或者动态为连接操作而构造一个索引；对外关系 r 的每个元组 tr , 利用索引查找内关系 s 的与 tr 满足连接条件的元组。 归并连接将两个关系在连接属性上排序，其连接步骤类似于排序-归并算法的归并阶段； 主要不同在于连接属性中重复值的处理；归并连接只能用于等值连接和自然连接; 每个块只 需要读一次。 哈希连接适合等值连接和自然连接；Hash 函数 h 用来划分参与连接的两个关系；h 的 输入是 JoinAttrs ,输出 {0, 1, ..., n}, 其中 JoinAttrs 表示参与连接关系的属性；r0, r1, . . ., rn 表 示 r 元组的划分，i = h(tr [JoinAttrs])，元组 tr r 属于划分 ri； s0, s1. . ., sn 表示 s 元组集 合的划分，i = h(ts [JoinAttrs])，元组 ts s 属于划分 si；在分组之上实现连接操作。 连接操作的执行代价需要考虑内外存数据交换的次数。选择合适的连接算法需要考虑数 据的分布情况。 (2) XML 数据解析的 DOM 解析 文档对象模型 DOM (document object model)是由 W3C 制定的 XML树状结构模型和标准 操作接口规范。DOM 解析根据 XML 文档的结构将其转换为树状结构的文档对象模型。用 户通过对该对象模型的访问，可以动态地创建文档，遍历文档结构，对 XML 文档中的数据 进行修改、移动、删除和插入等操作。 DOM 解析器提供了基于文档对象模型的 API 来解析和操纵 XML 文档。它把 XML 文档 内容看作树，而每个元素(Element)用结点表示，称为 DOM Node。程序可以从根结点开始以 一种导航的方式来访问文档的组成部分。 基于 DOM 解析的优点：支持通过 DOM 接口实现 XML 文档的数据和结构的更改；支 持在任何时候在树中做任意方向的导航；支持简单有效地实现 XML 查询。 基于 DOM 解析的缺点：由于 DOM 解析需要在内存中表示 XML 文档中元素、文本、 属性等，所以 DOM 解析的时间和空间代价昂贵。 (3) XML 数据解析的 DOM 解析 SAX 是基于事件的 XML 文档顺序访问的一组 API 接口。相对于 DOM 解析方式，SAX 是读取和操作 XML 数据的更快速、更轻量的方法。SAX 的 API 基于事件处理程序的概念 构建，是由与语法分析实际相关联的用户指定函数构成。语法分析事件对应文档组成部分的 识别：例如，当找到一个元素的开始标签的时候产生一个事件，而当找到结束标签时又产生
一个事件,对这些事件的响应由用户指定函数进行处理。一个文档的不同片段总是可以按照 从开始到结束的顺序找出。具体的事件有文档的开始和结束、元素的开始和结束、文本内容 的读取等。 例如,给定一个XML文档片断 Database Principle Ullman。SAX解析器处理文档的结果如下: Starte element(book)、 StartElement(tle)、Text( Database Principle")、 endElement(tle)、 StartElement( author)、 Text(Ullman), endElement(author), end Element(book) 基于SAX解析的优点:SAX解析的时间代价和空间代价较低,SAX解析支持高效的 XML顺序访问;SAX解析支持ⅹML文档的部分解析,可以提前终止解析过程。 基于SAⅩ解析的缺点:SAⅩ解析不能支持对ⅹML文档的随机访问;SAX解析不能支 持XML文档的修改;SAX解析实现ⅩML查询需要应用程序的支持。 (4) XPath査询 XPath是w3C所提出的一种路径查询语言( (path language),支持通过路径表达式来定位 XML文档的部分内容。 XPath中的路径表达式是一串通过”P隔开的定位步骤的序列。路径 表达式的查询结果是一个XML子树的集合。 XPath路径表达式是从一个XML结点(即当前的上下文结点)到另外一些结点的定位步骤 序列。每个定位步骤包含以下三个部分:轴描述、结点测试和谓词。 XPath路径表达式中的轴描述指从上下文结点在XML数据树中进行访问的方向,具体 包括 child(子结点)、 attribute(属性)、 descendant(子孙结点)、 descendant-or-self(自身或子孙 结点)、 parent(父结点)、 ancestor(祖先结点)、 ancestor-or-self(自身或祖先结点)、 following(下 文结点)、 preceding(前文结点)、 following- sibling(后一个同级结点)、 preceding- sibling(前一 个同级结点)、sef(自己)、 namespace(命名空间)。 XPath路径表达式中的结点测试检验满足轴描述的结点,如果该结点与限定的元素名称 或元素类型相匹配,则保留在结果集合中,否则该结点被丢弃 XPath路径表达式中的谓词筛选一个结点集以生成新的结点集。对于结点集中的每一个 结点,谓词表达式将此结点作为当前上下文结点进行求值。基于当前上下文结点,计算谓词 表达式中的值,并将结果转换为布尔值。如果结果为True,该上下文结点保留:否则被丢 弃 在DOM树中实现 XPath查询需要在树结构中根据 XPath的特性来递归执行。鼓励同学 实现XML的索引减少 XPath的搜索空间在SAX解析器中实现 XPath查询需要利用将XPat 转换为自动机,将 XPath的查询转换为SAX事件对自动机的驱动。 6.课后练习和实习 融合经典的理论教学内容与学科的前沿新技术和发展方向,设计验证型、探索型、综合 应用型的习题和上机题,通过数据库连接操作算法和ⅹML数据查询算法提高学生综合各种 数据结构来解决实际问题的能力,训练学生的创新思维能力训练、工程实践能力。 数据结构应用可以安排2道综合上机实习题。安排2次习题讲评。 总结 数据结构应用是《数据结构与算法》课程训练学生算法思想、创新思维能力、工程实践 能力的重要环节,同时,扩展数据结构应用领域的知识,使学生理解关系数据处理和ⅩML 数据处理的基本算法 参考文献:
一个事件，对这些事件的响应由用户指定函数进行处理。一个文档的不同片段总是可以按照 从开始到结束的顺序找出。具体的事件有文档的开始和结束、元素的开始和结束、文本内容 的读取等。 例如，给定一个 XML 文档片断 Database Principle Ullman 。SAX 解析器处理文档的结果如下：StarteElement(book)、 StartElement(title) 、 Text(“Database Principle”) 、 endElement(title) 、 StartElement(author) 、 Text(“Ullman”)、endElement(author)、endElement(book)。 基于 SAX 解析的优点：SAX 解析的时间代价和空间代价较低，SAX 解析支持高效的 XML 顺序访问；SAX 解析支持 XML 文档的部分解析，可以提前终止解析过程。 基于 SAX 解析的缺点：SAX 解析不能支持对 XML 文档的随机访问；SAX 解析不能支 持 XML 文档的修改；SAX 解析实现 XML 查询需要应用程序的支持。 （4）XPath 查询 XPath 是 W3C 所提出的一种路径查询语言(path language)，支持通过路径表达式来定位 XML 文档的部分内容。XPath 中的路径表达式是一串通过”/”隔开的定位步骤的序列。路径 表达式的查询结果是一个 XML 子树的集合。 XPath路径表达式是从一个XML结点(即当前的上下文结点)到另外一些结点的定位步骤 序列。每个定位步骤包含以下三个部分：轴描述、结点测试和谓词。 XPath 路径表达式中的轴描述指从上下文结点在 XML 数据树中进行访问的方向，具体 包括 child (子结点)、attribute (属性)、descendant(子孙结点)、descendant-or-self (自身或子孙 结点)、parent (父结点)、ancestor (祖先结点)、ancestor-or-self (自身或祖先结点)、following (下 文结点)、preceding (前文结点)、following-sibling (后一个同级结点)、preceding-sibling (前一 个同级结点)、self (自己)、namespace（命名空间）。 XPath 路径表达式中的结点测试检验满足轴描述的结点，如果该结点与限定的元素名称 或元素类型相匹配，则保留在结果集合中，否则该结点被丢弃。 XPath 路径表达式中的谓词筛选一个结点集以生成新的结点集。对于结点集中的每一个 结点，谓词表达式将此结点作为当前上下文结点进行求值。基于当前上下文结点，计算谓词 表达式中的值，并将结果转换为布尔值。如果结果为 True，该上下文结点保留；否则被丢 弃。 在 DOM 树中实现 XPath 查询需要在树结构中根据 XPath 的特性来递归执行。鼓励同学 实现 XML 的索引减少 XPath 的搜索空间。在 SAX 解析器中实现 XPath 查询需要利用将 XPat 转换为自动机，将 XPath 的查询转换为 SAX 事件对自动机的驱动。 6．课后练习和实习 融合经典的理论教学内容与学科的前沿新技术和发展方向，设计验证型、探索型、综合 应用型的习题和上机题，通过数据库连接操作算法和 XML 数据查询算法提高学生综合各种 数据结构来解决实际问题的能力，训练学生的创新思维能力训练、工程实践能力。 数据结构应用可以安排 2 道综合上机实习题。安排 2 次习题讲评。 7．总结 数据结构应用是《数据结构与算法》课程训练学生算法思想、创新思维能力、工程实践 能力的重要环节，同时，扩展数据结构应用领域的知识，使学生理解关系数据处理和 XML 数据处理的基本算法。 参考文献：
1.张铭,王腾蛟,赵海燕,《数据结构与算法》,高等教育出版社,2008年6月。—一普 通高等教育“十一五”国家级规划教材。 2.张铭、赵海燕、王腾蛟、宋国杰、高军,北京大学“数据结构与算法”教学设计,《计 算机教育》2008第20期。获得“英特尔杯2008年全国计算机教育优秀论文评比”一等 奖。 3.北京大学《数据结构与算法》精品课程网站(2008年北京市“精品课程”暨国家“精品 课程),http://www.jpk.pkuedu.cn/pkujpk/course/sjjg/ 4.蒋宗礼,“编译原理教学设计”。《计算机教育》,2008.3。 5.张铭、许卓群、杨冬青、唐世渭,“数据结构知识系统及教学实践”。《计算机教育》。《计 算机教育》,2004年2、3月合刊,PP89-91
1. 张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2008 年 6 月。——普 通高等教育“十一五”国家级规划教材。 2. 张铭、赵海燕、王腾蛟、宋国杰 、高军，北京大学“数据结构与算法”教学设计，《计 算机教育》2008 第 20 期。获得“英特尔杯 2008 年全国计算机教育优秀论文评比”一等 奖。 3. 北京大学《数据结构与算法》精品课程网站（2008 年北京市“精品课程”暨国家“精品 课程”）， http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 4. 蒋宗礼，“编译原理教学设计”。《计算机教育》, 2008.3。 5. 张铭、许卓群、杨冬青、唐世渭，“数据结构知识系统及教学实践”。《计算机教育》。《计 算机教育》，2004 年 2、3 月合刊，PP89-91
