A Guided Tour of Relational Databases and Beyond

Database theory is now in a mature state, and this book addresses important extensions of the relational database model such as deductive, temporal and object-oriented databases. It provides an overview of database modelling with the Entity-Relationship (ER) model and the relational model providing the pivot on which the material revolves. The main body of the book focuses on the primary achievements of relational database theory, including query languages, integrity constraints, database design, comput able queries and concurrency control. The most important extensions of the relational model are covered in separate chapters. This book will be useful to third year computer science undergraduates and postgraduates studying database theory, and will also be of interest to researchers and database practitioners who would like to know more about the ideas underlying relational dat abase management systems and the problems that confront database researchers.

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?.- Discussion.- Background Material.- Exercises.- The Entity-Relationship Model.- Graphs.- The Building Blocks of an Entity-Relationship Diagram (ERD).- 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 Equivalence of Query Languages for the Relational Model.- Integrity Constraints in Relational Databases.- Inference of Integrity Constraints.- Data 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.- Horizontal Decompositions.- Algorithms for Converting a Relation Schema into Normal Form.- 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.- Subclasses of Computable Database 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.- Locking.- Deadlock.- Lock Granularity and Lock Manager.- Lock Manager Implementation.- Timestamp Ordering.- 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.