Databases

Databases

1. ER Diagrams

   • entity-relationship diagram
   • entity - described by attribute
     • primary key = underlined
   • relationship = association among 2+ entities
     • descriptive attributes - record info about relationship
     • role indicators if relationship within entity
     • key constraints
       • one-to-many = A- <> <- B, each B gets at most one A
       • many-to-many = A - <> - B
       • one-to-one = A-> <> <-B, A gets at most 1 B, B gets at most 1 A
     • Participation Constraint
       • total = thick line, B needs an A
     • Weak entity = identified uniquely with (dot underline) attributes and primary key of another "identifying owner" entity
       • 1 owner to many weak entitys
         • total participation from weak
           • cascade removal
       • thick lines around weak entity and relationship
     • ISA = triangle - overlap constraint if two subclasses contain same entity
     • aggregation - dotted square around relationship
       • relation acts like an entity

2. Functional Dependencies

   • redundancy
     • storage, inconsistent update, insert, delete
   • Decomposition = replace schema with 2+ schemas splitting data
     • if F+ = G+ then F is a cover for G and vice versa
     • Lossless-join decomposition: if pi_X(R) join pi_Y(R) = R, if X intersect Y -> X or X intersect Y -> Y, necessary to eliminate redundancy
     • Dependency-preserving decomposition: (F_x union F_y)+ = F+, enforce FD that hold just on X and just on Y, then all FDs in original must hold
     • BCNF = Boyce-Codd
       • given R and F, if X subset of R and A attribute of R, R in BCNF if forall X->A in F either A in X or X is a superkey
       • most desirable- no redundancy, but may not exist
       • let X in R, A single attribute in R, X->A violates BCNF, decompose R into R-A and XA. repeat
     • 3NF, always exists- A in X, X superkey, or A part of some key for R
       • broken by: partial dependency (X contained in key, X->A), or Transitive Dependency (X intersects key and key->X, X->A, OR A in key and key->X, X->A)
       • minimal cover: F+ = G+, RHS of each FD in G is single attribute, modify G by deleting FD or attributes from FD in G, closure changes
         • put FDs in standard form (attributes on RHS), Minimize LHS of each FD, Delete redundant FD
       • create G, min cover of F. identify set N of dependencies in F not preserved, for each FD X->A in N, create schema XA and add it to decomp of R
   • Can determine an attribute B by knowing attribute A, A->B
     • if X->Y then forall t,s in R, pi_x(t)=pi_x(s) => pi_y(t)=pi_y(s)
     • key: if forall s,t in R, pi_x(t)=pi_x(s) => pi_U(t) = pi_U(s) <=> t=s
     • implies: set of FDs F implies additional X->Y if, for any relation where FDs in F hold, X->Y also holds, use double turnstile
     • Armstrong Axioms: sound (derives => implies) and complete (implies => derives)
       • Reflexivity: if Y in X, then X -> Y
       • Augmentations: if X->Y then XZ->YZ
       • Transitivity: if X->Y and Y->Z then X->Z
     • Derives: single turnstile, start with set F and apply axioms to obtain new FD
   • Closures: F+ = set of all FDs implied by FDs in F
     • Attribute Closure: set of all attributes implied by set of attributes
       • close = X, repeat until no change{ for every U->V st U in close { close = close union V}} = O(af^2) time where a=num attribute, f = num FD in F

3. NoSQL: Not only SQL

   • key-value pairs
   • generalized Key-value DynamoDB - relies on keys for queries
   • requires thinking about queries upfront and creating indexes at the beginning
   • Column Family Model
     • map of <rowid, columnId, timestamp> -> value
     • map very sparse
     • column family = set of attributes about an instance
       • set in advance
   • document-oriented DB: mongoDB
     • like a JSON, limited join support
   • MapReduce
     • processing/programming model
     • parallel
     • iterate over record, MAP: extract info, bring together intermediate results, REDUCE: aggregate intermediate results, generate final output
     • key-value model
     • MAP: (K1,V1) -> [(K2, V2)]
     • REDUCE: (K2,[V2]) -> [(K3,V3)]
     • barrier aggregates output of (K2,V2) into one (K2, [V2])
     • need to preserve the graph structure
     • PageRank: output each neighbor with a fraction of your weight
     • account for lost mass with alpha(1\G) + (1-alpha)(m/G + p), p = current pageRank, m = lost mass, G = #nodes
     • Alternatives to MapReduce: Bulk Synchronous Parallel model BSP
       • computation in supersteps
         • each superstep has local computation, communication, and synchronization barrier
       • no key-value structure, no sort/shuffle
       • not every "unit" needs to process at each step, processors can store state between steps
       • Pregel: graph processing, pass data to neighbors, and vote to halt if there is no change
       • GraphLab: vertex's read directly their neighbor's state
       • Graph Databases: designed for queries that do not use the entire graph
         • Neo4j Graph DB, Cypher = query language, pattern match on the graph structure
           • nodes with properties and types, relationships that are directed and contain properties
             • CREATE (matrix2:Movie { title : 'The Matrix Reloaded', year : '2003-05-07' })
               • CREATE (carrieanne) - [:ACTS_IN { role : 'Trinity' }]->(matrix3)
               • MATCH (a) – [:ACTS_IN] -> (m) <- [:ACTS_IN]-(b) RETURN a.name, b.name;
             • where, order by, limit, with, etc
         • indexed on subgraphs so that you have a candidate graph that may contain the query
           • paths-query has paths, look in index for any that have same path
             • subgraph indexing
         • spatial data: points and regions
           • range, nearest-neighbor, spatial join
             • 1D B+tree not enough for index
           • R-tree: axis-aligned bound box
             • leaf = <nD box, rid>
               • index node = <nD box, ptr to child>
           • start at root, if at not-leaf, for each entry <E,ptr>, if E overlaps Q, search ptr. if leaf, for each entry <E,rid> if E overlaps Q, rid identifies object that may overlap
           • search several subtrees
           • kd-tree
             • binary space partition across median
             • alternate dimensions
             • map onto tree
             • for searching, need to prune out, but still search whole tree
               • if circle intersects root's line, check both subtrees

4. Concurrency Control and Transactions

   • fundamental database abstraction
   • ACID
     • Atomicity: execute completely or not at all, rolled back or committed
     • Durability: once transaction commits, changes persistent through crash
     • Isolation: no harmful interference between transactions, illusion that they are alone
     • Consistency: if executed by itself on consistent DB, will produce another consistent DB, system check constraints on data, otherwise from user
     • enforced by the system
       • trade-off performance and strength of guarantees
       • Recovery manager = AD
     • if can't complete, must undo changes
   • START TRANSACTION; ...; COMMIT
   • Isolation Anomalies: dirty read (read something uncommitted), unrepeatable read (R1, W2, C2, R1), Lost Update (W1 W2)
     • Final State Serializability: if produce same final DB as some serial schedule
       • View Serializable: if view equivalent to serial schedule
         • Ti reads same initial value, Ti reads same written value by T2, Ti writes same final value
         • Conflict Serializability: no cycle in conflict graph
           • conflict if 2 different transactions on same object and at least 1 is a write. first -> second
     • Serial in CS in VS in FSS
     • Recoverable: if transaction commits only after commit of all transactions it read
       • ACA - Avoid Cascading Aborts - never read uncommitted writes
       • Strict: whenever a transaction writes, no other transaction can read or write to item until T commit or abort
       • Serial in Strict in ACA in Recov
   • Protocols for enforcing properties
     • Locking Protocols
       • two-phase locking: 2PL
         • lock entire DB, locks object it needs, specifies read or write lock
         • conservative: get locks at start - no deadlock, need to know all objects, less concurrency
         • strict: hold lock till commit - no cascading aborts, less concurrency
         • plain 2PL = non-strict, non-conservative
         • cannot issue release lock followed by an acquire lock
       • check periodically for deadlock with cycles in waits-for graph
         • transactions = nodes, edge from Ti to Tj if Ti waiting for lock Tj has
           • if find deadlock, abort one of transactions
             • priority based on timestamp, kill older one
       • PHANTOM problem: T1 has locks on existing, T2 inserts new. lost isolation! eliminate with index locking, B+ locking, travel down tree, lock child, release parent
         • Lock modes for levels in hierarchy, intention locks for shared and exclusive locks
       • Optimistic Concurrency Control
         • 3 phase: read, validate, write
           • changes to local copy and then push to DB
             • Ti completes before Tj
           • Ti complete before Tj writes & WS(Ti) intersect RS(Tj) = {}
           • Ti complete read before Tj does & WS(Ti) intersect RS(Tj) = {} & WS(Ti) intersect WS(Tj) = {}
           • write phases do not overlap with commit
         • less overhead, restart transactions that fail validation
         • Multiversion Concurrency Control
           • when transaction writes, creates new version instead of overwrite.
           • when read, version visible is determined by protocol
           • Timestamp: show version writen by largest stamp less than Ti's
             • if want to write, check if some transaction bigger already read, if so, abort & restart
           • Snapshot isolation: version visible to read is last commited version as of trans. start time
             • first committer wins
             • write skew anomalies:
         • Isolation Levels:
           • Read Uncommitted: dirty reads, usually limited to read-only
           • read committed: no lost updates or dirty reads
           • repeatable read: read and write locks help until commit, phantoms can still happen
           • serializable: no phantoms, need predicate lock (on index)

5. Recovery:

   • handle buffer pool: force (push commits to disk, issue with durability), steak (put uncommitted on disk, issue with atomicity)
     • write-ahead logging: force log to disk before data page steal and before commit
   • AIRES
     • log entry has Log Sequence Number (LSN)
     • data page has pageLSN = most recent record of update to page
     • flushedLSN = max LSN on disk
     • before write page, pageLSN <= flushedLSN
     • log: prevLSN, transID, type, (pageID, length, offset, before, after)
     • transaction table: transID, status, lastLSN
     • dirty page table: pageID, recLSN (first caused page to be dirty
     • steal, no-force
     • checkpoint: keep transTable, DPT
     • commit: write commit, flush up to lastLSN, commit returns, remove from transTable, end
     • abort, undo actions by prevLSNs, write CLR with undonextLSN in log, end
     • CLR is never undone (but may be redone)
     • recover: start from checkpoint, analysis, redo, undo
       • analysis: start from end_chkpt, scan forward. end = remove from transTable, commit = change in transTable & change last LSN, update record = add to DPT and set recLSN
       • redo: start from smallest recLSN, redo unless page not in DPT, page in DPT with recLSN > LSN, pageLSN >= LSN
       • undo: in reverse order for all uncommitted transactions
   • Distributed Databases
     • scalability & availability
       • horizontal partition: break table into tuples with certain characteristics
     • vertical partition: break columns
     • Distributed joins:
       • compute & fetch as necessary
       • ship to one site and evaluate
       • semijoin - project S onto join columns, ship, then join S projection with R. reduces shipping tuples
       • Bloomjoin: avoid shipping whole projection of S. filter projection by hash to a bit vector and ship bit-vector. discard any tuples that don't have a 1 in the bit-vector
       • false positives possible
       • need all subtransaction to commit or all abort
         • detect communication failures with timeouts
         • consensus protocols: 2-phase commit (2PC)
           • every node either coordinator or subordinate
             • voting phase: coord sends prepare. each sub decides what to do and communicates yes/no to coord
               • termination phase: coord collects, if all yes -> commit, if 1+ no -> abort. Subs commit and send ack
               • assumed abort = if no commit/abort record, assume abort, don't force write
                 • if committed, proceed as normal 2PC
               • presumed commit-coord will force-write begin and commit, require ack for abort, subs fors abort records, no info = commit
               • vote with read, no need for second case, only contact non-reads
               • 2PC may cause blocking even if a portion of nodes are up, if subordinate is in uncertainty and contacts other in uncertainty
                 • 3PC avoid blocking as long as a majority of sites are up and no coord failures
                   • vote, decide (if all yes, send precommit), when get acks from majority, actually make decision to commit, terminate
                 • Paxos: distributed consensus to agree on value
                   • nodes wish to agree on value, assume we don't care which value
                   • roles: proposers and acceptors
                   • proposed values get unique sequence number, highest sequence number wins
                     • proposer: send prepare, wait for majority, if majority = yes, send back value of any proposals they have already accepted, pick highest numbered and send accept request with that number and value. if no values previously accepted, use your own. If majority reject/don't reply, abandon and restart
                       • acceptor: when prepare received, compare number to highest you've accepted already. if new one higher, reply yes with value of any proposals you already accepted. if lower, don't reply. when receive accept, accept it unless you have already sent yest to higher numbered proposal
                         • OLAP: historical collection of all relevant data for analysis purposes, management, read-only, analysis, adhoc query, low isolation, many records, C-store (column)
                         • OLTP: stores current snapshop of the business, clerical, regular business, read/write, predefined queries, transaction level, high isolation, few records needed at a time, H-store(in main memory)
                   • can create dueling proposers
               • Eventual consistency
                 • data replicated across stores: want access to be linearizable
                   • total order on operations across whole system, consistent with wall-clock ordering for non-overlapping operations, if a read is ordered after a write, the read should see the value written by that write
                 • availability: all clients must be able to access some version of the data
                 • consistency: accesses to object must be atomic/linearizable
                 • partition tolerance: need to be able to handle scenarios when parts of network go down
                 • systems choose availability over consistency, instead use eventual consistency
                 • N = replication factor, R = how many replicas checked during read, W = how many replicas must acknowledge receipt of a write
                 • if W + R > N, strong consistency. if W = N, R = 1 then fast read, if W=1, R=N then fast write
                   • W=Q, R=Q, Q=N/2+1 "Quorum"
           • uncertainty period if voted yes and lost touch
             • include logging for force-write abort of commit

Imágenes y archivos del mapa