Databases

Lecturer: Dr J.K.M. Moody (km@cl.cam.ac.uk)

No. of lectures: 12  

The nature of a database.

Essential features of databases, examples. Formal data models: resilience to change, data independence. The role of metadata.

The architecture of a DBMS.

ANSI/SPARC architecture for DBMS. The need for a DDL. CODASYL and relational model terminology for schemas etc.

Logical database design.

Application database design methodology. Access for retrieval and update, the benefits and cost of indexing. Mutation rate.

Physical database design.

Rotating storage devices, space allocation, persistent record identifiers, the need for synchronised atomic change. Indexing and inverted files (B-trees assumed). Value set mechanisms.

Network model of data.

CODASYL/DBTG proposals as an example of the ANSI/SPARC architecture. The CODASYL DML and COBOL verbs. Currency and database navigation.

Relational model: basic semantics.

Domains and data types. n-tuples over domains. Keys as application level tuple identifiers. Relations as sets, Tables as multi-sets. Entity descriptions and inter-entity relationships. First Normal Form. Data definition language requirements.

Relational algebra.

Boolean operations on relations. Key-based semantics. Select, Project and (equi-)Join. Examples. Views as expressions in the relational algebra. Their use for access control.

Relational schema design.

Functional dependence between attributes. Data redundancy. Boyce-Codd normal form. Examples. Loss of referential integrity. Multi-valued dependencies. Projection/Join normal form.

Relational calculus.

Relationally complete languages. SQL as a standard. Combining DDL and DML functionality. Multi-set semantics. Null values and Outer Joins. Aggregates and GROUP_BY.

Fixed-point semantics.

Finding paths in transport networks. The `parts explosion' problem. Deductive databases. DATALOG. Computing the transitive closure.

Semantic weaknesses of the relational model.

Identifying database entities. Modelling application datatypes. First Normal Form. Subdomains and inheritance. The Nested Relational Model (NF2). Nested Relational Algebra.

Object-Relational DBMS.

POSTGRES. Extending semantics within the relational standard. The Third-Generation Data Base System Manifesto. SQL3.

Recommended books:

Ullman, J.D. & Widom, J. (1997). A First Course in Database Systems. Prentice-Hall.

Korth, H.F. & Silberschatz, A. (1991). Database System Concepts. McGraw-Hill (2nd ed.).

Date, C.J. (1995). An Introduction to Database Systems, vol. 1. Addison-Wesley (6th ed.).

Kent, W.T. (1978). Data and Reality. North-Holland.

Cattell, R.G.G. (ed.) (1997). The Object Database Standard ODMG-93, Release 2.0. Morgan Kaufmann.