CSCI 558 Exam 1 Terms

Entity-Relationship model

A graph-based model of data that achieves high data independence, preserves semantics, and can be understood naturally

Network Model

Most natural view of data. Not very capable of data independence

Relational Model

Based on relational theory. Data independent. Loses semantic information

Entity Set model

Based on set theory. Data independent. Unnatural view of data

4 Views of data

1 - Conceptual manager
2 - Information structure
3 - Access path independent
4 - Access path dependent

Entity

A “thing” which can be distinctly identified (e.g. a specific person, company, or event)

Relationship

An association among entities (e.g. father-son)

Role

The “function” of an entity in a relationship (e.g. husband, wife)

Attribute

• A function that maps from an entity or relationship set to a value set

• a Cartesian product of a value set

Shared-nothing architecture

Distributed computing setup where every node has its own CPU, memory, and storage, and nodes do not share any physical resources.

Gamma

A parallel relational database system that uses SQL

Horizontal partitioning / Declustering

• Dividing a database into multiple smaller tables by a certain partitioning attribute or hash

  • Enables large relations to be processed by multiple processors concurrently

OCC

• Optimistic concurrency control

• Lilelihood of accessing same data across parallel processes is low

MVCC

• Multi-version concurrency control

• 
  

3 Key ideas of Gamma

• Horizontally partitioned

• Parallel algorithms based on hashing to implement relational operators

• Dataflow scheduling techniques

FoundationDB

A database structure developed by Apple that decouples read and write paths and uses strict serializability to allow the access and modification of files across devices and users while handling commit conflicts.

3 Main principles of FoundationDB

• Divide and conquer - Decouples read and write paths to scale independently

• Failure is a common case - handle failure using recovery path. Minimizes mean time to recovery

• Simulation testing - randomized, deterministic simulation

Hybrid Range Partitinoing

A modification of range partitioning which divides a database table into smaller partitions distributed across nodes based on a specified range of values. These partitions are then split into fragments within the node that can be searched using parallel operations.

Range Partitioning

divides a database table into smaller partitions distributed across nodes based on specified ranges of values

M

• Desired degree of parallelism for a query

• Calculated using CPU processing time, Disk processing time, Network processing time, and additional processor overhead

BG Benchmark

A way to compare and contrast the performance and accuracy of different data stores across social networking platforms (Based on facebook)

SoAR

• Social Action Rating

  • Highest number of completed actions per second satisfying SLA requirement

Socialites

Highest number of simultaneous threads that satisfy an SLA requirement

SLA Requirement

>= X percentage of requests to observe a response time <= to Y with the amount of unpredictable data < Z for some duration T.

ACID properties

Atomicity, Consistency, Isolation, and Durability

BASE properties

Basically Available, Soft state, and Eventually consistent

CAP Theorem

A multi node system may provide two out of three of the following guarantees

• Consistency

• Availability

• Partition tolerance

Unpredictable data

Stale, inconsistent, or simply invalid data produced by a data store