A Guided Tour of Relational Databases and Beyond

by Mark Levene, George Loizou

Overview

Addressing important extensions of the relational database model, including deductive, temporal, and object-oriented databases, this book provides an overview of database modeling with the Entity-Relationship (ER) model and the relational model. The book focuses on the primary achievements in relational database theory, including query languages, integrity constraints, database design, computable queries, and concurrency control. This reference will shed light on the ideas underlying relational database systems and the problems that confront database designers and researchers.

Product Details

ISBN-13:	9781852330088
Publisher:	Springer London
Publication date:	06/22/1999
Edition description:	Softcover reprint of the original 1st ed. 1999
Pages:	625
Product dimensions:	6.10(w) x 9.25(h) x 0.39(d)

Table of Contents

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.