List of Figures
1.1Database management system and interacting components
2.1An algebra tree (left) and its optimization (right)
3.1Example for semantic overloading
4.1A social network as a graph
4.2Geographical data as a graph
4.3A property graph for a social network
4.4Violation of uniqueness of edge labels
4.8A hypergraph with generalized hyperedge “Citizens”
5.3XML tree with preorder numbering
5.4Pre/post numbering and pre/post plane
5.7Chained memory pages with text extraction
5.8B-tree structure for node IDs in pages
5.9Page split due to node insertion
5.10Conflicting accesses in an XML tree
6.2A map-reduce-combine example
7.1Finite state machine for record assembly
8.1Writing to memory tables and data files
8.2Reading from memory tables and data files
8.4Multilevel index in data files
8.8Bloom filter for a data file
8.9A Bloom filter of length m = 16 with three hash functions
8.10A partitioned Bloom filter with k = 4 and partition length m0 = 4
9.1Generalization (left) versus abstraction (right)
9.8Resident Object Table (grey: resident, white: non-resident)
9.9Edge Marking (grey: resident, white: non-resident)
9.10Node Marking (grey: resident, white: non-resident)
10.1A hash tree for four messages
11.1XML fragmentation with shadow nodes
11.2Graph partitioning with shadow nodes and shadow edges
11.3Data allocation with consistent hashing
11.4Server removal with consistent hashing
11.5Server addition with consistent hashing
12.2Master-slave replication with multiple records
12.4Failure and recovery of a server
12.5Failure and recovery of two servers
12.6Two-phase commit: commit case
12.7Two-phase commit: abort case
12.8A basic Paxos run without failures
12.9A basic Paxos run with a failing leader
12.10A basic Paxos run with a dueling proposers
12.11A basic Paxos run with a minority of failing acceptors
12.12A basic Paxos run with a majority of failing acceptors
12.13Lamport clock with two processes
12.14Lamport clock with three processes
12.15Lamport clock totally ordered by process identifiers
12.16Lamport clock with independent events
12.18Vector clock with independent events
12.19Version vector synchronization with union merge
12.20Version vector synchronization with siblings
12.21Version vector with replica IDs and stale context
12.22Version vector with replica IDs and concurrent write
13.1Interfering operations at three replicas
13.2Serial execution at three replicas
13.3Read-one write-all quorum (left) and majority quorum (right)