Fall 2009 CS 3/586 Introduction to Databases

Instructor	Len Shapiro len at pdx dot edu, 115-13 FAB.
Class Meeting	Tuesday, Thursday 12:00-1:50 PM , NH454
Office Hours	Tues. 4-4:50PM, Thurs. 10:30-11:20AM, and by appt.

Weekly Schedule

Date	Topic	Reading Assgt	Slides; Quizzes	Hmwk.
Sept 29,Oct 1	Intro; Database Design; Relational Data Model; Intro to SQL	Ch. 1; Ch 2 (skip 2.4.3-5, 2.5.4); 3.1,3.2,3.4,3.5.1-3,5.1.1, 5.2.1	Lecture1	Homework 1
Oct 6,8	SQL	Ch 5.2-6	Lecture2 Quiz 1 ans	Homework 2 H1Answers
Oct 13,15	More SQL, Relational Algebra,	Ch 4.1-2, Secs 5.7-9	Lecture3 Quiz 2 ans	Homework 3 H2Answers
Oct 20	Constraints, Triggers, Views.DB App. Devt	Sec 6.1	Lecture4 , Quiz 3 ans	H3Answers
Oct 22	MIDTERM EXAM on all preceding material Midterm answers
Oct 27,29	Midterm review, Security, PhP	Ch 21, 1-6	Lecture 5
Nov 3,5	Storage and Indexing, Disks and Files, Query Eval.	Secs 8.1,2,3.2,5; Sec 9.1, Ch 12.1, 12.3.3, 12.4.1,12.6,	Lecture 6	Homework 4
Nov 10,12	Transactions, Backup and Recovery, Concurrency	Ch 16, Sec 17.1	Lecture 7 Quiz 4 ans	Homework 5 H4Answers
Nov 17,19	Schema Refinement and Normal Forms, Physical Database Design and Tuning	Secs 20.1-3, 20.6,7,9 20.11, 20.12, Ch. 19 (omit Secs 19.7, 19.8),20.8	Lecture 8 Quiz 5 ans	Homework 6 H5Answers
Nov 24	Unstructured Data		Lecture 9 Quiz 6 ans	Homework 7 H6Answers
Dec 1	Data Warehousing, Analytic databases	Ch 25	Lecture 10
Dec 3	No class – demo Homework 7
Dec 10	FINAL EXAM covering the entire course. Thursday December 10, in the usual classroom, 10:15-12:05 (sched)

My Goal

My goal for this course is that every one of you succeeds in it. If you all get A’s I will be very happy. I want you to do your best. I must grade you on what you do, not on what you know, but if anything stands in the way of your doing your best, then I want to know about it so I can help you to do your best.

If you don’t understand something I say in class, it’s my fault. Please raise your hand and let me know so I can try to do better. If you fear you will be embarrassed, give me just one chance to prove that you won’t be.

Objectives for the course

Graduates of this course will be able to:

1) Transform data into information:

a) Transform requirements into an ER diagram

b) Transform an ER Diagram into a relational Schema

c) Normalize a relational schema into BCNF

d) Implement an application that includes embedded SQL

2) Translate between equivalent English, SQL, and relational algebra queries.

3) Explain how queries are optimized and processed

4) Given a schema and a workload, evaluate which indexes are likely to be most effective.

5) Explain how basic backup, recovery and concurrency control services are implemented.

6) Explain how queries are processed by a search engine.

Class E-mail

The e-mail list for this class is 386@cecs.pdx.edu. It will be used for announcements from the instructor. You can also send questions and answers to this mail list. In order to join the mail list, go to https://mailhost.cecs.pdx.edu/mailman/listinfo/386 . I enrolled some of you in the list already, and those people received email this weekend.

Textbooks

REQUIRED: Database Management Systems, 3rd Edition. By Raghu Ramakrishnan and Johannes Gehrke, McGraw Hill, 2000, ISBN 0-07-246563-8.

New Catalog Description

Introduction to fundamental concepts of database management using primarily the relational model. Schema design and refinement, query languages, database application environments, physical data organization, overview of query optimization and processing, physical design, recovery and concurrency control, query processing for search engines. As time permits, the course may cover security, data warehousing and analytic databases. Prerequisites: CS 161, 250. Recommended prerequisite: 251.

Grading
Pre-Requisite Quiz: I will give a pre-requisite quiz the first day of class, based on the contents of CS161 and 250. If you do not take it, or do not pass it, then you must obtain my permission in order to pass the course.

Homework: There are 7 homeworks, each worth 5%, but we drop your lowest grade. Homeworks are done in teams of one or two students. Please remind me to make time after the first few classes for you to find friends. Homeworks are available online on THURSDAY and are due in hard copy the following THURSDAY before class begins. Type your homework, though you may draw diagrams by hand. Homework 7 is an exception to the above. It is distributed at the beginning of the course and you should begin work on it soon. It is worth 10% of your grade and cannot be dropped as the lowest score. Thus your homework is worth 35% of your grade.

Quizzes: There are 7 quizzes, based on learning objectives from the week’s lectures. Each quiz is worth 2%, but I drop your lowest quiz grade, so the quizzes are worth 12% of your grade. A quiz is given at the beginning of TUESDAY’s lecture. There are NO MAKEUPS FOR QUIZZES.

I realize it is hard to avoid traffic and other causes for being late to class. That is why I drop your lowest quiz score. After you are late to one quiz class and receive a zero quiz grade, plan to be in class early on the following quiz Tuesdays.

Quizzes and exams are open book and notes. On both, a check means correct, X means incorrect.

Exams: There is a midterm exam (21%) that covers the 1st half of the class material, and a final exam (32%) during finals week that covers the all class material.

Exercises: At the end of most lectures there are exercises. Answers are in notes view. I advise you strongly to work the exercises and check the answers. If you hand in the worked exercises, each set will earn you 1% extra credit. I will try to end each lecture early so you can split up into study groups to work the exercises in class and I can help you if you have problems. Hand in exercises with each homework assignment.

Grading scale: If you earn 60% or more overall, your grade is guaranteed to be at least D, 70% C, 80% B, 90% A.

Flu

Please take the five action steps recommended here to prevent the spread of the flu: http://www.shac.pdx.edu/H1N1/H1N1syllabi.pdf . According to this university directive http://www.shac.pdx.edu/H1N1/H1N1classrmpolicy_092109.pdf if you exhibit any of these symptoms in class I must ask you to leave: fever (have chills, feel very warm, have a flushed appearance, or are sweating), headache, tiredness, sore throat, runny or stuffy nose, body aches.

Information

Paper Grader is Vijay Gokarn, at vijayg@cecs.pdx.edu. Here are links to Answers to odd numbered question from the text, symbols for Word and symbols for Power Point. If you come to my office and I am with someone, tell me you are “in line” so I can properly triage.

Policies

Students are responsible for anything that transpires during a class - therefore if you're not in a class, you should get notes from your friend. Your friend should also pick up returned homework for you. Don’t expect the instructor to keep track of your uncollected homework.

I cannot accept late homework because I post answers on the web soon after homework is due. However, if you have a family emergency or medical excuse and you tell me before the homework is due, then I will make arrangements with you.

Makeup exams will not be given except in cases of medical or family emergencies. If an emergency arises and you are going to miss an exam, contact me BEFORE the exam to arrange for a special circumstance.

Students with disabilities who are in need of academic accommodations should contact me as soon as possible to arrange needed supports. Students are also encouraged to contact the Disability Resource Center (DRC) for additional information on support services and available accommodations at 503/725-4240 or 503 725-4150.

Cheating

All the work you hand in must be written by you, or you must cite a reference. Violation of this rule will result in your receiving a grade of zero on that assignment, and failing the course.

Supplementary Readings

What follows is a list of online resources that you may find helpful over the course of the class. None of these materials are necessary to complete the class; however, you may find that they can offer you perspectives beyond those offered by the textbook or the instructor/TA, especially if you plan to continue your study in the database field.

SQL Standards

SQL-92 http://www.cs.pdx.edu/~len/sql1992.txt
SQL:1999 http://www.cs.pdx.edu/~len/sql1999.pdf
SQL:2003 http://www.cs.pdx.edu/~len/sql_2003.zip

Some SQL standards web pages:

Relational model

E. F. Codd. A relational model of data for large shared databanks. Communications of the ACM, 13(6):377-387, 1970. (.pdf) (.html )
E. F. Codd. Data models in database management. In Proc. ACM SIGMOD/PODS Workshop on Data Abstraction, Databases, and Conceptual Modeling, pp. 112-114, 1980.
William Kent. Limitations of record-based information models. ACM Transactions on Database Systems, 4(1):107-131, 1979.
Joseph Albert. Algebraic Properties of Bag Data Types, In Proc. 17th International VLDB Conference, Barcelona, Sept. 1991.
Carlo Zaniolo. Database Relations with Null Values (Extended Abstract). In proc. PODS, 1982: 27-33.

Conceptual and Logical Design

Peter P. Chen. The entity-relationship model - Towards a unified view of data. ACM Transactions on Database Systems (TODS), 1(1):9-36, 1976.
William Kent. A simple guide to five normal forms in relational database theory. Communications of the ACM, 26(2):120-25, 1983. (html version)
Eugene Y. Sheng. On bi-level conceptual schemas. In Proc. 1993 ACM conference on Computer Science, pp. 483-488, 1993.

Storage and indexing

Michael Stonebraker Operating system support for database management. Communications of the ACM, 24(7):412-418, 1981.
Douglas Comer. The ubiquitous B-tree. ACM Computing Surveys, 11(2):121-137, 1979.
Gerald Herd and Michael Stonebraker. B-trees re-examined. Communications of the ACM, 21(2):139-144, 1978.

Query processing

D. Chamberlin, et al. A history and evaluation of System R. Communications of the ACM, 24(10):632-646, 1981.
Yannis Ioannidis. Query optimization. Handbook for Computer Science, Chapter 45 (CRC Press).
Goetz Graefe. Query evaluation techniques for large databases. ACM Computing Surveys 25(2): 73-170. 1993.
M.W. Blasgen, et al. System R: An architectural overview. IBM Systems Journal, 20(1):375-396, 1981.
P. Griffiths Selinger et al, Access path selection in a relational database management system. ACM SIGMOD international conference on Management of data, pp. 23-34, 1979.

Transactions

J. Gray. The Transaction Concept, Virtues And Limitations. In Proc. 7th VLDB Conference, Cannes, France, pp. 144-154.1981. ( MS Word document)
C. Mohan, et al. ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging. ACM Transactions on Database Systems, 17(1):94-162, 1992.

Others

Michael Stonebraker and Joseph M. Hellerstein, eds. Readings in Database Systems. Morgan Kaufmann Publishers, 1998. (A number of influential papers. Available in the OGI library.)
Zloof Moshe. Query-by-Example: A data base language. IBM Systems Journal, 16(4):324-343, 1977.
Whitemarsh Information Systems Corp. Presentations on SQL Standards

LEAP Relational Algebra RDBMS, SourceForge