MyOOPS開放式課程
請加入會員以使用更多個人化功能
來自全球頂尖大學的開放式課程,現在由世界各國的數千名義工志工為您翻譯成中文。請免費享用!
課程來源:MIT
     
翻譯:彭法鑾

編輯:劉夏泱 陳盈

Inside of a hard drive.
硬碟的內部構造。(圖片承蒙Brandon Blinkenberg和stock.xchng提供)
Inside of a hard drive. (Image courtesy of Brandon Blinkenberg and stock.xchng.)

課程重點

本課程的重點在於一組在作業部分提供之可下載的整套問題集和答案。另外,在相關閱讀資料部分,我們提供了一份推薦與指定的閱讀參考書單。

This course features a complete set of downloadable problem sets and solutions in the assignments section. In addition, an extensive bibliography of assigned and recommended readings is provided in the readings section.

課程描述

本 課程的目的是向研究生介紹資料庫的基礎知識。課程內容關注於其基本知識,如關係代數和資料模型、查詢優化、查詢處理和事務。本課程並不關注於資料庫設計和 SQL語言編程(雖然我們會簡要討論一下這方面的知識)。它是為那些已經學習了6.033課程(或等同課程)的學生而開設的,我們假定學生對資料庫並無預 先的知識,但是在大學部學習了資料庫課程的學生也是歡迎修習的。

This course is designed to introduce graduate students to the foundations of database systems, focusing on basics such as the relational algebra and data model, query optimization, query processing, and transactions. This is not a course on database design or SQL programming (though we will discuss these issues briefly). It is designed for students who have taken 6.033 (or equivalent); no prior database experience is assumed though students who have taken an undergraduate course in databases are encouraged to attend.
師資
講師:
Samuel Madden 教授
上課時數
教師授課:
每週2節
每節1.5小時
程度
研究所
回應
告訴我們您對本課程或「開放式課程網頁」的建議。
聲明
麻省理工學院開放式課程認可 開放式課程計畫(OOPS)的翻譯計畫,開放式課程計畫(OOPS)乃是運用其獨立團隊、獨立資源、獨立流程進行翻譯計畫之團隊。

所有麻省理工學院開放式課程之材料皆以麻省理工學院開放式課程創作共享授權發佈,所有之翻譯資料皆由開放式課程計畫(OOPS)所提供,並由其負翻譯品質之責任。

此 處麻省理工學院開放式課程之資料乃由 開放式課程計畫(OOPS) 譯為正體中文。麻省理工學院開放式課程在此聲明,不論是否遭遇或發現相關議題,麻省理工學院開放式課程、麻省理工學院教師、麻省理工學院校方並不對翻譯正 確度及完整性作保證。上述單位並對翻譯後之資料不作明示或默許對任一特定目的之適合性之保證、非侵權之保證、或永不出錯之保證。麻省理工學院校方、麻省理 工學院開放式課程對翻譯上之不正確不負任何責任。由翻譯所引發任何關於此等資料之不正確或其他瑕疵,皆由開放式課程計畫(OOPS)負全責,而非麻省理工 學院開放式課程之責。

原文聲明

 


概述

本課程的目的是向研究生介紹資料庫的基礎知識。課程內容關注於其基本知識,如關係代數和資料模型、 查詢優化、查詢處理和事務。本課程並不關注於資料庫設計和SQL語言編程(雖然我們會簡要討論一下這方面的知識)。它是為那些已經學習了6.033課程 (或等同課程)的學生而開設的,我們假定學生對資料庫並無預先的知識,但是在大學部學習了資料庫課程的學生也是歡迎修習的。

課程將包括講稿和對資料庫文獻學習的討論。這將是一個長達一學期的課程,包括兩次考試和一些(2到3次)的作業。

註冊本課程的人數將有所限制。

主題包括

主題主要相關於資料庫系統工程和設計,包括:資料模型、資料和模式設計、模式規範化和完整性約束、 查詢處理、查詢優化和成本估計、事務、恢復、併發控制、獨立性和一致性;分散式、並行或異構資料庫;自適應資料庫;觸發器系統;發佈子系統;半結構化資料 和XML查詢。講稿和讀物來自原始的研究論文。有長達一學期的專題和論文。

先修課程

學生必須先修習6.033或等同的課程。不需要有資料庫的預先知識。

單元

3-0-9,6.893是個Grad-H 的課程,被認定為系統課程中的工程核心課程。

評分

分數評定是由兩次作業、兩次測試、一個期末項目和課堂參與表現組成。評分比例如下所示:

分數 百分比
作業 20%
測試(每次10%) 20%
期末項目 45%
課堂參與 15%


不接收遲交的作業。

合作策略

你可以和其他同學討論和交流課後作業,但是一定要寫出你自己的答案,並且列出合作者的名單。抄襲別人的答案是絕對不允許的。對於組專題作業,必須組隊完成,並且全組只要交一份的報告即可。

教材

課程的教材主要是《資料庫系統閱讀資料》第四版,由Stonebraker和Hellerstein編著。本書的第三版《資料庫系統閱讀資料》與第四版完全不同(二者不包括相同的閱讀資料)。我們將在伺服器上貼出更多的其他閱讀材料。

補充閱讀

Ramakrishnan和Gehrke的 《資料庫管理系統》是一本對資料庫系統的基礎介紹和擴充內容的一個良好選擇。

6.033是先修的課程。你可能需要複習6.033的第8章,特別在我們討論事務和日誌期間。

Overview

This course is designed to introduce graduate students to the foundations of database systems, focusing on basics such as the relational algebra and data model, query optimization, query processing, and transactions. This is not a course on database design or SQL programming (though we will discuss these issues briefly). It is designed for students who have taken 6.033 (or equivalent); no prior database experience is assumed though students who have taken an undergraduate course in databases are encouraged to attend.

Classes will consist of lectures and discussions based on readings from the database literature. There will be a semester long project, as well as two exams and a few (2 or 3) problem sets.

Enrollment may be limited.

Topics Covered

Topics related to the engineering and design of database systems, including: data models; database and schema design; schema normalization and integrity constraints; query processing; query optimization and cost estimation; transactions; recovery; concurrency control; isolation and consistency; distributed, parallel, and heterogeneous databases; adaptive databases; trigger systems; pub-sub systems; semi-structured data and XML querying. Lecture and readings from original research papers. Semester-long project and paper.

Prerequisites

Students should have taken 6.033 or equivalent. Prior database experience is not required.

Units

3-0-9. 6.893 is a Grad-H class. It counts as an engineering concentration (EC) subject in Systems.

Grading

Grades are assigned based on 3 problem sets, 2 quizzes, a final project, and class participation. The grading breakdown is as follows:

activities percentageS
Problem Sets 20%
Exams (10% each) 20%
Final Project 45%
Class Participation 15%


Late assignments will not be accepted.

Collaboration Policy

For problem sets, you are allowed to discuss your answers with other students, but please write up your own answers and list your collaborators. Copying solutions from other students is never allowed. For the group project you will work in teams and hand in only one written report.

Text

The course readings will primarily be drawn from the 4th edition of Readings in Database Systems, edited by Stonebraker and Hellerstein. The third edition of Readings in Database Systems is a substantially different text (it does not include the same readings.) There will be several other readings that will be posted on the server.

Supplemental Readings

For an excellent introduction to the basics of database systems, including extensive coverage of, the textbook Database Management Systems from Ramakrishnan and Gehrke is excellent.

6.033 is a prerequisite. You may wish to review 6.033 Chapter 8, especially during our discussion of transactions and logging.


 

 
Calendar 課 課程單元 關鍵日期
基本原理
Fundamentals
1 介紹
Introduction
指派作業1
Problem set 1 out
2 關係模型和SQL語句
The Relational Model and SQL
 
3 邏輯設計和物理資料庫基礎
Logical Design and Physical Database Fundamentals
交作業1
Problem set 1 due
4 現代關聯資料庫系統介紹
Introduction to Modern Relational Database Systems
指派作業2
Problem set 2 out
查詢處理
Query Processing
5 優化的基本原理
Optimization Fundamentals
 
6 連接演算法和記憶體管理
Join Algorithms and Memory Management
 
7 索引
Indexing
 
8 分散式資料庫
Distributed Databases
繳交作業2
Problem set 2 due
9 資料倉庫
Data Warehouses
繳交專題大綱
Project proposals due
10 可擴展和面向物件的資料庫
Extensibility and Object Databases
指派作業3
Problem set 3 out
事務
Transactions
11 事務介紹
Introduction to Transactions
 
12 事務第二部分
Transactions Part 2
 
13 鎖機制和一致性
Locking and Consistency
 
14 併發控制的優化
Optimistic Concurrency Control
繳交作業3
Problem set 3 due
  考試1
Exam 1
 
15 分散式事務和複製
Distributed Transactions and Replication
 
網路化資料管理
Networked Data Management
16 Web服務
Web Services
 
17 半結構化資料
Semistructured Data
 
18 連續查詢
Continuous Queries
 
19 自適應性查詢處理
Adaptive Query Processing
 
20 流資料庫
Stream Databases
 
高級主題
Advanced Topics
21 資料挖掘和序列化查詢
Data Mining and Sequence Queries
 
22 模糊查詢
Approximate Querying
 
  考試2
Exam 2
 
23 資料流程的連貫性和可用性
Consistency and Availability in Data Streams
 
24 課程的最後一天總結
Last day of Class Presentations
繳交專題報告
Project Reports due

 

大多數閱讀材料來自「紅書」――《資料系統的閱讀材料》, 第四版,由Michael Stonebraker和Joseph Hellerstein編著,劍橋:麻省理工學院出版社,2005年1月,ISBN: 0262693143。 這本書可以從麻省理工學院出版社買到。請注意第四版和第三版是完全不同的,第四版包括很多新的材料和文章,這些文章其他地方是看不到的。

Most readings are from the "Red Book", otherwise known as Readings in Database Systems, 4th edition, edited by Michael Stonebraker and Joseph Hellerstein, Cambridge: MIT Press, January 2005, ISBN: 0262693143. This book is available from the MIT Press. Note that this version of the book is substantially different than the 3rd edition and includes a number of new readings (and articles that are not otherwise available).

課程閱讀材料 課 課程單元 閱讀問題 閱讀資料
基本原理
Fundamentals
1 介紹
Introduction
   
2 關係模型和SQL語句
The Relational Model and SQL
  Stonebraker, Michael和 Joseph Hellerstein.〈種什麼因,得什麼果〉,《紅書》 第一堂課將會給大家一份影本,請預習1-4節、第9、10、11節。
Stonebraker, Michael, and Joseph Hellerstein. "What Goes Around Comes Around." In Red Book.
Copies will be made available on the first day of class. Read Sections 1-4, 9, 10, and 11.

Codd, E. F.〈大型共用資料庫資料的關係模型〉,《美國電腦學會通訊》 (1970年). 著重點在於1.3節和第2節。
Codd, E. F. "A relational model of data for large shared data banks." Communications of the ACM (1970).
Focus on Sections 1.3 and all of Section 2.
3 邏輯設計和物理資料庫基礎
Logical Design and Physical Database Fundamentals
  實體關係模型(E-R模型) -- 一個統一的資料的視圖。
The Entity-Relationship Model -- toward a unified view of data.
我們不會在課堂上討論這篇論文 --我們談到這些是因為E-R模型是資料庫設計中廣泛使用的技術,它可能是一個有用的個人參考。
We will not discuss this paper in class -- I have included it because ER modeling is a technique that is widely used in database design that may be useful as a personal reference.

Hillyer和Mike的《資料庫規範化導論》。 注意這是對資料庫規範化的一個非常不正式的討論,並且也沒有在深度上涵蓋所有的主題。但它能為我們在課堂上,討論各種類型的資料庫規範化提供參考。
Hillyer, Mike. An Introduction to Database Normalization.
Note that this is an extremely informal discussion of the topic of database normalization, and does not cover all of the issues in depth. It is useful as a reference to the different types of normalization we discussed in class.

Vitter, J. 〈外部存儲演算法和資料結構:海量資料的處理〉,《美國電腦學會計算概觀》 33卷,第2期(2001年):第209-271頁。 閱讀章節:第1-3,5,9和10章。 我們將會在課程後半段裏複習R-Trees(第11章)。
Vitter, J. "External Memory Algorithms and Data Structures: Dealing with massive data." ACM Computing Surveys 33, no. 2 (2001): 209-271.
Read sections 1-3, 5, 9, and 10 -- we will revisit R-Trees (Section 11) later in the course.
4 現代關聯資料庫系統介紹
Introduction to Modern Relational Database Systems
  Hellerstein, Joseph, 和Michael Stonebraker.〈資料庫剖析〉,《紅書》 閱讀章節:第1-4章。當討論併發控制和恢復時我們將會返回到第5章
Hellerstein, Joseph, and Michael Stonebraker. "The Anatomy of a Database." In Red Book.
Read Sections 1-4; we will return to Section 5 when we discuss concurrency control and recovery.

Astrahan, M. M.等〈R系統:資料庫管理的關聯方法〉,《美國電腦學會--資料庫系統事務》ACM TODS (ACM Transactions on Database Systems) 1卷, 第2期 (1976年): 第97-137頁。
Astrahan, M. M., et. al. "System R: Relational Approach to Database Management." ACM TODS 1, no. 2 (1976): 97-137.
查詢處理
Query Processing
5 優化的基本原理
Optimization Fundamentals
  Selinger, Patricia, M. Astrahan, D. Chamberlin, Raymond Lorie, 和 T. Price.〈關聯資料庫管理系統中的存取路徑控制〉,《紅書》,美國電腦學會--資料管理特別興趣組學報(ACM SIGMOD). 1979年,第22-34頁. 下堂課我們會討論這篇論文的絕大部分,請把全文認真看完,特別注意基於最優化演算法的成本估算方法和動態編程。
Selinger, Patricia, M. Astrahan, D. Chamberlin, Raymond Lorie, and T. Price. "Access Path Selection in a Relational Database Management System." In Red Book. Proceedings of ACM SIGMOD. 1979, pp. 22-34.
We will discuss most of this paper next time in class -- read the whole thing, paying careful attention to the cost estimation methods and dynamic programming based optimization algorithm.

Mannino, Michael, Paichen Chu和Thomas Sager〈資料庫系統中的統計檔估算〉,《美國電腦學會計算概觀》,20卷, 第3期 (1988年): 第191-221頁。 這篇論文是可選讀的--它討論了很多在現代資料庫系統中,使用的查詢優化技巧和可操作的成本預算的方法。我們將在更高級的課程中討論這些構想。
Mannino, Michael, Paichen Chu, and Thomas Sager. "Statistical Profile Estimation in Database Systems." ACM Computing Surveys 20, no. 3 (1988): 191-221.
This paper is optional -- it discusses many of the techniques that are used to make query optimization and cost estimation practical in modern database systems. Will cover some of the ideas at a high level in class.
6 連接演算法和記憶體管理
Join Algorithms and Memory Management
  Shapiro, L. D.〈帶有大記憶體的資料庫系統的連接操作處理〉,《紅書》 這篇論文對連接計算的各種方法進行了徹底的討論,包括利用哈希演算法和btree指數的方法。我們將在課堂上討論各種連接操作演算法的利弊得失,所以大家認真考慮一下每種演算法的利弊。
Shapiro, L. D. "Join Processing in Database Systems with Large Main Memories." In Red Book.
This paper presents a thorough discussion of different strategies for computing a join, including methods that take advantage of hash and btree indices. We will discuss the tradeoffs between join strategies in class, so think carefully about the pros and cons of each approach.

Sacco, G. M,.和 M. Schkolnick.〈關聯資料庫系統中的緩衝管理〉,《美國電腦學會--資料庫系統學報》11卷,第4期 (1986年): 473-489頁。 我們不會在課堂上仔細討論這篇文章,所以大家不需要從頭到尾讀它,但是大家必須熟悉一下基於緩衝管理的hot-set背後的基本思想。為滿足特別的好奇 心,在這個領域的經典文章是Chou和Dewitt在1978年寫的,叫作〈對於關聯資料庫系統的緩衝管理的評估〉。它提出了一個hot-set模型和一 個名叫DBMIN的緩衝管理評估策略,這和〈關聯資料庫系統中的緩衝管理〉這篇文章中的策略很相似。(據我所知,美國電腦學會並沒有DBMIN論文的數位 格式,它可以在網上的其他地方找到)。
Sacco, G. M., and M. Schkolnick. "Buffer Management in Relational Database Systems." TODS 11, no. 4 (1986): 473-489.
We will not discuss this paper in detail in class and you do not need to read it front-to-back, but you should be familiar with the basic idea behind hot-set based buffer management. For the extra-curious, the classic paper in this area is from Chou and Dewitt in 1978, called "An Evaluation of Buffer Management Strategies for Relational Database Systems" -- it proposes a hot-set model and a evaluates a buffer management strategy called DBMIN that is similar to the strategy proposed in this paper (as far as I can tell, the DBMIN paper is not available in digital format from ACM -- it can be found elsewhere on the Web.)
7 索引
Indexing
閱讀問題 (PDF)
Reading Questions 7 (PDF)
Hellerstein, Joseph M., Jeffrey F. Naughton和Avi Pfeffer.〈資料庫系統中的一般化查詢樹〉,《紅書》,超大規模資料庫(VLDB;Very Large DataBase)). 1995年。 我們需要理解GiST(通用搜索樹,一種資料和查詢謂詞均可擴展的索引方式)的基本抽象,而不要將重點放在文中討論的各種類型樹的細節。
Hellerstein, Joseph M., Jeffrey F. Naughton, and Avi Pfeffer. "Generalized Search Trees for Database Systems." In Red Book. VLDB. 1995.
Rather than focusing on the details of the different tree types discussed in this paper, try to understand the basic GiST abstraction.

Beckman, Norbert, Hans-Peter Kriegel, Ralf Schneider和 Bernhard Seeger.〈R*樹:對於點和長方形的高效和穩固的存取方法〉,《紅書》,SIGMOD 資料管理特別興趣組,1990年。 R樹或R*樹是B樹的一種重要的一般化。大家一定要理解他們分別適合於哪種類型的查詢,並且理解他們的屬性是怎麼有別於B樹。
Beckman, Norbert, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger. "The R*-tree: An efficient and robust access method for points and rectangles." In Red Book. SIGMOD. 1990.
R/R* trees are an important generalization of B-trees. Make sure you understand what types of queries they are useful for, and how their properties differ from those of B-trees.
8 分散式資料庫
Distributed Databases
閱讀問題 (PDF)
Reading Questions 8 (PDF)
Dewitt, David和Jim Gray.〈並行資料庫系統:高性能資料庫處理的趨勢》,《紅書》,美國電腦學會通訊,1992年. 這是對並行資料庫系統以及對設計它們的事務的一個良好的綜合介紹。
Dewitt, David, and Jim Gray. "Parallel Database Systems: The Future of High Performance Database Processing." In Red Book. Communications of the ACM. 1992.
This is a good general introduction to parallel database systems and the issues involved in their design.

Mackert, Lothar F.和Guy M. Lohman.〈R*最優化驗證和分佈查詢的性能評估〉,《紅書》,超大規模資料庫(VLDB;Very Large DataBase).1986年。
Mackert, Lothar F., and Guy M. Lohman. "R* Optimizer Validation and Performance Evaluation for Distributed Queries." In Red Book. VLDB. 1986。
9 資料倉庫
Data Warehouses
閱讀問題(PDF)
Reading Questions 9 (PDF)
Chaudhuri, Surajit和Umeshwar Dayal.〈資料倉庫和聯機分析處理技術概述(OLAP OnLine Analytical Processing)〉,《紅書》,SIGMOD 資料管理特別興趣組報告,26卷,第1期,1997年。
Chaudhuri, Surajit, and Umeshwar Dayal. "An overview of data warehousing and OLAP technology." In Red Book. SIGMOD Record. Vol. 26, no. 1, 1997.

Gray, Jim, Surajit Chaudhuri, Adam Bosworth, Andrew Layman, Don Reichart和Murali Venkatrao.〈DataCube:對排序、交叉表和Sub-Totals進行歸納的一種相關集合操作〉,《紅書》,資料挖掘和知識發現,1997 年。
Gray, Jim, Surajit Chaudhuri, Adam Bosworth, Andrew Layman, Don Reichart, and Murali Venkatrao. "DataCube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals." In Red Book. Data Mining and Knowledge Discovery. 1997.

O'Neil, Patrick和Dallan Quass.〈使用變化指數改進的查詢性能〉,《紅書》,美國電腦學會--資料管理特別興趣組學報,1997年。 此篇文章是可選讀的,但是它值得一讀,至少要大致瞭解資料倉庫中經常使用之不平常的指數類型。這篇文章簡要的介紹了這種類型的指數。
O'Neil, Patrick, and Dallan Quass. "Improved Query Performance with Variant Indices." In Red Book. ACM SIGMOD. 1997.
This paper is optional, but it's worth reading to at least get a sense of the unusual types of indices that are often used in warehouses. The overview paper mentions this type of index briefly.
10 可擴展和面向物件的資料庫
Extensibility and Object Databases
閱讀問題(PDF)
Reading Questions 10 (PDF)
Stonebraker, Michael.〈關聯資料庫系統中包含的新類型〉,《紅書》,國際遠端教育理事會學報(InternationaI Council for Distance Education 簡稱ICDE),1986年。
Stonebraker, Michael. "Inclusion of New Types in Relational Database Systems." In Red Book. Proceedings of ICDE. 1986.

Lamb, Charles, Gordon Landis, Jack Orenstein和Dan Weinreb.〈物件存儲的資料庫系統〉,《美國電腦學會通訊》 34卷,第10期,1991年。
Lamb, Charles, Gordon Landis, Jack Orenstein, and Dan Weinreb. "The ObjectStore Database System." Communications of the ACM 34, no. 10, 1991.
Transactions
11 事務介紹
Introduction to Transactions
  Franklin, Michael.〈併發控制與恢復〉,《電腦科學與工程手冊》,A. Tucker編輯,CRC出版社,Boca Raton, 1997年。(PDF)
Franklin, Michael. "Concurrency Control and Recovery." In The Handbook of Computer Science and Engineering. Edited by A. Tucker. CRC Press, Boca Raton, 1997. (PDF)

複習 6.033 第8章.
Review 6.033 Chapter 8.

此篇文章沒有閱讀問題,它是篇很容易理解的概述性文章。
There are no reading questions for this paper -- it's a fairly accessible overview, which you should read and understand.
12 事務第2部分
Transactions Part 2
閱讀問題 (PDF)
Reading Questions 12 (PDF)
Haerder, Theo和Andreas Reuter.〈面向物件資料庫恢復事務原理〉,《美國電腦學會計算概觀》15卷,第4期,1983年。
Haerder, Theo, and Andreas Reuter. "Principles of Transaction Oriented Database Recovery." ACM Computing Surverys 15, no. 4, 1983.
13 鎖機制和一致性
Locking and Consistency
閱讀問題(PDF)
Reading Questions 13 (PDF)
Gray, Jim等〈共用資料庫中鎖粒度和一致性〉,《 紅書》,資料庫管理系統中的模型化,G. M. Nijssen編輯,1976年。
Gray, Jim, et. al. "Granularity of Locking and Degrees of Consistency in a Shared Data Base" In Red Book. Modeling in Data Base Management Systems. Edited by G. M. Nijssen. 1976.
14 併發控制的優化
Optimistic Concurrency Control
閱讀問題(PDF)
Reading Questions 14 (PDF)
Kung, H. T.和John T. Robinson.〈併發控制的最優化方法〉,《紅書》,資料庫系統事務,(簡稱TODS Transactions on Database Systems),1981年6月。
Kung, H. T., and John T. Robinson. "On Optimistic Methods for Concurrency Control." In Red Book. TODS. June 1981.

Agrawal, Rakesh, Mike Carey和Miron Livny.〈併發控制性能模型:選擇與暗示〉,《紅書》,美國電腦學會--資料庫系統事務(簡稱TODS Transactions on Database Systems),12卷,第4期,1987年。 (請注意紅書中的此篇文章並不包括613頁到622頁。這是刻意的,你也不能要去看這個部分,即使你能從其他途徑獲得這幾頁的內容)。你可以不讀第6部 分。
Agrawal, Rakesh, Mike Carey, and Miron Livny. "Concurrency Control Performance Modeling: Alternatives and Implications." In Red Book. ACM Transactions On Database Systems. Vol. 12, no. 4, 1987.
(Note that the paper that appears in the Red Book does not contain pages 613-622 -- this is intentional and you shouldn't read them if you get the paper from elsewhere.) You also do not need to read Section 6.
  考試1
Exam 1
   
15 分散式事務和複製
Distributed Transactions and Replication
閱讀問題 (PDF)
Reading Questions 15 (PDF)
Mohan, C., Bruce Lindsay和R. Obermarck.〈R分散式資料庫管理系統中的事務管理〉,《紅書》,美國電腦學會--資料庫系統事務(簡稱TODS Transactions on Database Systems) 11卷,第4期,1986年。
Mohan, C., Bruce Lindsay, and R. Obermarck. "Transaction Management in the R* Distributed Database Management Systems." In Red Book. ACM Transactions On Database Systems. Vol. 11, no. 4, 1986.

Gray, Jim等.〈複製可能的危害和解決方案〉,《紅書》,美國電腦學會--資料管理特別興趣組(ACM Special Interest Group on Management of Data),1996年。
Gray, Jim, et. al. "The Dangers of Replication and a Solution." In Red Book. ACM SIGMOD. 1996.
網路化資料管理
Networked Data Management
16 Web服務
Web Services
閱讀問題 (PDF)
Reading Questions 16 (PDF)
Brewer, Eric.〈合併系統和資料庫:一個搜索引擎的回顧〉,《紅書》。
Brewer, Eric. "Combining Systems and Databases: A Search Engine Retrospective." In Red Book.

Jacobs, Dean〈應用伺服器中的資料管理〉,《紅書》。 Jacobs, Dean. "Data Management in Application Servers." In Red Book.
17 半結構化資料
Semistructured Data
閱讀問題 (PDF)
Reading Questions 17 (PDF)
Bergholz, Andre.〈提高你的身價:一個XML教程〉《IEEE 網路計算》 (2003年8月)。(PDF) 這是一篇對XML、DTD和XML模式的基礎簡介。如果你已經熟悉XML了,就不需要看這篇文章了。
Bergholz, Andre. "Extending your Markup: An XML Tutorial." IEEE Internet Computing (August 2003). (PDF)
This is a basic introduction to XML, DTDs, and XML schemas. If you are already familiar with XML, you do not need to read it.

Goldman, Ray和Jennifer Widom〈XML查詢優化〉,《超大規模資料庫》 VLDB (1999年)。(PDF)
Goldman, Ray, and Jennifer Widom. "Query Optimization for XML." VLDB (1999). (PDF)

Hunter, Jason〈 X就是為了XQuery〉,Oracle網路科技公司。 這是對XQuery語言的簡單介紹, 是一個正在興起的XML查詢處理的標準。
Hunter, Jason. X is For XQuery. Oracle Technology Network.
This provides a very lightweight introduction to the XQuery language, an emerging standard for XML query processing.
18 連續查詢
Continuous Queries
閱讀問題(PDF)
Reading Questions 18 (PDF)
Chen, Jianjun, David DeWitt, Fend Tian和Yuan Wang〈NiagaraCQ:一個可升級的網路資料庫連續查詢系統〉,《紅書》,美國電腦學會--資料管理特別興趣組,ACM SIGMOD (ACM Special Interest Group on Management of Data),2000年。
Chen, Jianjun, David DeWitt, Fend Tian, and Yuan Wang. "NiagaraCQ: A Scalable Continuous Query System for the Internet Databases." In Red Book. ACM SIGMOD. 2000.

Hanson, Eric N., Chris Carnes, Lan Huang, Mohan Konyala, Lloyd Noronha, Sashi Parthasarathy, J. B. Park和Albert Vernon〈可升級觸發器處理〉,《紅書》,國際遠端教育理事會,(InternationaI Council for Distance Education 簡稱ICDE)1999年。
Hanson, Eric N., Chris Carnes, Lan Huang, Mohan Konyala, Lloyd Noronha, Sashi Parthasarathy, J. B. Park, and Albert Vernon. "Scalable Trigger Processing." In Red Book. ICDE. 1999.
19 自適應查詢處理
Adaptive Query Processing
閱讀問題(PDF)
Reading Questions 19 (PDF)
紅寶書中Avnur, Ron和Joseph M. Hellerstein的“Eddies: 連續地適應性查詢處理”.《資料管理特別興趣組會議》SIGMOD (Special Interest Group on Management of Data),2000年。
Avnur, Ron, and Joseph M. Hellerstein. "Eddies: Continuously Adaptive Query Processing." In Red Book. SIGMOD Conference. 2000.

Deshpande, Amol.〈Eddies高階的初始學習〉,《資料管理特別興趣組會議記錄》33卷,第1期, (2004年3月)。(PDF)
Deshpande, Amol. "An Initial Study of Overheads of Eddies." SIGMOD Record 33, no. 1, (March 2004). (PDF)
20 流資料庫
Stream Databases
閱讀問題(PDF)
Reading Questions 20 (PDF)
Abadi, Daniel J., Don Carney, Ugur Cetintemel, Mitch Cherniack, Christian Convey, Sangdon Lee, Michael Stonebraker, Nesime Tatbul和Stan Zdonik等〈Aurora:流資料管理的一種新的模型和架構〉,《超大規模資料庫雜誌》12卷,第2期 (2003年8月):第120-139頁。(PDF) 閱讀第1到6章,注意這不是《紅書》中的Aurora那篇文章。
Abadi, Daniel J., Don Carney, Ugur Cetintemel, Mitch Cherniack, Christian Convey, Sangdon Lee, Michael Stonebraker, Nesime Tatbul, and Stan Zdonik. "Aurora: a New Model and Architecture for Data Stream Management." VLDB Journal 12, no. 2 (August 2003): 120-139. (PDF)
Read Sections 1-6. Note that this is not the Aurora paper in the Red Book.
高級主題
Advanced Topics
21 資料挖掘和序列化查詢
Data Mining and Sequence Queries
閱讀問題(PDF)
Reading Questions 21 (PDF)
Lerner, Alberto和Dennis Shasha〈AQuery:面向順序資料、最優化技術和實踐的一種查詢語言〉,《超大規模資料庫》2003年。 (PDF)
Lerner, Alberto, and Dennis Shasha. "AQuery: A Query Language for Ordered Data, Optimization Techniques, and Experiments." VLDB. 2003. (PDF)
22 模糊查詢
Approximate Querying
閱讀問題 (PDF)
Reading Questions 22 (PDF)
Hellerstein, Joseph, Ron Avnur, 和Vijayshankar Raman.〈Informix在控制下:線上查詢處理〉,《紅書》,資料挖掘和知識發現,12卷,2000年,第281-314頁。
Hellerstein, Joseph, Ron Avnur, and Vijayshankar Raman. "Informix under CONTROL: Online Query Processing. Data Mining and Knowledge Discovery." In Red Book. Vol. 12, 2000, pp. 281-314.
  考試 2
Exam 2
   
23 資料流程的連貫性和可用性
Consistency and Availability in Data Streams
閱讀問題(PDF)
Reading Questions 23 (PDF)
Hwang, Jeong-Hyon, Magdalena Balazinska, Alexander Rasin, Ugur Cetinemel, Mike Stonebraker和Stan Zdonik等.〈分散式流處理的高可用的性演算法〉,《國際遠端教育理事會》(InternationaI Council for Distance Education 簡稱ICDE)。2005年。(PDF)
Hwang, Jeong-Hyon, Magdalena Balazinska, Alexander Rasin, Ugur Cetinemel, Mike Stonebraker, and Stan Zdonik. "High-Availability Algorithms for Distributed Stream Processing." ICDE. 2005. (PDF)
24 課程的最後一天總結
Last day of Class Presentations
   

 
 
課堂講稿
Lecture Notes: Lecture notes files 課 課程單元
基本原理
Fundamentals
1 介紹
Introduction
2 關係模型和SQL語句
The Relational Model and SQL
3 邏輯設計和物理資料庫基礎 (PDF)
Logical Design and Physical Database Fundamentals (PDF)
4 現代關聯資料庫系統介紹 (PDF)
Introduction to Modern Relational Database Systems (PDF)
查詢處理
Query Processing
5 優化的基本原理
Optimization Fundamentals
6 連接演算法和記憶體管理 (PDF)
Join Algorithms and Memory Management (PDF)
7 索引
Indexing
8 分散式資料庫
Distributed Databases
9 資料倉庫
Data Warehouses
10 可擴展和面向物件的資料庫
Extensibility and Object Databases
事務
Transactions
11 事務介紹
Introduction to Transactions
12 事務第二部分
Transactions Part 2
13 鎖機制和一致性(PDF)
Locking and Consistency (PDF)
14 併發控制的優化
Optimistic Concurrency Control
  考試1
Exam 1
15 分散式事務和複製
Distributed Transactions and Replication
網路化資料管理
Networked Data Management
16 Web服務
Web Services
17 半結構化資料
Semistructured Data
18 連續查詢
Continuous Queries
19 自適應性查詢處理
Adaptive Query Processing
20 流資料庫
Stream Databases
高級主題
Advanced Topics
21 資料挖掘和序列化查詢
Data Mining and Sequence Queries
22 模糊查詢
Approximate Querying
  考試2
Exam 2
23 資料流程的連貫性和可用性
Consistency and Availability in Data Streams
24 課程的最後一天總結
Last day of Class Presentations

 


這個部分提供全套的作業和答案

作業文件 作業 答案
作業 1(PDF) (PDF)
作業 2 (PDF) (PDF)
作業 3 (PDF) (PDF)


這個部分提供兩套考試題

考試文件 考試 答案
考試題 1 (PDF) (PDF)
考試題 2 (PDF) (PDF)

This section provides the two quizzes for the course.

Exam files EXAMS SOLUTIONS
Quiz 1 (PDF) (PDF)
Quiz 2 (PDF) (PDF)

 

這 裏列出了資料庫系統的可選的課堂主題。每個專題需要2到3名同學組隊一起完成。我們並不要求大家一定要選擇這個列表中的題目。在選擇專題期間,你們可以向 指導老師提交你們自己的題目並得到批准。總之,一個好的專題可能來自於研究小組中挑戰資料管理課題的那些同學,(簡單地設計一個模式或者安裝一個原有的資 料庫可不是一個具有挑戰性的課題!)其他項目課題可以是我們課堂上學習過的或者將要學習的系統,比方說,你可以要在公開源代碼的Postgres資料庫上 補充一個新的索引類型,或者實現併發控制的優化(查看紅寶書),然後與鎖機制併發控制進行比較。

你必須在第9節課時提交專題大綱的初步方案。其中要包括一頁紙的內容來講述你的專題計畫和隊友名單。這個大綱不記分,但是不交大綱會影響到最後的項目評分。在下幾週時間裏我將會花一些時間分別和每組討論一下項目大綱。

你們提交的專題的研究報告(10到15頁左右)的格式類似於我們這一學期看到的那些研究論文。這些主題是大家自己把握的,所以請確保你選的課題適合在未來的10週時間內供你們的組員一起進行研究。

可選的專題(以及如何獲得更多的資訊)

TinyDB 項目

TinyDB是一種在小型的無線傳感設備(例如 強弩公司的「塵埃」晶片)上使用的資料庫系統。用戶可以通過聲明查詢語句來收集資訊。有很多可行的TinyDB的擴展,一些想法如下:

設計一個簡單的程式設計環境,使用戶或程式師可以開發一些新的方法來擴展TinyDB,比如在資料庫系統中讓用戶使用自定義函數。
實現一套操作符或擴展TinyDB查詢語句,使其支援一些信號處理或者時序資料的分析演算法。 改進TinyDB使其在非連接的感應器網路拓撲下也能使用。

對於這個主題感興趣的學生可以得到一個模擬器和硬體,關於TinyDB的更多資訊可以與我(Madden教授)聯繫。

複製狀態機

研究資料庫複製的複製狀態機的可行性(查看6.033的課堂筆記)。主要的挑戰在於資料庫並不保證序列併發的查詢語句的確定執行,所以需要一些睿智來保證所有的複製在同一個狀態下執行。如果你對這個專題感興趣,和我聯繫,我這裏有一些已經完成的基礎架構和想法。

流監視程式

資料庫系統最近的一個趨勢是關於“流監控”,我們將會在以後的學習中學到有關 的Aurora系統(見紅寶書)。中心思想是運用資料庫技術於連續的元組的流,而不是用於存儲在磁片上的關係。目前已經有了一些流資料庫,我們在MIT可 以看到一個早期的商業系統。一個好的專題可以是應用這個系統來創建一個有趣的應用。例如一個網路入侵檢測系統,它掃描傳入一台機器的資料;或者是一個病毒 追蹤器,它可以在一封收到的新郵件中探測病毒。聯繫我以獲得關於這個專題更多的資訊。

CiteSeer

麻省理工學院的PDOS研究小組已經可以將資料保存在CiteSeer系統中,CiteSeer系統不像當前其他系統一樣保存在關聯資料庫中。一個好的專題是改進系統成一個資料庫引擎,並且利用一些新的有趣的SQL查詢語句來擴展新的功能,或者比較一下改進前後的性能差別。

查詢驅動資料的獲取

實現一個軟體雛形或者一個網路監視工具,用這個工具可以決定監視哪些內容,或 者怎樣實現編碼或網路。這個工具在你的設計中,是基於用戶特殊的某種語言的查詢語句(可能是SQL語言)。證明這個系統的性能並不比簡單地收集所有的資料 慢(比如軟體反應速度或監視器需要的帶寬)。聯繫我以獲得更多的資訊和想法。.

資料庫設計和公路交通視覺化應用程式

我們剛開始一個新項目,那就是使用支援802.11協議並以電池供電的個人車 載伺服器來監控道路的堵塞情況。當802.11連接可用時,資料隨時被收集。我們需要一個資料庫系統架構來存儲這些資料,並且可以顯示和查詢這些資料。查 詢最好具有地理空間功能,比如我想查「在某個特定區域中的擁擠的道路」。請與我聯繫以獲得更多的資訊。

個人資訊管理

開發一個可以收集和查詢結構化和非結構化的資料(關於用戶的資料、檔和一般計 算環境)的軟體。例如這個工具可以管理一大堆的URL,可以自動從與這些URL相連的網站中抽取出關鍵字,再將他們保存在資料庫中。這樣一來用戶可以查找 到他們喜歡的網頁中的內容,而不需去記這些URL。或者開發一個可以保存URL和關鍵字所在的網頁檔的軟體來方便對這些檔的查詢。或者開發一個可在資料庫 中保存用戶喜好檔或註冊資訊的工具,並且可以讓用戶撤銷一些失誤的操作以及/或者一些危險的改變。

Haystack中的資料庫性能

Haystack是 一個「通用資訊用戶端」,可以用來儲存任何個人的資料,比如電子郵件、通訊錄、日程表等。它使用RDF格式來保存資料,RDF格式是一種類似於XML的半 結構化表現。Haystack還使用一個定制的內置資料庫系統。Haystack小組將樂意用一個現成的資料庫引擎來代替這個系統,但是這就可能引發很多 明顯的性能問題。一個有趣專題是分析產生這些性能問題的原因,設計一套可用的方案來提高資料庫性能,並且在Haystack中實現。

Haystack中的結構化資料探索

創建處理一個非結構化資料(例如那些沒有固定模式的資料)的資料庫系統的難處 在於查詢這些資料會很困難,因為用戶不知道他們要查詢哪些欄位。一個有趣的問題是試著開發一個工具,可以讓用戶將那些和系統中的記錄有類似模式的資料插入 其中。一個類似的挑戰在於開發一個程式設計環境,使開發者可以容易查詢那些沒有特定模式(但是模式又是已知)的資料。

流資料系統中的完整性約束

現今的流資料處理系統都沒有提供方式,讓用戶來定義一些約束在他們可以處理的資料上,比如金融分析程式想驗證任何一筆支出都沒有超出可用的範圍。這個項目將要解決這些約束的具體意義,並且研究對這些約束進行檢查和操作的高效的方法。請與我聯繫以獲得更多的資訊。

This is a list of possible class projects related to database systems. Projects are to be done in teams of 2-3 people. You are not required to choose a project from this list -- pending, of course, approval of your project with the instructor. In general, a good source of projects can be people in your research group who have challenging data management issues (simply designing a schema and installing an off-the-shelf database is not a challenging issue!) Other possibilities include implementing one of the systems we have studied (or will study) in class -- for example, you might add support for a new type of index to the Postgres open source database, or implement optimistic concurrency control (see the Red Book) and compare it to locking-based concurrency control.

You must turn in a preliminary project proposal in lecture 9. This should consist of about 1 page of text describing what you plan to study in your project, as well as a list of your team members. The proposal will not be graded, but not turning in a proposal will adversely affect your final grade on the project. I will meet with each group individually for a few minutes during the next few weeks to discuss the project proposal.

The deliverables for your project are a research paper (10-15 pages) similar to the sort we have read throughout the semester. Projects are very self-directed, so make sure your topic is something you feel comfortable building as a team over the next 10 weeks.

Possible projects (and where to look for more information, when available):

TinyDB Projects

TinyDB is a database system that runs on networks of tiny, wireless sensing devices (e.g., Crossbow Motes and allows users to collect information from the via declarative queries. There are many possible kinds of extensions to TinyDB; some ideas:

Design a simple programming environment so that users and programmers can extend TinyDB with new functions, just like users can write user defined functions in database systems.
Implement a set of operators or extend the TinyDB query language with support for some kind of signal processing or time-series analysis algorithm. Make TinyDB work in the face of disconnections in the sensor network topology.

There is a simulator and hardware available for students interested in one of these projects. Contact me (Professor Madden) for more information about TinyDB.

Replicated State Machines

Explore the feasibility of replicated state machines (see your 6.033 class notes) for database replication. The challenge here is that databases don't guarantee deterministic execution of a sequence of concurrently executed queries, so some cleverness is required to keep all replicas in the same state. If you are interested in this project, contact me -- there is some basic infrastructure and thinking that has been done already about this topic.

Stream Monitoring Applications

A recent trend in database systems has to do with "stream monitoring" -- we will read about the Aurora system (see the Red Book) later in the class. The basic idea is to apply database technology to continuous streams of tuples, rather than to relations stored on disk. There are several stream database systems that are available -- we have access to an early commercial system here at MIT. A good project would involve taking this system and using it to build an interesting application -- e.g., a network intrusion detector that scan data coming into a machine, or a virus tracker the catalogs virus in incoming emails. Contact me for more information.

CiteSeer

The PDOS research group at MIT has access to the data for the CiteSeer system, which is currently not stored in a relational database. An interesting project would be to port the system to a database engine, and extend the functionality with some new and interesting queries enabled by SQL, or to compare the performance before and after the porting.

Query-Driven Data Acquisition

Implement a software profiler or network monitoring tool that decides what to monitor (or how to instrument code or the network) based on user-specified "queries" in some language (possibly SQL) of your devising. Show that the performance of this system (e.g., software latency or bandwidth consumed by the monitor) is less than with naive collection of all data. Contact me for more information and ideas.

Database Design and Visualization for a (Road) Traffic Application

We are starting a new project to monitor road congestion using 802.11-equipped, battery-powered servers in individual cars. Data will be collected opportunistically, when 802.11 connections are available. We need a database system infrastructure to store this data, as well a set of tools to display and query it. Queries will have a geo-spatial flavor (e.g., "find slow roads in a particular region"). Contact me.

Personal Information Management

Build a utility for collecting and querying structured and unstructured data about a user's data, files, and general computing environment -- for example, this tool might manage lists of URLs, automatically extracting keywords about those URLs from the associated Web sites and storing them in a database so that users can search for their favorite Web pages without remembering URLs. Or build a system that stores URLs and keywords with downloaded files to facilitate file search. Or build a tool that keeps a database of a users preferences files (or registry entries) and allows users to "rollback" inadvertent and / or nasty changes.

Database Performance in Haystack

Haystack is a "universal information client" useful for storing all sorts of personal data -- email, contacts, calendars, etc. It stores data in RDF (an XML-like semi-structured representation) and uses a custom in-memory database system. The Haystack team would like to be able to replace this system with an off-the-shelf database engine, but there are some significant performance issues in doing so. An interesting project would be to analyze the cause of these performance issues, devise a set of recommendations for how to improve database performance, and implement this in Haystack.

Exploiting Structured Data in Haystack

One of the challenges of building a database system for unstructured data (e.g., data where there is no fixed schema) is that formulating queries over such data is very hard (because users don't know which fields to query). One interesting question is to try to build a set of tools that encourage users to insert data that has a similar schema as records already in the system. A similar challenge is to devise a programming environment that makes it easy for developers to query data that has no definite schema (but where something about the schema is known.)

Integrity Constraints in Streaming Systems

Current stream data processing systems do not provide any way for users to specify constraints on the data that they can handle -- for example, a financial analysis application might want to verify that no purchases exceed some available balance. This project would involve defining what such constraints mean, and exploring ways to efficiently check and react to them. Contact me.


 
對「課程6.893:資料庫系統」這門課有興趣的教育家、學生和自學者們,歡迎來和其他應用這個教材學習或教課的人在這個討論群組上互動。

這個服務是由麻省理工學院開放式課程提供,由猶他州立大學教育科技系的「開放持續學習機會研究群」所管理。世界各地的獨立學員可以互相連繫、協同合作、組織學習小組,及就利用麻省理工「開放式課程網頁」教材資源於他們正規或非正規教育學習時得到支援。

「開放式學習支援網」(Open Learning Support, 簡稱OLS)是一個著眼著眼於建立「社群軟體」的研究計劃,讓非正規學習社群利用現存公開的教材而組織起來。OLS基本前提是完整的教育機會必須讓使用者 能夠與能解答其問題或提供支援的其他人建立起溝通管道。贊助者一般只能提供免費開放的網頁教材,但很難提供這樣的社群管道。社群支援必須由其他使用者提 供。因此,OLS是:

在麻省理工「開放式課程網頁」以外獨立運作的。
需要使用者註冊並登入才能參與的
並不頒授任何學位或文憑的計劃
不提供與麻省理工或猶他州立大學教職人員直接連繫的管道
馬上來本課程《6.893 資料庫系統》的討論群組看看吧。

「開放式學習支援網」是由The William and Flora Hewlett 基金會贊助提供。


 

留下您對本課程的評論
標題:
您目前為非會員,留言名稱將顯示「匿名非會員」
只能進行20字留言

留言內容:

驗證碼請輸入3 + 9 =

標籤

現有標籤:1
新增標籤:


有關本課程的討論

目前暫無評論,快來留言吧!

Creative Commons授權條款 本站一切著作係採用 Creative Commons 授權條款授權。
協助推廣單位: