#cs145

Pregel

Batch algorithms on large scale graphs: PageRank, single source shortest paths, connected components. 

Data model is a directed graph. 

Each vertex has a value and an active/inactive flag. Edges may also have values.

Computing over these graphs consists of iterations. 

On each iteration, each vertex reads messages from the previous iteration and updates its value and active/inactive state, and sends messages via Vertex.compute(). 

Adjacency Matrix: Given graph (V,E), we define A in {0,1} in the space of |V|x|V| such that A(u,v) = 1 iff (u,v) in E. 

A graph is a binary relation. 

Join(R,S,T) = {(a,b,c):(a,b) in R, (a,c) in S, (b,c) in T}

Join(R,S,T) = Join(Join(R,S),T)

System R searches through pairwise joins. 

Data: R(A,B), S(A,C), and T(B,C). Let Q be Join(R,S,T) = "R-S-T Triangles". If R,S,T contain <= N tuples, how big can |Q| be? 

We can find it in O(N^1.5). 

We call a node heavy if it has more than N^0.5 neighbors. Let H be the set of heavy nodes. If v is in H, check whether each edge e in E forms a triangle with v. At most 2N |H| probes. We claim since |H| <= 2N^0.5, then total time is O(N^1.5). 

Pairwise joins are suboptimal. 

We care about graphs because

Sparse / irregular data

new programming model

marketing people

Reading

SQL is not turing complete--> no unbounded computation. 

SQL WITH Statement (Postgres)

WITH recursive R1 as (query 1) // can reference R1

R2 as (query 2)

...

Rn as (query n)

<query involving R1, ..., Rn>

Recursion Template

WITH Recursive

R as (base query UNION recursive query) 

NOSQL = "Not only SQL"

Examples include:

Map reduce for OLAP

Key Value stores for OLTP --> column stores

Document stores

Graph databases

Map Reduce

Originally Hadoop from Google

Data is stored in files (GFS/HGFS) without a data model. 

User provides implementations for these functions: map, reduce, reader, writer, combine. 

System provides fault tolerance, scalability, and basically maps and reduces stuff. 

Map: divides problem into smaller problems. 

Reduce: solve sub problems and combine result. 

Pig: imperative with relational operators

Hive: schemas, a language like SQL

Both compile to hadoop jobs. 

Dryad: can specify a hadoop workflow. 

Key Value Stores

Data model: key-value

Operations: insert, fetch, update, delete. 

Records distributed to nodes based on key

Replication

Single-record transactions, "eventual consistency"

Document Store

Data model: key-document

JSON, XML, other semi-structured forms.

Operations: insert, fetch, update, delete. 

Graph Databases

Nodes have ID + attributes

Data Cube: dimension data forms are the axes of the cube. The fact data (dependent data) form the cells. Aggregated data is on the sides, acting as edges and corners. 

Data Warehousing: refers to combining data from multiple OLTP sources into one warehouse for OLAP analysis.

Fact tables: often very large, append only, frequently updated.  

Three basic operations: 

Consolidation (roll-up) : sales offices rolled up to sales department

Drill-down: navigating through details

Slicing and dicing: take out specific set of data and view from different viewpoints. 

Use multidimensional data model. 

OLAP Cube (also hypercube): consists of numeric facts called measures categorized by dimensions. Measures are placed at intersections of the hypercube spanned by the dimensions as a vector space. Manipulated by matrix interface (pivot tables). 

Star Schema consists of one+ fact tables referencing any number of dimension tables. 

Fact Tables record measurements / metrics for a specific event. They generally consist of numeric values and foreign keys to dimensional data where descriptive information goes. 

Transaction fact tables record facts about a specific event

Snapshot fact tables record facts at a given point in time

Accumulating snapshot tables record aggregate facts at a given point in time

Fact tables have surrogate keys to indentify each row. 

Dimension Tables have few records but many attributes per record. Examples are: time dimension tables, geography dimension tables, product dimension tables, employee dimension tables, range dimension tables. 

Dimension tables have surrogate primary keys.  

You can reference a view like a regular table. 

Modifications to views are rewritten to modify the base tables. There are two approaches to rewriting: 

We can have the rewriting process specified explicitly by the view creator

Restrict views / modifications so that translation to base table modifications is meaningful and unambiguous.