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. Mutation rate of data items. Benefits and cost of indexing.

The architecture of a DBMS.

ANSI/SPARC architecture for DBMS. The need for a Data Definition Language. Brief history of Data Models and DBMS. Corporate evolution and the need for Standards. Schema evolution.

Transaction processing, physical database design.

Recap of ACID properties of transactions. Rotating storage devices, space allocation, the need for synchronised atomic change. Indexing and inverted files (B-trees assumed). Extensible hashing schemes.

Database design.

Entities and attributes. Functional dependency between attribute sets. Single and multi-attribute keys. Relationships between entities. Entity-Relationship (E/R) diagrams. Degree and multiplicity of relationships. Entity types as classes. Object-based design methodology. UML.

Network model of data.

Historical review of DBMS. CODASYL/DBTG proposals as an example of the ANSI/SPARC architecture. Bachman diagrams. Storage diagrams and explicit traversal. Record identifiers (DB keys). Control of record placement. Lack of data independence.

Relational model: basic semantics.

Codd's 1970 paper. Data independence. Domains and data types. n-tuples over domains. First Normal Form. Keys as user level tuple identifiers. Data independence. Describing entities using tuples. Describing inter-entity relationships by tuples. Research into efficient implementation. System-R. Duplicate elimination. Relations as sets, Tables as bags. Transaction support, Roll-Back. Work on query optimisation. SQL.

Relational algebra.

PRTV and ISBL. Boolean operations on relations. Key-based semantics. Cartesian product. Select, Project and (equi-)Join. Theta-joins. Semi-joins. Examples. Techniques for implementing joins. Cardinality. Views as expressions in the relational algebra. INGRES, access control.

Relational schema design.

Functional dependence between attributes. Data redundancy for access, update and insertion anomalies. Second and Third Normal Form (3NF). Boyce-Codd normal form. Examples. Loss of referential integrity. Multi-valued dependencies. Fourth Normal Form (4NF).

Relational calculus and SQL.

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

Semantic considerations in the SQL2 data model.

Entity integrity. Modelling application datatypes, repeating groups. Collection types. Subdomains and inheritance. Generalisation. Referential integrity and Foreign keys. The need for transitive closure. Fixed-point semantics. Deductive databases. DATALOG. SQL3.

Distributed applications.

Legacy databases. Data mining. Corporate restructuring. Federation. Identifying entities, naming. Data collection and data warehouses. Materialised views. Entity representations as objects. (O)ODBMS. Object Data Management Group. The Object Database Standard ODMG 2.0. The ODMG object model.

The Object Database Standard ODMG 2.0.

The ODMG Object Model. ODMG/ODL as a Data Definition Language. Metadata and the ODL Schema Repository. Type system: atomic objects (user-defined), collection objects, literal types, structures. NULL-extended types. Tables. Attributes. Object identifiers as values. Relationships and their inverses. Operations and exceptions. Transactions. Lock types, 2PL as the default concurrency control policy. Databases. OQL: an object query language extending the SQL query sublanguage. Update by method invocation. Navigation via path expressions. WHERE clauses. Java binding, persistence by reachability.

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 2.0. Morgan Kaufmann.