SimpleDB：一个简单的基于java的教学数据库内的多用户系统外文翻译资料

SimpleDB: A Simple Java-Based Multiuser System for Teaching Database Internals

Edward Sciore Boston College Computer Science Dept Chestnut Hill, MA

617-552-3928

sciore@bc.edu

ABSTRACT

In this paper we examine the problem of how to give hands-on assignments in a database system internals course. We argue that current approaches are inadequate, either because they are not sufficiently comprehensive or because they require using software that has a steep learning curve. We then describe SimpleDB, which is software written expressly for such a course. SimpleDB is a database system in the spirit of Minibase. Unlike Minibase, however, it supports multiple users and transactions via JDBC, and its code is easy to read and modify. We then describe a course that we teach using SimpleDB, and discuss the educational benefits resulting from it.

Categories and Subject Descriptors

H.2.4 [Database Management]: Systems – relational databases, query processing.

General Terms

Algorithms, Design, Languages

Keywords

pedagogical database software, database internals, minibase

1. INTRODUCTION

The topics in an undergraduate introductory database course typically fit into two categories: how to use a database system, and how a database system works. Topics in the first category include database design, relational algebra, SQL, and how to build database applications. Topics in the second category include concurrency control, recovery, indexing, and query processing.

Historically, these topics were compressed into a single-semester course. More recently, many schools (including Boston College) have chosen to teach the material over two courses, with each course corresponding to one of the two categories. The first course becomes a user-oriented course, whereas the second course becomes a system-oriented course.

There are several advantages to this division. The first advantage is that it is possible to go much deeper into the various topics. The user-oriented course can cover advanced material such as web- based development and data mining. The system-oriented course can cover additional design alternatives, such as locking vs. multi- version concurrency, top-down vs. bottom-up query processing, additional forms of indexing, etc.

The second advantage to the split is that each course has different prerequisites and a different student population. The user-oriented course requires very little programming experience (if any), and is appropriate for students looking for a practical, applications- oriented course. For example at Boston College, this course is taught in the business school and is a requirement for their Information Systems concentration. Computer Science majors tend to find the course very easy, and it counts towards their major only as a low-level CS elective.

The system-oriented course, on the other hand, is a quintessential computer science course, on a par with the traditional upper-level CS courses. It touches on mainstream issues such as data structures (for indexing), external sorting, operating systems (file systems and memory management), distributed systems (client- server, threading, deadlock), language interpreters, and algorithm design. At Boston College this course has only Data Structures as a prerequisite, but an interesting alternative would be to teach it as a senior capstone course.

Another difference between the two courses is the kind of assignments given to students. The user-oriented course is very hands-on: Students learn to use a particular database system, and very often work on a major project in which they build a sophisticated application from scratch. The system-oriented course, on the other hand, tends to be theoretical: Students draw pictures of B-Trees, interpret log files by hand, prove serializability, and calculate optimal query plans.

A theoretically-based system course is ok, but I think most would agree that a hands-on course is better, at least for undergraduates. In my experience, undergraduate students have a relatively easy time solving problems in a narrow context, but have a very difficult time grasping how everything fits together. Ideally, a student would write an entire database system as part of his coursework, as one would write a compiler in a compiler course. However, database systems are much more complex than compilers, and so that approach is not practical. What should an instructor do?

Several strategies are possible:

bull; Have students write a “toy” database system from scratch.

bull; Provide students with the object code to an instructor-written database system, and have students rewrite specific modules according to a given API.

bull; Provide students with the source code to a pedagogically- written database system, and have students modify specific modules.

bull; Give students access to an open-source commercial database system, and let them add features to it.

Each of these approaches has drawbacks.

Writing a toy system gives students the experience of building a large system, but this system usually winds up being so simple that it has no correspondence to how a real database system is built.

On the other hand, writing individual modules to an otherwise- unknown system gives students the experience of writing actual code, but does not give them an overall understanding of the system and does not allow them to make improvements that encompass multiple modules.

The last two strategies allow students to see the entire source code of a system. Studying this source code can provide the sense of how things fit together, and modifying the code can reinforce this understanding. The difference between these two strategies is whether the code is specifically written for student us

剩余内容已隐藏，支付完成后下载完整资料

---

SimpleDB：一个简单的基于java的教学数据库内的多用户系统

Edward Sciore Boston College Computer Science Dept Chestnut Hill, MA

617-552-3928

sciore@bc.edu

摘要

在本文中，我们将探讨如何在数据库系统内部课程中提供手工作业的问题。我们认为，目前的方法是不够的，要么是因为它们不够全面，要么是因为它们需要使用陡峭的学习曲线的软件。然后我们描述SimpleDB，它是专门为这样的课程编写的软件。SimpleDB是一个基于最小数据库精神的数据库系统。但是，与MyBasic不同，它通过JDBC支持多个用户和事务，并且其代码易于读取和修改。然后，我们描述一个课程，我们介绍SimpleDB，并讨论其带来的教育效益。

类别和主题描述

H.2.4[数据库管理]：系统-关系数据库，查询处理。

一般术语

算法、设计、语言

关键字

教学数据库软件、数据库内部、小型数据库

1.介绍

本科介绍数据库课程的主题通常分为两类：如何使用数据库系统，以及数据库系统是如何工作的。第一类的主题包括数据库设计、关系代数、SQL以及如何构建数据库应用程序。第二类中的主题包括并发控制、恢复、索引和查询处理。

历史上，这些主题被压缩成一个学期的课程。最近，许多学校（包括波士顿学院）选择教两门课程的材料，每门课程都对应于这两类课程之一。第一门课程成为面向用户的课程，而第二门课程则成为面向系统的课程。

这种划分有几个优点。第一个优点是可以深入地了解各种主题。面向用户的课程可以涵盖诸如基于Web的开发和数据挖掘等高级材料。面向系统的课程可以覆盖额外的设计方案，如锁定与多版本并发、自上而下与自下而上的查询处理、附加的索引形式等。

分裂的第二个优势是每个课程有不同的先决条件和不同的学生群体。面向用户的课程需要非常少的编程经验（如果有的话），并且适合于寻找实用的、面向应用的课程的学生。例如，在波士顿学院，这门课程是在商学院授课的，是他们信息系统集中的要求。计算机科学专业的学生往往觉得这门课很容易，而且只作为低年级的CS选修课。

另一方面，面向系统的课程是一门典型的计算机科学课程，与传统的高级CS课程相媲美。它涉及主流问题，如数据结构（用于索引）、外部排序、操作系统（文件系统和内存管理）、分布式系统（客户端-服务器、线程、死锁）、语言解释器和算法设计。在波士顿学院，这门课程只有数据结构作为先决条件，但有趣的选择是教它作为一个高级顶点课程。

这两门课的另一个区别是给学生的作业种类。面向用户的课程是非常实用的：学生学习使用特定的数据库系统，并且经常工作在一个主要项目中，他们从零开始构建一个复杂的应用程序。另一方面，面向系统的课程往往是理论性的：学生绘制B-树的图片，手工解释日志文件，证明可串行化，并计算最优查询计划。

理论上的系统课程是可以的，但我认为大多数人会同意动手实践课程更好，至少对于本科生来说。在我的经验中，本科生在一个狭隘的环境中有相对容易的时间解决问题，但是很难掌握所有事情是如何结合在一起的。理想情况下，学生将编写整个数据库系统作为课程作业的一部分，因为在编译器课程中编写编译器。然而，数据库系统比编译器复杂得多，因此这种方法是不实用的。教师应该做什么？

有几种可能的策略：

让学生从头开始写一个”小型”数据库系统。

为学生提供目标代码到教师编写的数据库系统，并让学生根据给定的API重写特定的模块。

为学生提供源代码到一个教学的书面数据库系统，并让学生修改特定的模块。

让学生访问一个开源的商业数据库系统，并让他们添加特性。

这些方法中的每一个都有缺点。

编写一个玩具系统给学生构建一个大系统的经验，但是这个系统通常会变得如此简单以至于它与真实的数据库系统是如何建立的没有对应关系。

另一方面，将单个模块写入另一个未知系统给学生编写实际代码的经验，但不给他们对系统的全面理解，不允许他们进行包含多个模块的改进。

最后两种策略允许学生查看系统的全部源代码。研究这个源代码可以提供事物如何组合的感觉，并且修改代码可以增强这种理解。这两种策略的区别在于代码是专门为学生使用的，还是它是商业级的。

商业开源软件具有“真实”代码的威望，但庞大、复杂、功能齐全。它不仅会有一个陡峭的学习曲线，而且很难修改，因为所有简单的改进都已经完成了。Ailamaki和Helel斯坦[1]描述了一个使用PostgreSQL来实现这一目的的课程。他们的学生能够成功地修改系统，但在学期中只有两个系统分配是可能的（一个修改缓冲管理器，一个添加了额外的查询运算符）。

一个教学系统有一个奢侈品，它可以包括任何看似合理的特征，并省略其余部分。它可以用一个眼睛来写，它是一个可读的基本概念的呈现，而不是仅仅是高效的。然而，它运行的风险过于简单，因此无关。

最广泛的教学系统是Minibase[2，第30章]。Minibase尝试具有商业数据库系统的结构和功能，但易于理解和扩展。通过平衡双方的担忧，这两个问题都不太好。（这一评估在1）中得到了回应，它具有很高的学习曲线，但没有开源系统的优点。它没有多用户或事务处理能力。建议的项目类似于[1]，显然没有简单。

文献中提到的另一个教学系统是MySQL[3]。该系统设计为重量级架构，但重量轻的代码。也就是说，系统的组成部分和它们的功能与商业系统基本相同，但是实际代码只实现了它所能实现的一小部分。例如，系统不是实现所有的SQL，而是实现足够的允许非平凡查询。

MySQL这样的系统的优点在于它简化了学习曲线——学生不会被无关的特征及其随之而来的编程细节所淹没。不幸的是，MinSQL从来没有公开过，所以不可能围绕它建立一个课程。

我开发了SimpleDB数据库系统，独立于MySQL，但出于同样的原因。SimpleDB的主要目标是可读性、可用性和易修改性。与MinSQL一样，它具有商业数据库系统的基本架构，但剥离了所有不必要的功能，只使用最简单的算法。该系统是用java写的，充分利用java库。例如，它使用java RMI处理客户端服务器的问题，和java虚拟机来处理线程调度。

在我的数据库系统内部课程中，我已经使用SimpleDB（某种程度上）了三多年。本文介绍了SimuleDB及其体系结构，以及在该课程中的应用经验。

2.SimpleDB系统

SimpleDB代码分为三个部分：

（1）包含JDBC接口并实现JDBC驱动程序的客户端代码。

（2）基本的服务器，它提供了完整的（虽然是裸露的）功能，但是忽略了效率问题。

（3）对支持高效查询处理的基本服务器的扩展。

下面的小节地址每个部分。

2.1客户端代码

一个SimpleDB客户端是与服务器进行通信的java程序通过JDBC。例如，图1的代码片段打印销售部门中每个雇员的工资。

Figure 1: Printing the salary of everyone in the sales dept

JDBC包java.sql定义接口驱动程序、连接、语句和结果集。数据库系统负责提供实现这些接口的类；在SimpleDB中，这些类被命名为SimpleDriver、SimpleConnection等。客户端只需要知道SimpleDriver，但所有类都需要提供给它。在大多数商业系统中，这些类打包在一个JAR文件中，该文件被添加到客户端的类路径中。SimpleDB不附带客户端JAR文件，但对于学生来说，这是一个简单的（有用的）练习。

标准的JDBC接口具有大量的方法，其中大部分是对数据库内部构件的理解的外围设备。因此，SimpleDB有自己的这些接口的版本，其中包含了方法的一小部分。优点是SimpleDB代码可以更小和更集中，并且如果需要的话，省略的方法可以被实现为类练习。

2.2基本服务器

基本服务器包括SimpleDB代码的大部分。它由十个分层组件组成，其中每个组件使用它下面的组件的服务并为其上面的组件提供服务。这些组件显示在图2中。本节的其余部分从底部向上简要讨论了这些组件。

Figure 2: The components of the basic SimpleDB server

文件管理器支持对SimpleDB使用的各种数据文件的访问：每个表的文件、索引文件、一些目录文件和日志文件。文件管理器API包含用于随机访问块的读取和写入的方法。更高级别的组件将数据库视为磁盘上块的集合，其中块包含固定数量的字节。

日志管理器负责维护日志文件。它的API包含将日志记录写入文件并通过日志文件中的记录进行迭代的方法。

缓冲区管理器负责页面的内存存储，其中页面保存块的内容。它的API包含将缓冲区插入到块中、将缓冲区刷新到磁盘、以及在块内的任意位置获取/设置值的方法。更高级别的组件将数据库视为内存中的值页集合。

事务管理器是缓冲管理器周围的包装器。它具有与缓冲区管理器基本相同的API，有一些额外的提交和回滚事务的方法。事务管理器的任务是拦截对缓冲区管理器的调用，以便处理并发控制和恢复。它将块视为锁粒度的单位，每当调用（或设置）值的方法被调用时，就在适当的块上获得SLOK（或XLoK）。事务管理器还通过使用值的提前写入日志来支持恢复；当调用设置值的方法时，事务管理器将旧值写入日志中，然后告诉缓冲区管理器将新值写入页面。更高级别的组件仍然将数据库看作是值页的集合，但使用确保安全性和可串行化性的方法。

记录管理器负责将块格式化成固定长度的未跨越记录。它的API包含迭代文件中所有记录的方法。记录管理器隐藏数据库的块结构。更高级别的组件将数据库视为文件的集合，每个文件都包含一个记录序列。

元数据管理器将目录信息存储在目录文件中。它的API包含创建给定模式的新表的方法，以及检索现有表的架构。元数据管理器隐藏数据库的物理特性。更高级别的组件将数据库视为表和索引的集合，每个表包含一系列记录。

查询处理器实现查询树，这些查询树可以由关系代数运算符选择、项目和产品组成。它的API包含创建查询树并迭代它的方法。

解析器利用递归下降识别SQL的已拆分子集。该语言对应于具有非常简单谓词的选择项目连接查询。除了“和”之外，没有布尔运算符，除了“=”之外没有比较，没有算术或内置函数，没有分组，没有重命名，等等。

规划人员根据查询的解析表达式构建查询计划。该计划是最简单的：它采用所提到的表的产品（按所提到的顺序），接着是使用WHERE子句谓词的选择操作，随后是输出字段上的投影。

最后，远程接口实现JDBC API的一小部分。关键方法是Statement.executeQuery，它调用解析器和规划器来构造查询树，并将其传递给ResultSet对象进行遍历。所有的网络通信是照顾的java RMI。

三.结论

SimpleDB数据库服务器是为了帮助学生在数据库系统内部课程而编写的。它有两个目的：

(1)给学生一个易于理解的真实数据库系统的例子；

(2)给学生一个做有意义的手工编程任务的工具。

我的经验是，系统已经很好地达到了这些目的。该系统在与数据库系统研究无关的方面也变得有价值。它让学生们体验一个大系统，既要理解它，又要修改它。它为学生在其他课程中遇到的大量理论概念提供了一个实用的“顶点”示例。

基本SimpleDB服务器由3500行左右的java代码（不包括Javadoc注释），和效率的扩展是大约一半大小。

四.参考文献

1. Ailamaki, A., and Hellerstein, J. Exposing Undergraduate Students to Database System Internals. ACM SIGMOD Record, 32, 3 (September 2003), 18-20.
2. Ramakrishnan, R. and Gehrke, J. Database Management Systems (Third Edition). McGraw-Hill, Boston, 2003.
3. Swart, G. MinSQL: A Simple Componentized Database for the Classroom. In Proceedings of the 2^nd international conference on Principles and Practice of Programming in Java (Kilkenny City, Ireland, June 16-18, 2003). ACM International Conference Proceeding Series Vol. 42, 2003, 129-132.

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[22869]，资料为PDF文档或Word文档，PDF文档可免费转换为Word