MASSACHVSETTS INSTITVTE OF TECHNOLOGY Department of ElectricProject 3 - DatabasesPurposeRelational DatabasesOperations on Relational TablesDatabase implementationPart 1: Table ImplementationPart 2: Adding Enumerated TypesPart 3: Data Abstractions Using TablesPart 4: Life Expectancy DataSubmissionMASSACHVSETTS INSTITVTE OF TECHNOLOGY Department of Electrical Engineering and Computer Science 6.001 Structure and Interpretation of Computer Programs Fall Semester, 2005 Project 3 - Databases • Issued Monday, October 24th • To Be Completed By: Friday, November 4th, 6:00 pm • Code to load for this project: o Links to the system code file census-dbase.scm is provided from the Projects link on the course web page. Purpose Project 3 focuses on the implementation and use of relational databases. Higher-order procedures, data structures, tagged data, and data abstraction all play a role in the project. In addition to implementing relational database operations, you will also extend the system, and then explore its use with a real dataset. The last part will use life expectancy data (you can find a link to this report on the project web site) from the U.S. Department of Health and Human Services. Relational Databases In lecture 13, a simple table abstract data type (ADT) was described, where each entry in a table consists of a (key,value) pair. In this project, on the other hand, we consider relational database tables that generalize our lecture tables in a number of important ways. First, each entry or "row" in a relational table can store several values (v1,v2,v3,...), each value being in a distinct "column." Second, any column can be considered to hold a "key," depending on the use of the table. For example, one can formulate a "query" on the table to find one or more rows which have a particular value, or satisfy constraints on one or more values. Finally, the tables from lecture depended on unique keys; adding another (key, value) pair where the key was already in the table replaced the previous value associated with the key with the new value. In contrast, we will see that relational tables do not require that every key be unique.Each table in a relational database stores information about a "relationship" between values. A table consists of an unordered list of rows and an ordered list of columns. Each row of the table has a value for each column. Each column has a name and a type of data stored in that column. For example, a table which stores a relation between name and major: name major ben 6 jen 3 amy 12 kim 13 alex 6 This table has five rows and two columns. Though not shown in the table above, the name column has type symbol and the major column has type number. Attempting to add a row that doesn't meet these type constraints will yield an error. This careful type-checking will lessen the chance of database corruption escaping unnoticed. Operations on Relational Tables The following operations are specified on relational tables. Some of these operations are defined in census-dbase.scm; in other cases, you will complete these procedures as part of this project. • make-empty-table columns Creates a table, given a list of column names and types, and returns an empty table. Once created, the columns for a table never change. • table-insert! row-data table The row is inserted into the table if the data in the row matches the expected types of the columns for the table. Rows might be inserted anywhere, as the table doesn't specify any default ordering of the rows. Note that the same row of data can be entered more than once in the table; this is unlike the simple tables from lecture where the key had to be unique. The table-insert! operation modifies an existing table (and returns a pointer to the table as the return value), as opposed to creating a new table with the row inserted. This procedure is provided to you; forthe moment, ignore the mechanics of this modification (it will be covered in the lecture on mutation). • table-delete! predicate table Rows are deleted from the table if the provided predicate returns true when applied to the row. Similar to insert, this operation modifies the table (and returns a pointer to the table as the return value). • table-select predicate table A new table is created and returned with the same columns, but containing only those rows for which the provided predicate returns true. A select using the predicate (lambda (row) (= (get 'major row) 6)) returns the table: name major ben 6 alex 6 • table-update! predicate column updateproc table Modifies an existing table (and returns a pointer to the table as the result), changing those rows for which the predicate returns true. A single column is updated, with the new value being computed by another provided procedure. For example, (table-update (lambda (row) (eq? (get 'name row) 'amy)) 'major (lambda (row) 6) table) modifies the table, setting amy's major to 6. • table-order-by column table Creates and returns a new version of the specified table, with rows ordered based on the values of a particular column from the table. Our example table, ordered by major:name major jen 3 ben 6 alex 6 amy 12 kim 13 Many of these operations are similar to the SQL commands of the similar name (e.g. insert, delete, select, update). SQL (Structured Query Language) is used to manipulate almost every relational database on the market. Database implementation Read over the code in census-dbase.scm. Check the DrScheme references manual as needed if there are procedures or special forms being used that you are unfamiliar with. Types A type-table contains an association list (as discussed in lecture 11) of type name, and a pair of procedures, the checker and the comparator, for operating on that type. • the checker returns true if a given value is of the specified type • the comparator compares two values of the type, and returns true if the first one is "less than" the second one. Essentially, this provides an ordering over the values of a given type, so that they can be sorted. Other abstractions Make sure to familiarize yourself with the column, row and table abstractions. The following annotated picture of the printed representation of the example table may help:Part 1: Table Implementation In this part, you will complete the implementation of the table abstraction. For this part, a limited set of example and test cases have been
View Full Document
Unlocking...