Database Systems: The Complete Book (2024)

Database Systems: The CompleteBook

Welcome to the home page for Database Systems: The Complete Book(DS:CB),by HectorGarcia-Molina, Jeff Ullman,and Jennifer Widom.The second edition of this book was published on June 9, 2008.Some material on this page is also relevant to AFirst Course in Database Systems, 3nd Edition.

The Gradiance contract with Pearson (Addison-Wesley + Prentice-Hall) has terminated, andwe have decided to turn Gradiance into a FREE service.If you are an instructor who wants to use the system, startby creating an account for yourself at www.gradiance.com/servicesNOT at the Pearson site.Note: passwords are >= 10 letters+digits,with at least one of each. Also, we cannot make an account be aninstructor account for a book if the same account has registeredas a student for a course using the same materials.

Then, email your chosen login,with the book whose materials you want, to support@gradiance.comWe'll enable you to create a class using those materials.There are manuals at www.gradiance.com/info.htmlthat should enableyou to use the system without problems, but feel free to emailsupport@gradiance.com if you encounter difficulties.

In addition, we have created eleven free "omnibus classes" covering Databases,Automata, Compilers, Operating Systems, Introductory Java, Data Structures,and Data Mining. Students wishing to join either one of these classeswill find the Student Directions useful.

Index

• Sample Database Projects
• Solutions to Selected Exercises
• Errata
• Slides and Lecture Notes
• Oracle Guide
• Exams and Homework from Stanford Courses
• Material from the First Edition Deleted from the Second
• Course Materials From Elsewhere
• Book-Ordering Information

About the Book

Table of Contents and Sample Chapters

• Table ofContents.
• Sample chapters in PDF:Chapter 1.Chapter 2.
• The book has Demonstrated Appeal toReaders of All Ages.

New Features

• We begin with a discussion of relational design, rather than E/R design.There are a number of technical improvements to the discussion of functionaland multivalued dependencies, including the synthesis algorithm for 3NF andthe use of the "chase" algorithm to make inferences of dependencies.
• We have added coverage of high-level design using UML.
• Coverage of index selection and use of materialized views has been added.
• There is new coverage of the database aspects of PHP.
• There are two new chapters on XML-related material, including XML Schema,XPath, XQuery, and XSLT.
• Coverage of information integration has been expanded. There is new coverage ofalgorithms for processing mediator queries. Also added is a treatment of"local-as-view" mediation and the techniques necessary to process queries in this setting.
• There is greatly expanded coverage of data mining for large-scale data.Improvements on the a-priori algorithm for association rules are explained.We also added material on similarity search (shingling, minhashing,and locality-sensitive hashing) and clustering of large-scale, high-dimensional data.
• The PageRank algorithm is explained, along with generalizations to topic-specific PageRankand TrustRank for detecting link spam.
• Entity resolution (merging of similar records) is covered.
• Material on peer-to-peer databases has been added, including an algorithm for distributed hashing.

Support Materials Available

The materials below areavailable for use by others.Instructors are welcome to use them in their owncourses, download them to their own class' website, or modify them to suit.However, you must acknowledge the source of the original and notattempt to place your own copyright on this material.

Note: If you are creating your own materials for a course basedon the book and would like to share themwith the world, we would be happy to create a link to them.

Projects

• Eric Silverberg's Project (Star-Trek guide).
• Jake Olefsky's Project(Brain Teasers).
• Steven van Loben Sels' Project(Rock Music).
• Rafael Hernandez's Project(Shutter Shop).
• Keith Ito's Project(Literature Search).

Solutions to Exercises

Because the Gradiance (GOAL) automatic homework system is now available, we are notupdating the on-line solutions. Prentice-Hall is preparing a complete solutionmanual available to instructors only.

On-line solutions to selectedexercises from the first edition of DS:CB.

Errata

• The Current Errata Sheet for DS:CB(Errata for the 3nd edition of FCDB are those on pp. 1-554).
• The Errata Sheet for DS:CB First Edition(Errata for the 2nd edition of FCDB are those on pp. 1-502).

Our list is growing!Send us a correction to ullman aT gmail DoT comand see yourself acknowledged on the errata page.

Slides and Lecture Notes

• Jeff's Slides for CS145, Fall,2007.
• Jennifer's Notesfor CS145, Spring, 2006.
• Jeff's Slides for CS145, Fall,2004.
• Jeff's Slides for CS145, Fall,2002.These are available in Powerpoint (with voiceover), or in GIF withoutthe voiceover.
• Jennifer's Notesfor CS145, Spring, 2002.
• Hector'sSlides for CS245, Winter, 2002.
• Jeff's Slides for CS145, Fall, 2001.They are available on-line as Postscript and PDF only.
• Slides in PowerPoint and other formats, by Arthur Keller, similar tothe above.
• Jeff's Slides for CS245A,Winter, 1998.

Documentation for Oracle DMBS

The CS145 Oracle Guide.

Handouts, Homeworks, and Exams

CS145

This material is based approximately on Ch. 1-12 of DS:CB, or the entirebook FCDB.

Usually, Jeff teaches CS145 in the Fall and Jennifer in the Spring.

• Fall,1995.
• Fall,1996.
• Spring,1997.
• Fall, 1997.
• Spring, 1998.
• Fall, 1998.
• Spring 1999 (Taught by Jun Yang).
• Fall, 1999.
• Spring, 2000.
• Fall, 2000.
• Spring, 2001.
• Fall, 2001.
• Spring, 2002.
• Fall, 2002.
• Spring, 2003.
• Fall, 2003.
• Spring, 2004.
• Fall, 2004.
• Fall, 2006.
• Fall, 2007.

CS245

This material is based approximately on Ch. 13-21 of DS:CB.

• Winter 1998 CS245A (Taught byJeff).
• Winter 1999 CS245 (Taught byHector).
• Summer 1999 CS245 (Taught byClaire Cui).
• Winter 2000 CS245 (Taught byHector).
• Winter 2001 CS245 (Taught byHector).
• Summer 2001 CS245 (Taught byChris Olston).
• Winter 2002 CS245 (Taught byHector).
• Winter 2003 CS245 (Taught byHector).

CS345A

CS345A is occasionally taught as Web-mining. When it is, Chapters 22 and 23of DS:CB are covered, along with other material. You can find lecture notesfor past editions of CS345A, taught by Anand Rajaramanand Jeff Ullman, in Data-Mining Notes.

CS346

CS346 is the database project course.It covers query optimization, as in Ch. 15-16, in more detail than doesCS245.

• Winter 1999 CS346(Taught byJennifer).

Materials from First Edition Deleted in Second

1. Object-Oriented Query Languages (old Sections 4.1, 9.1, 9.2, and 9.3).
2. Recursive Datalog (old Section 10.3).
3. View Serializability (old Section 19.2).

Also Check Out

• Materials from IT University of Copenhagen: A Basic Course by Rasmus Pagh andan Advanced Courseby Pagh and Anna Östlin.
• IreneGuessarian's notes from University of Paris VI/LIAFA (French overPostscript).
• Tim Finin'sCMSC461 at University of Maryland, Baltimore County has someuseful materials, such as an Oracle guide.
• AlonLevy's CS444 at the Univ. of Washington.
• JagdishGangolly's course on DB's for accounting at SUNY-Albany.

Ordering Information

• ThePrentice-Hall Web Page for the book has further information.
• TheAmazon Page for the book.