Contents

Preface

Overview

List of Figures

List of Tables

Part I: Introduction

1Background

1.1Database Properties

1.2Database Components

1.3Database Design

1.3.1Entity-Relationship Model

1.3.2Unified Modeling Language

1.4Bibliographic Notes

2Relational Database Management Systems

2.1Relational Data Model

2.1.1Database and Relation Schemas

2.1.2Mapping ER Models to Schemas

2.2Normalization

2.3Referential Integrity

2.4Relational Query Languages

2.5Concurrency Management

2.5.1Transactions

2.5.2Concurrency Control

2.6Bibliographic Notes

Part II: NOSQL And Non-Relational Databases

3New Requirements, “Not only SQL” and the Cloud

3.1Weaknesses of the Relational Data Model

3.1.1Inadequate Representation of Data

3.1.2Semantic Overloading

3.1.3Weak Support for Recursion

3.1.4Homogeneity

3.2Weaknesses of RDBMSs

3.3New Data Management Challenges

3.4Bibliographic Notes

4Graph Databases

4.1Graphs and Graph Structures

4.1.1A Glimpse on Graph Theory

4.1.2Graph Traversal and Graph Problems

4.2Graph Data Structures

4.2.1Edge List

4.2.2Adjacency Matrix

4.2.3Incidence Matrix

4.2.4Adjacency List

4.2.5Incidence List

4.3The Property Graph Model

4.4Storing Property Graphs in Relational Tables

4.5Advanced Graph Models

4.6Implementations and Systems

4.6.1Apache TinkerPop

4.6.2Neo4J

4.6.3HyperGraphDB

4.7Bibliographic Notes

5XML Databases

5.1XML Background

5.1.1XML Documents

5.1.2Document Type Definition (DTD)

5.1.3XML Schema Definition (XSD)

5.1.4XML Parsers

5.1.5Tree Model of XML Documents

5.1.6Numbering Schemes

5.2XML Query Languages

5.2.1XPath

5.2.2XQuery

5.2.3XSLT

5.3Storing XML in Relational Databases

5.3.1SQL/XML

5.3.2Schema-Based Mapping

5.3.3Schemaless Mapping

5.4Native XML Storage

5.4.1XML Indexes

5.4.2Storage Management

5.4.3XML Concurrency Control

5.5Implementations and Systems

5.5.1eXistDB

5.5.2BaseX

5.6Bibliographic Notes

6Key-value Stores and Document Databases

6.1Key-Value Storage

6.1.1Map-Reduce

6.2Document Databases

6.2.1Java Script Object Notation

6.2.2JSON Schema

6.2.3Representational State Transfer

6.3Implementations and Systems

6.3.1Apache Hadoop MapReduce

6.3.2Apache Pig

6.3.3Apache Hive

6.3.4Apache Sqoop

6.3.5Riak

6.3.6Redis

6.3.7MongoDB

6.3.8CouchDB

6.3.9Couchbase

6.4Bibliographic Notes

7Column Stores

7.1Column-Wise Storage

7.1.1Column Compression

7.1.2Null Suppression

7.2Column striping

7.3Implementations and Systems

7.3.1MonetDB

7.3.2Apache Parquet

7.4Bibliographic Notes

8Extensible Record Stores

8.1Logical Data Model

8.2Physical storage

8.2.1Memtables and immutable sorted data files

8.2.2File format

8.2.3Redo logging

8.2.4Compaction

8.2.5Bloom filters

8.3Implementations and Systems

8.3.1Apache Cassandra

8.3.2Apache HBase

8.3.3Hypertable

8.3.4Apache Accumulo

8.4Bibliographic Notes

9Object Databases

9.1Object Orientation

9.1.1Object Identifiers

9.1.2Normalization for Objects

9.1.3Referential Integrity for Objects

9.1.4Object-Oriented Standards and Persistence Patterns

9.2Object-Relational Mapping

9.2.1Mapping Collection Attributes to Relations

9.2.2Mapping Reference Attributes to Relations

9.2.3Mapping Class Hierarchies to Relations

9.2.4Two-Level Storage

9.3Object Mapping APIs

9.3.1Java Persistence API (JPA)

9.3.2Apache Java Data Objects (JDO)

9.4Object-Relational Databases

9.5Object Databases

9.5.1Object Persistence

9.5.2Single-Level Storage

9.5.3Reference Management

9.5.4Pointer Swizzling

9.6Implementations and Systems

9.6.1DataNucleus

9.6.2ZooDB

9.7Bibliographic Notes

Part III: Distributed Data Management

10Distributed Database Systems

10.1Scaling horizontally

10.2Distribution Transparency

10.3Failures in Distributed Systems

10.4Epidemic Protocols and Gossip Communication

10.4.1Hash Trees

10.4.2Death Certificates

10.5Bibliographic Notes

11Data Fragmentation

11.1Properties and Types of Fragmentation

11.2Fragmentation Approaches

11.2.1Fragmentation for Relational Tables

11.2.2XML Fragmentation

11.2.3Graph Partitioning

11.2.4Sharding for Key-Based Stores

11.2.5Object Fragmentation

11.3Data Allocation

11.3.1Cost-based allocation

11.3.2Consistent Hashing

11.4Bibliographic Notes

12Replication And Synchronization

12.1Replication Models

12.1.1Master-Slave Replication

12.1.2Multi-Master Replication

12.1.3Replication Factor and the Data Replication Problem

12.1.4Hinted Handoff and Read Repair

12.2Distributed Concurrency Control

12.2.1Two-Phase Commit

12.2.2Paxos Algorithm

12.2.3Multiversion Concurrency Control

12.3Ordering of Events and Vector Clocks

12.3.1Scalar Clocks

12.3.2Concurrency and Clock Properties

12.3.3Vector Clocks

12.3.4Version Vectors

12.3.5Optimizations of Vector Clocks

12.4Bibliographic Notes

13Consistency

13.1Strong Consistency

13.1.1Write and Read Quorums

13.1.2Snapshot Isolation

13.2Weak Consistency

13.2.1Data-Centric Consistency Models

13.2.2Client-Centric Consistency Models

13.3Consistency Trade-offs

13.4Bibliographic Notes

Part IV: Conclusion

14Further Database Technologies

14.1Linked Data and RDF Data Management

14.2Data Stream Management

14.3Array Databases

14.4Geographic Information Systems

14.5In-Memory Databases

14.6NewSQL Databases

14.7Bibliographic Notes

15Concluding Remarks

15.1Database Reengineering

15.2Database Requirements

15.3Polyglot Database Architectures

15.3.1Polyglot Persistence

15.3.2Lambda Architecture

15.3.3Multi-Model Databases

15.4Implementations and Systems

15.4.1Apache Drill

15.4.2Apache Druid

15.4.3OrientDB

15.4.4ArangoDB

15.5Bibliographic Notes

Bibliography

Index