Note: small window for data loss (committed tx log records not sent)

Distributed Databases

33/95

Two kinds of distributed databases

• parallel database on a distributed architecture
  • single schema/control, data distributed over network
• independent databases on a distributed architecture
  • independent schemas/DBMSs, combined via global schema

Distribution of data complicates tx processing ...

• potential for multiple copies of data to become inconsistent
• commit or abort must occur consistently on all nodes

... Distributed Databases

34/95

Distributed tx processing handled by two-phase commit

• initiating site has transaction coordinator C_i ...
  • waits for all other sites executing tx T to "complete"
  • sends <prepare T> message to all other sites
  • waits for <ready T> response from all other sites
  • if not received (timeout), or <abort T> received, flag abort
  • if all other sites respond <ready T>, flag commit
  • write <commit T> or <abort T> to log
  • send <commit T> or <abort T> to all other sites
• non-initiating sites write log entries before responding

... Distributed Databases

35/95

Distributed query processing

• may require query ops to be executed on different nodes
  • node provides only source of some data
  • some nodes may have limited set of operations
• needs to merge data received from different nodes
  • may require data transformation (to fit schemas together)

Non-classical DBMSs

Classical DBMSs

37/95

Assumptions made in conventional DBMSs:

• data is sets of tuples; tuples are lists of atomic values
• data values can be compared precisely (via =, >, <, ...)
• filters can be described via boolean formulae
• SQL is a suitable langauage for all data management
• transaction-based consistency is critical
• data stored on disk, processed in memory
• data transferred in blocks of many tuples
• disk ↔ memory cost is most expensive in system
• disks are connected to processors via fast local bus

Modern DBMSs

38/95

Demands from modern applications

• more flexible data structuring mechanisms
• very large data objects/values (e.g. music, video)
• alternative comparisons/filters   (e.g. similarity matching)
• massive amounts of data   (too much to store "locally")
• massive number of clients   (thousands tx's per second)
• solid-state storage   (minimal data latency)
• data required globally   (network latency)

... Modern DBMSs

39/95

Some conclusions:

• relational model doesn't work for all applications
• SQL is not appropriate for all applications
• hard transactions not essential for all applications

• "for all"  is really  "for any"
• ⇒ relational DBMSs and SQL are dinosaurs
• ⇒ NoSQL is the new way

... Modern DBMSs

40/95

Some approaches:

• storage systems: Google FS, Hadoop DFS,   Amazon S3
• data structures: BigTable, HBase, Cassandra,   XML, RDF
• data structures: column-oriented DBMSs e.g. C-store
• data structures: graph databases e.g. Neo4j
• operations: multimedia similarity search e.g. Shazam
• operations: web search e.g. Google
• transactions: eventual consistency
• programming: object-relational mapping (ORM)
• programming: MapReduce
• languages: Sawzall, Pig, Hive,   SPARQL
• DB systems: CouchDB, MongoDB, F1, Cstore

Scale, Distribution, Replication

41/95

Data for modern applications is very large (TB, PB, XB)

• not feasible to store on a single machine
• not feasible to store in a single location

• each node holds moderate amount of data
• each data item is replicated on several nodes
• nodes clustered in different geographic sites

• reliability, fault-tolerance, availability
• proximity ... use data closest to client
• scope for parallel execution/evaluation

Schema-free Data Models

42/95

Many new DBMSs provide (key,value) stores

• key is a unique identifier (cf. URI)
• value is an arbitrarily complex "object"
  • e.g. a text document  (often structured, e.g. Wiki, XML)
  • e.g. a JSON object: (property,value) list
  • e.g. an RDF triple  (e.g. <John,worksFor,UNSW>)
• objects may contain keys to link to other objects

Eventual Consistency

43/95

RDBMSs use a strong transactional/consistency model

• if a tx commits, changes take effect "instantly"
• all tx's have a strong guarantee about data integrity

• e.g. doesn't matter if catalogue shows yesterday's price

• update is initiated on one node
• different nodes may have different versions of data
• after some time, updates propagate to all nodes

... Eventual Consistency

44/95

If different nodes have different versions of data

• conflicts arise, and need to be resolved (when noticed)
• need to decide which node has "the right value"

• ONE: at least one node has committed change   (weakest)
• QUORUM: at least half nodes holding data have committed
• ALL: changes propagated to all copies   (strongest)

MapReduce

45/95

MapReduce is a programming model

• suited for use on large networks of computers
• processing large amounts of data with high parallelism
• originally developed by Google; Hadoop is open-source implementation

• Map phase:
  • master node partitions work into sub-problems
  • distributes them to worker nodes (who may further distribute)
• Reduce phase:
  • master collects results of sub-problems from workers
  • combines results to produce final answer

... MapReduce

46/95

MapReduce makes use of (key,value) pairs

• key values identify parts of computation

• applied in parallel to all (key₁,val₁) pairs
• results with common key₂ are collected in group for "reduction"

• collects all values tagged with key₂
• combines them to produce result(s) val₃

... MapReduce

47/95

"Classic" MapReduce example (word frequency in set of docs):

function map(String name, String document):
  // name: document name
  // document: document contents
  for each word w in document:
    emit (w, 1)
 
function reduce(String word, Iterator partialCounts):
  // word: a word
  // partialCounts: list of aggregated partial counts
  sum = 0
  for each c in partialCounts:
    sum += c
  emit (word, sum)

... MapReduce

48/95

MapReduce as a "database language"

• some advocates of MapReduce have oversold it (replace SQL)
• DeWitt/Stonebraker criticised this
  • return to low-level model of data access
  • all done before in distributed DB research
  • misses efficiency opportunities affored by DBMSs
• concensus is emerging
  • SQL/MapReduce good for different kinds of task
  • MapReduce as a basis for SQL-like languages (e.g. Apache HiveQL)

Modern vs Classical

49/95

Some criticisms of the NoSQL approach:

• DeWitt/Stonebraker: MapReduce: A major step backwards
• Online parody of noSQL advocates  (strong language warning)

Hadoop DFS

50/95

Apache Hadoop Distributed File System

• a hierarchical file system (directories & files a la Linux)
• designed to run on large number of commodity computing nodes
• supporting very large files (TB) distributed/replicated over nodes
• providing high reliability  (failed nodes is the norm)

Optimised for write-once-read-many apps

• simplifies data coherence
• aim is maximum throughput rather than low latency

... Hadoop DFS

51/95

Architecture of one HDFS cluster:

... Hadoop DFS

52/95

Datanodes ...

• provide file read/write/append operations to clients
  • under instruction from Namenode
• periodically send reports to Namenode

• is a collection of fixed-size blocks
• blocks are distributed/replicated across nodes

• Heartbeat ... Datanode still functioning ok
• Blockreport ... list of all blocks on DataNode

... Hadoop DFS

53/95

Namenodes ...

• hold file-system meta-data (directory structure, file info)
  • e.g. file info: (filename, block#, #replicas, nodes)
  • e.g. (/data/a, 1, 2, {1,3}),  (/data/a, 2, 2, {4,5}),  (/data/a, 3, 2, {3,5})
• provides file open/close/rename operations to clients
• determine replication and mapping of data blocks to DataNodes
• select Datanodes to serve client requests for efficient access
  • e.g. node in local rack > node in other rack > remote node

Two Case Studies

54/95

Consider two variations on the DBMS theme ...

Column Stores

• still based on the relational model
• but with a variation in how data is stored
• to address a range of modern query types

• based on a graph model of data
• emphasising explicit representation of relationships
• relevant to a wide range of application domains

Column Stores

Column Stores

56/95

Column-oriented Databases (CoDbs):

• are based on the relational model
• store data column-by-column rather that row-by-row
• leading to performance gains for analytical applications

Rose to prominence via Daniel Abadi's PhD thesis (MIT, 2008)

Commercial systems have now been developed (e.g. Vertica)

... Column Stores

57/95

File structures for row-store vs column-store:

Values in individual columns are related by extra tuple id (cf. oid)

... Column Stores

58/95

Stored representation of logical (relational) tables

• each table is stored as a set of projections (slices)
• each projection consists of a different set of columns
• each column appears in at least one projection
• "rows" can be ordered differently in each projection

• projection₁: (course,student,grade) ordered by course
• projection₂: (term,student,mark) ordered by student
• projection₃: (course,student) ordered by course

Rows vs Columns

59/95

Workload for different operations

• insert requires more work in CoDbs
  • row: update one page;   column: update multiple pages
• project comes "for free" in CoDbs
  • row: extract fields from each tuple;   column: merge columns
• select may require less work in CoDbs
  • row: read whole tuples;   column: read just needed columns
• join may require less work in CoDbs
  • row: hash join;   column: scan columns for join attributes

... Rows vs Columns

60/95

Which is more efficient depends on mix of queries/updates

• RDBMSs are, to some extent, write-optimized
  • effective for OLTP applications  (e.g. ATM, POS, ...)
• when RDBMSs might be better ...
  • when query requires all attributes
  • might read more data, but less seek-time  (multiple files)
• when CoDbs might be better ...
  • smaller intermediate "tuples"
  • less competition for access to pages  (locking)

... Rows vs Columns

61/95

Storing sorted columns leads to

• potential for effective compression
  • compression ⇒ more projections in same space
  • no need to compress all columns  (if some aren't "compressible")
• sorted data is useful in some query evaluation contexts
  • e.g. terminating scan once unique match found
  • e.g. sort-merge join

Query Evaluation in CoDbs

62/95

Projection is easy if one slice contains all required attributes.

If not ...

• sequential scan of relevant slices in parallel
• combine values at each iteration to form a tuple

Assume: each column contains N values
for i in 0 .. N-1 {
   x = a[i]   // i'th value in slice containing a
   y = b[i]   // i'th value in slice containing b
   z = c[i]   // i'th value in slice containing c
   add (x,y,z) to Results
}

... Query Evaluation in CoDbs

63/95

If slices are sorted differently, more complicated

• scan based on tid values
• at each step, look up relevant entry in slice

Assume: each column contains N values
for tid in 0 .. N-1 {
   x = fetch(a,tid)  // entry with tid in slice containing a
   y = fetch(b,tid)  // entry with tid in slice containing b
   z = fetch(c,tid)  // entry with tid in slice containing c
   add (x,y,z) to Results
}

Potentially slow, depending on how fetch() works.

... Query Evaluation in CoDbs

64/95

For remaining discussion, assume

• each slice has 1 attribute, and  a[i].tid = b[i].tid = c[i].tid

... Query Evaluation in CoDbs

65/95

Consider typical multi-attribute SQL query

select a,b,c from R where b > 10 and d < 7

Query operation on individual column is done in one slice

Mark index of each matching entry in a bit-vector

Combine (AND) bit-vectors to get indexes for result entries

For each index, merge result entry columns into result tuple

Known as late materialization.

... Query Evaluation in CoDbs

66/95

Example: select a,b,c from R where b = 5

// Assume: each column contains N values
matches = all-zero bit-string of length N
for i in 0 .. N-1 {
   x = b[i]  // i'th value in b column
   if (x == 5)
       matches[i] = 1  // set bit i in matches
}
for i in 0 .. N-1 {
   if (matches[i] == 0) continue
   add (a[i], b[i], c[i]) to Results
}

Fast sequential scanning of small (compressed?) data

... Query Evaluation in CoDbs

67/95

Example: select a,b,c from R where b>10 and d<7

// Assume: each column contains N values
matches1 = all-zero bit-string of length N
matches2 = all-zero bit-string of length N
for i in 0 .. N-1 {
   if (b[i] > 10) matches1[i] = 1
   if (d[i] < 7) matches2[i] = 1
}
matches = matches1 AND matches2
for i in 0 .. N-1 {
   if (matches[i] == 0) continue
   add (a[i], b[i], c[i]) to Results
}

... Query Evaluation in CoDbs

68/95

Join on columns, set up for late materialization

Note: the left result column is always sorted

... Query Evaluation in CoDbs

69/95

Example: select R.a, S.b
                from   R join S on R.a = S.x

// Assume: N tuples in R, M tuples in S
for i in 0 .. N-1 {
   for j in 0 .. M-1 {
      if (a[i] == x[j])
         append (i,j) to IndexList
   }
}
for each (i,j) in IndexList {
   add (aR[i], bS[j]) to Results
}

... Query Evaluation in CoDbs

70/95

Aggregation generally involves a single column

• multiple aggregations could be carried out in parallel

select avg(mark), count(student) from Enrolments

Operations involving groups of columns

• may require early materialization ⇒ slower

Graph Databases

Graph Databases

72/95

Graph Databases (GDbs):

• DBMSs that use graphs as the data model

• all graphs have nodes and edges, but are they ...
• directed or undirected, labelled or unlabelled?
• what kinds of labels? what datatypes?
• one graph or multiple graphs in each database?

... Graph Databases

73/95

Typical graph modelled by a GDb

Graph Data Models

74/95

RDF  =  Resource Description Framework

• directed, labelled graphs
• nodes have identifiers  (constant values, incl. URIs)
• edges are labelled with the relationship
• can have multiple edges between nodes  (diff. labels)
• can store multiple graphs in one database
• datatypes based on W3C XML Schema datatypes

RDF is a W3C standard;  supported in many prog. languages

... Graph Data Models

75/95

RDF model of part of earlier graph:

... Graph Data Models

76/95

Property Graph

• directed, labelled graphs
• properties are (key/label, value) pairs
• nodes and edges are associated with a list of properties
• can have multiple edges between nodes  (incl same labels)

... Graph Data Models

77/95

Property Graph model of part of earlier graph:

GDb Queries

78/95

Graph data models require a graph-oriented query framework

Types of queries in GDbs

• node properties   (like SQL where clauses)
  • e.g.   is there a Person called John?   how old is John?
• adjacency queries
  • e.g. is John the parent of Jane?
• reachability queries
  • e.g. is William one of John's ancestors?
• summarization queries   (like SQL aggregates)
  • e.g. how many generations between William and John?

... GDb Queries

79/95

Graphs contain arbitrary-length paths

Need an expression mechanism for describing such paths

• path expressions are regular expressions involving edge labels
• e.g. L* is a sequence of one or more connected L edges

• SPARQL = based on the RDF model   (widely available via RDF)
• Cypher = based on the Property Graph model   (used in Neo4j)

Example Graph Queries

80/95

Example: Persons whose first name is James

SPARQL:

PREFIX p: <http://www.people.org>
SELECT ?X
WHERE { ?X p:given "James" }

Cypher:

MATCH (person:Person)
WHERE person.given="James"
RETURN person

... Example Graph Queries

81/95

Example: Persons born between 1965 and 1975

SPARQL:

PREFIX p: <http://www.people.org/>
SELECT ?X
WHERE {
 ?X p:type p:Person . ?X p:y-o-b ?A .
 FILTER (?A ≥ 1965 && ?A ≤ 1975)
 }

Cypher:

MATCH (person:Person)
WHERE person.y-o-b ≥ 1965 and person.y-o-b ≤ 1975
RETURN person

... Example Graph Queries

82/95

Example: pairs of Persons related by the "parent" relationship

SPARQL:

PREFIX p: <http://www.people.org/>
SELECT ?X ?Y
WHERE { ?X p:parent ?Y }

Cypher:

MATCH (person1:Person)-[:parent]->(person2:Person)
RETURN person1, person2

... Example Graph Queries

83/95

Example: Given names of people with a sibling called "Tom"

SPARQL:

PREFIX p: <http://www.people.org/>
SELECT ?N
WHERE { ?X p:type p:Person . ?X p:given ?N .
        ?X p:sibling ?Y . ?Y p:given "Tom"  }

Cypher:

MATCH (person:Person)-[:sibling]-(tom:Person)
WHERE tom.given="Tom"
RETURN person.given

... Example Graph Queries

84/95

Example: All of James' ancestors

SPARQL:

PREFIX p: <http://www.socialnetwork.org/>
SELECT ?Y
WHERE { ?X p:type p:Person . ?X p:given "James" .
        ?Y p:parent* ?X }

Cypher:

MATCH (ancestor:Person)-[:parent*]->(james:Person)
WHERE james.given="James"
RETURN DISTINCT ancestor

Course Review + Exam

Syllabus

86/95

View of DBMS internals from the bottom-up:

• storage subsystem (disks,pages)
• buffer manager, representation of data
• processing RA operations (sel,proj,join,...)
• combining RA operations (iterators/execution)
• query translation, optimization, execution
• transactions, concurrency, durability
• non-classical DBMSs

Exam

87/95

Tuesday 27 August, 1.45pm - 5pm, (1.45 = reading time)

Held in CSE Labs (allocations posted in Week 11).

All answers are typed and submitted on-line.

Environment is similar to Vlab.

Learn to use the shell, a text editor and on-screen calculator.

... Exam

88/95

Resources available during exam:

• exam questions   (collection of web pages)
• PostgreSQL manual   (collection of web pages)
• C programming reference   (collection of web pages)
• course notes   (HTML version from Course Notes)

No network access is available (e.g. no web, no email, ...)

... Exam

89/95

Tools available during the exam

• C compiler   (gcc, make)
• text editors   (vim, emacs, gedit, nedit, nano, ...)
• on-screen calculators   (bc, gcalctool, xcalc)
• all your favourite Linux tools   (e.g. ls, grep, ...)
• Linux manual   (man)

What's on the Exam?

90/95

Potential topics to be examined ...

• A - Course Introduction, DBMS Revision, PostgreSQL
  
• B - Storage: Devices, Files, Pages, Tuples, Buffers, Catalogs
  
• C - Cost Models, Implementing Scan, Sort, Projection
  
• D - Implementing Selection on One Attribute
  
• E - Implementing Selection on Multiple Attributes
  
• F - Similarity-based Selection (only first 15 slides)
  
• G - Implementing Join
  
• H - Query Translation, Optimisation, Execution
  
• I - Transactions, Concurrency, Recovery
  
• J - Non-classical DBMSs

... What's on the Exam?

91/95

Questions will have the following "flavours" ...

• write a small C program to do V
• describe what happens when we execute method W
• how many page accesses occur if we do X on Y
• explain the numbers in the following output
• describe the characteristics of Z

You will not have to modify PostgreSQL during the exam.

Exam Structure

92/95

There will be 8 questions

• 2 x C programming questions (40%)
• 6 x written answer questions (60%)

• exam contributes 60% of final mark
• hurdle requirement: must score > 24/60 on exam

Special Consideration

93/95

Reminder: this is a one-chance exam.

• attendance at the Exam is treated as "I am fit and well"
• subsequent claims of "I failed because I felt sick" are ignored

Special consideration requests must clearly show

• how you were personally affected
• that your ability to study/take-exam was impacted

Revision

94/95

Things you can use for revision:

• past exams
• theory exercises
• prac exercises
• course notes
• textbooks

Note: I'm away on August 18-20 inclusive (no email)

And that's all folks ...

95/95

Produced: 8 Aug 2019