A Guided Tour of Relational Databases and Beyond

An Introductory Example.- What is a Database?.- Why do we Need Database Management Systems?.- The Three Levels of Data Abstraction.- What is a Database Management System?.- The Concept of Data Independence.- What is a Data Model?.- The Relational Data Model.- The Network Data Model.- The Hierarchical Data Model.- The Nested Relational Data Model.- The Deductive Data Model.- An Object-Oriented Data Model.- Discussion.- Background Material.- Basic Concepts of Set Theory.- Basic Concepts of Ordered Sets.- Basic Concepts of Mathematical Logic.- Basic Concepts of the Theory of Computing.- Finite-Model Theory.- Exercises.- The Entity-Relationship Model.- Graphs.- The Building Blocks of an Entity-Relationship Diagram (ERD).- Entities.- Relationships and their Functionality.- Attributes and Domains.- Keys.- Recursive Relationships.- Weak Entity Types.- The Steps Needed for Constructing an ERD.- Discussion.- Exercises.- The Relational Data Model.- The Data Structure of the Relational Model.- Query and Update Languages for the Relational Model.- The Relational Algebra.- The Domain Relational Calculus.- Datalog.- An Update Language for the Relational Model.- The Equivalence of Query Languages for the Relational Model.- Domain Independence.- The Equivalence of the Algebra, the Calculus and Datalog.- Integrity Constraints in Relational Databases.- Inference of Integrity Constraints.- Data Dependencies.- Functional Dependencies and Keys.- Armstrong Relations for Functional Dependencies.- The Implication Problem for Functional Dependencies.- Lossless Join Decompositions and the Chase Procedure.- Minimal Covers for Sets of Functional Dependencies.- Projection of Functional Dependencies.- Inclusion Dependencies.- The Chase Procedure for Inclusion Dependencies.- Armstrong Databases for Inclusion Dependencies.- The Implication Problem for Inclusion Dependencies.- Interaction between Functional and Inclusion Dependencies.- The Case of No Interaction Between Functional and Inclusion Dependencies.- Multivalued Dependencies.- Join Dependencies.- Domain and Cardinality Constraints.- The View Update Problem.- Discussion.- Exercises.- Relational Database Design.- Update Anomalies in Relational Databases.- Desirable Properties of Database Decompositions.- The Synthesis Versus Decomposition Approaches to Relational Database Design.- Normal Forms.- Second Normal Form (2NF).- Third Normal Form (3NF).- Boyce-Codd Normal Form (BCNF).- Inclusion Dependency Normal Form (IDNF).- Horizontal Decompositions.- Algorithms for Converting a Relation Schema into Normal Form.- A 3NF Synthesis Algorithm.- BCNF Decompositions.- How to Obtain a Decomposition in IDNF.- Converting an ERD into a Relational Database Schema in IDNF.- Discussion.- Exercises.- Incomplete Information in the Relational Data Model.- Different Types of Null Value.- The Open and Closed World Assumptions.- Introducing Order into the Domain.- Extending the Relational Algebra with Null Values.- Extending Integrity Constraints with Null Values.- The Or-sets Approach.- The Fuzzy Sets Approach.- The Rough Sets Approach.- The Default Values Approach.- Updating Incomplete Relations.- Discussion.- Exercises.- Computable Database Queries and the Expressiveness of the Relational Algebra.- What is a Computable Database Query?.- Formalising Computable Database Queries.- Encodings and Decodings.- Definition of Computable Database Queries.- Subclasses of Computable Database Queries.- Order-Independent Computable Queries.- Isomorphism-Independent Computable Queries.- Encoding-Independent Computable Queries.- An Equivalence Relation on Computable Queries.- Computational Query Completeness.- The Expressive Power of the Relational Algebra.- Adding a Looping Mechanism to the Relational Algebra.- Discussion.- Exercises.- Temporal Relational Databases.- The Importance of Modelling Time.- A Taxonomy of Time in Databases.- Historical Relations.- A Historical Relational Algebra.- Historical Relational Completeness.- TSQL2.- Historical Key Dependencies.- Schema Evolution.- Discussion.- Exercises.- Concurrency Control.- Manifestations of Concurrency Control.- Serialisability.- Serialisability Theory.- Locking.- Two-Phase Locking Policy.- Deadlock.- Deadlock Detection.- Deadlock Prevention.- Lock Granularity and Lock Manager.- Lock Manager Implementation.- Timestamp Ordering.- Timestamp Ordering Implementation.- Serialisation Graph Testing.- Discussion.- Exercises.- Deductive Databases.- Model-theoretic Semantics of Datalog.- Expressive Power of Datalog.- Equivalence Between Datalog Programs.- Datalog Not-Equal.- Updates in Deductive Databases.- Integrity Constraints in Deductive Databases.- Discussion.- Exercises.- Extensions to the Relational Data Model and Recent Directions.- Nested Relational Databases.- Object-Oriented Databases.- Graph-Based Databases.- Active Databases.- Hypertext Databases.- Semistructured Databases.- Knowledge Discovery and Data Mining.- Other Areas.- What Lies Beyond?.- Exercises.- 577.- 609.