Foundations of Information Systems: Parallel Databases, Distributed Storage, and Transaction Management

Comprehensive practice flashcards covering parallel database systems, partitioning techniques, parallel joins and sorting algorithms, relational transaction management (ACID, schedules, locking), and distributed NoSQL storage models.

Data

Raw facts gathered and captured during the input phase of an information system.

Information

A collection of facts organized in such a way that they provide value beyond the facts themselves.

Process

A set of logically related tasks executed to convert input data into useful outputs.

Knowledge

The awareness and understanding of a set of information.

Competitive Advantage

A significant edge gained over competitors, achieved by using information systems to enhance supply chain efficiency, reduce costs, or improve services.

Procedures (Information Systems)

The strategies, policies, methods, and rules that govern the use and operation of a Management Information System (MIS).

Structured Data

Data conforming to a predefined data model that organizes it into a form that is relatively easy to store, process, retrieve, and manage (e.g., relational database tables).

Unstructured Data

Data lacking a predefined conceptual model, such as flat binary files containing text, audio, or video, while still potentially possessing encoding formats and metadata.

Dynamic Data

Data that changes relatively frequently, such as office documents and transactional entries in financial systems.

Static Data

Data that changes rarely or remains constant once captured, exemplified by medical imaging data from MRI or CT scans.

Vertical Scaling (Scale-Up)

Increasing system capacity by adding resources (CPU, RAM, disk) to a single machine, bounded by physical hardware limits of that single machine.

Horizontal Scaling (Scale-Out)

Increasing capacity by distributing the database across multiple machines, limited in traditional RDBMSs by the read-to-write ratio and network communication overhead.

Data Sharding (Data Striping)

Partitioning and distributing segments of data across multiple independent nodes or servers to allow concurrent and parallel data accesses.

Amdahl's Law

A formula used to determine the theoretical speedup achievable by parallelizing a computing program given the fraction of the code that can be parallelized.

BASE Properties

A database consistency model for large-scale distributed architectures characterized by Basically Available, Soft-State, and Eventual Consistency.

Document Store

A NoSQL database that stores data as semi-structured documents (BLOBs such as JSON, XML, or PDF) and typically queries via MapReduce (e.g., MongoDB, CouchDB).

Graph Database

A specialized NoSQL database that represents data using vertices and edges to optimize graph-traversal queries like shortest-path search (e.g., Neo4j, VertexDB).

Key-Value Store

A NoSQL data store where primary keys map directly to values or complex structures like lists, primarily supporting basic CRUD operations (e.g., Redis, Amazon DynamoDB).

Columnar Database

A hybrid database combining relational database features with key-value architectures to store data tables by column rather than row (e.g., HBase, Vertica).

Horizontal Partitioning

Dividing the tuples of a relation across multiple disks such that each individual tuple resides on exactly one disk, enabling parallel I/O.

Round-Robin Partitioning

A partitioning scheme distributing the $i$-th tuple inserted in a relation to disk $i \bmod n$ across $n$ disks; optimal for full sequential scans but inefficient for point and range queries.

Hash Partitioning

A partitioning technique where a hash function $h$ maps a tuple's partitioning attribute value to a disk index in the range $0$ to $n - 1$; ideal for point queries on the partitioning attribute but poor for range queries.

Range Partitioning

A partitioning strategy using a vector $[v_0, v_1, \dots, v_{n-2}]$ on a partitioning attribute to cluster contiguous attribute values onto designated disks.

Attribute-Value Skew

A distribution imbalance where specific values occur frequently in the partitioning attribute, forcing all tuples containing those values to reside on the same partition.

Partition Skew

An imbalance in range partitioning caused by an inadequately chosen partitioning vector that allocates disproportionate quantities of tuples across partitions.

Balanced Partitioning Vector

A partition boundary vector established by sorting a relation on its partitioning attribute and recording the value after every $\frac{1}{n}$-th fraction of tuples has been read.

Interquery Parallelism

The concurrent execution of distinct transactions or queries in parallel, designed to increase overall system throughput in transactions per second.

Intraquery Parallelism

The execution of an individual database query across multiple processors and disks simultaneously to decrease execution time for complex, long-running operations.

Intraoperation Parallelism

A division of intraquery parallelism where each individual relational operation (e.g., sort, join) is parallelized across multiple processors.

Interoperation Parallelism

A division of intraquery parallelism where different relational operations within a single query expression tree execute concurrently.

Range-Partitioning Sort

A parallel sort method where data is redistributed across processors using a range-partition vector, sorted locally on each processor, and concatenated without requiring an expensive global merge.

Parallel External Sort-Merge

A parallel sorting algorithm where each processor locally sorts its disk data, range-partitions the resulting sorted runs across target processors, merges the incoming streams, and concatenates the outputs.

Partitioned Join

A parallel join technique for equi-joins and natural joins in which relations $r$ and $s$ are partitioned into $n$ segments using the same attribute and hash/range function, allowing each processor to compute $r_i \bowtie s_i$ locally.

Partitioned Join Architecture

A parallel join structure where both input relations ($r$ and $s$) are split into subsets ($r_0, \dots, r_{n-1}$ and $s_0, \dots, s_{n-1}$) across processors ($P_0, \dots, P_{n-1}$) on identical join attributes.

Asymmetric Fragment-and-Replicate Join

A parallel join algorithm for non-equijoins wherein one relation is partitioned across all available processors while the other relation is fully replicated to each processor.

General Fragment-and-Replicate Join

A parallel join scheme partitioning relation $r$ into $n$ fragments and relation $s$ into $m$ fragments across an $n \times m$ grid of processors $P_{i,j}$, with each processor joining fragment $r_i$ with $s_j$.

Fragment-and-Replicate Join Architecture

Parallel join execution diagrams showing (a) asymmetric fragment and replicate where relation $s$ is broadcast to all processors, and (b) general fragment and replicate using an $n \times m$ array of processing nodes.

Transaction

The DBMS's abstract view of a user program, conceptualized as an atomic sequence of database read and write operations.

Atomicity

The ACID property ensuring that either all operations of a transaction are completed and recorded, or none of them are.

Consistency

The ACID property guaranteeing that a transaction executing on a consistent database will leave the database in a consistent state upon completion.

Isolation

The ACID property ensuring that the intermediate actions of concurrently executing transactions are hidden from one another.

Durability

The ACID property guaranteeing that the effects of committed transactions survive system failures, crashes, or media corruptions.

Serial Schedule

An execution schedule where transactions execute sequentially one after another without any interleaved operations.

Serializable Schedule

An interleaved transaction execution schedule whose final database state is identical to that produced by some non-interleaved serial execution of those transactions.

Reading Uncommitted Data (WR Conflict)

A concurrency hazard (dirty read) occurring when a transaction reads modifications made by an uncommitted transaction that subsequently aborts.

Unrepeatable Read (RW Conflict)

A concurrency conflict occurring when a transaction reads a data item, another transaction modifies or overwrites it, and the first transaction rereads the item, observing an inconsistent value.

Overwriting Uncommitted Data (WW Conflict)

A concurrency conflict (dirty write) that occurs when a transaction overwrites an object written by another transaction that has not yet committed.

Recoverable Schedule

A schedule wherein each transaction is only allowed to commit after all other transactions whose written values it has read have committed.

Strict Two-Phase Locking (Strict 2PL)

A concurrency control protocol requiring shared ($S$) locks for reads and exclusive ($X$) locks for writes, holding all acquired locks until the transaction terminates.

Deadlock

A situation where two or more transactions are permanently blocked because each holds a lock requested by another transaction in a cyclical dependency.

Phantom Phenomenon

A concurrency anomaly under row-level locking where a transaction queries a set of tuples satisfying a predicate twice and observes newly inserted or deleted rows created by another transaction.