DBMS: File Organization, Relational Model, Algebra, Calculus, and Normalization

Comprehensive vocabulary flashcards covering physical file organization, indexing techniques, relational model concepts, relational algebra operations, relational calculus, and database normalization forms.

Physical Data Organization

The method that defines how logical data models (such as tables) are physically stored and mapped to hardware blocks on storage devices to optimize disk I/O performance, storage efficiency, and query speed.

Block (Page)

The basic unit of physical storage used by a DBMS, containing multiple records, transferred between secondary storage and main memory in a single I/O operation to reduce disk accesses.

Heap File Organization

An unordered file structure in which records are placed wherever free space is available, enabling fast insertions but slower search times due to full file scans.

Hashed File Organization

A file organization technique that uses a mathematical hash function on a key to determine record storage locations, offering fast exact-match searches but poor efficiency for range queries.

Primary Index

An ordered file of fixed-length records with two fields: the first is the primary key of the data file, and the second is a pointer to the corresponding disk block address.

Dense Index

An indexing structure in which an index record is created for every search-key value present in the database, offering fast lookups at the expense of higher storage overhead.

Sparse Index

An indexing technique where index records appear for only some search-key values, storing a block address for a range of records to minimize index space and maintenance overhead.

Clustering Index

An index created on an ordered data file ordered by a non-primary key column, where records sharing the same key value are grouped together and pointed to by the index as a cluster.

Secondary Index

A multi-level indexing structure that divides search ranges into multiple tiers, keeping first-level mapping small enough for primary memory while storing lower levels on secondary storage.

Pile File Method

A sequential file organization method operating on a first-come, first-served basis, where incoming records are automatically appended to the end of the file in the order they arrive.

Sorted File Method

A sequential file organization technique where records are maintained in sorted order by a key or attribute, inserting newly arrived records directly into their sorted position.

Tuple

The formal relational model term for a single row in a relation, representing a set of related attribute values for a specific entity.

Relational Schema

A formal description specifying the relation name and its list of attributes, denoted as $R(A_1, A_2, \dots, A_n)$.

Domain Constraints

Rules specifying that the value assigned to each attribute in a tuple must be an atomic value belonging to that attribute's defined data type and valid range.

Entity Integrity Constraint

A relational constraint stating that no attribute comprising the primary key of a relation can contain a null value.

Referential Integrity Constraint

A constraint between two tables specifying that a foreign key value in one table must match an existing primary key value in the referenced table or be null.

Candidate Key

A minimal super key capable of uniquely identifying every tuple in a relation without any redundant attributes.

Foreign Key

An attribute or set of attributes in a relation that matches the primary key of another relation to enforce referential consistency between tables.

Relational Algebra

A procedural query language that prescribes a step-by-step sequence of operations using relational operators to compute query results.

Select Operation ($\sigma$)

A unary relational algebra operation denoted by $\sigma$ that filters and retrieves a subset of tuples meeting a defined condition predicate.

Project Operation ($\pi$)

A unary relational algebra operation denoted by $\pi$ that selects specified columns from a relation, discarding all other attributes and eliminating duplicate rows.

Cartesian Product ($\times$)

A binary relational algebra operation that combines each tuple from one relation with every tuple from a second relation, creating all possible cross combinations.

Rename Operation ($\rho$)

A relational algebra operator denoted by $\rho$ used to alter the name of a resulting relation or its attributes.

Relational Calculus

A non-procedural declarative query language based on predicate logic that describes what data to retrieve without specifying the procedural steps to fetch it.

Tuple Relational Calculus (TRC)

A non-procedural calculus expressed as $\{T \mid P(T)\}$, where the filtering variable ranges over tuples of a relation that satisfy the predicate $P(T)$.

Domain Relational Calculus (DRC)

A non-procedural calculus expressed as $\{a_1, a_2, \dots, a_n \mid P(a_1, a_2, \dots, a_n)\}$, where the filtering variables range over attribute domains rather than complete tuples.

Normalization

The formal database design process of decomposing larger tables with data redundancy into smaller, well-structured relations to eliminate modification anomalies.

Insertion Anomaly

A database anomaly occurring when a user cannot insert a new tuple into a table because certain required unrelated data is unavailable.

Deletion Anomaly

A database anomaly occurring when the deletion of certain data unintentionally causes the loss of other essential, unrelated information.

Update Anomaly

A database anomaly where modifying a single data value requires updates across multiple duplicate records, risking inconsistencies if some rows are missed.

First Normal Form (1NF)

A normal form condition requiring that every column of a table holds only atomic, indivisible values, prohibiting composite or multivalued attributes.

Second Normal Form (2NF)

A normal form condition requiring a relation to be in 1NF and ensure that all non-key attributes are fully functionally dependent on the primary key, eliminating partial dependencies.

Third Normal Form (3NF)

A normal form state requiring a relation to be in 2NF with no transitive dependencies for non-prime attributes, such that for every non-trivial $X \rightarrow Y$, $X$ is a super key or $Y$ is a prime attribute.

Boyce-Codd Normal Form (BCNF)

A stricter version of 3NF where every functional dependency $X \rightarrow Y$ requires the determinant $X$ on the left-hand side to be a super key.

Fourth Normal Form (4NF)

A normal form requiring that a table is in Boyce-Codd Normal Form (BCNF) and possesses no multi-valued dependencies.

Fifth Normal Form (5NF)

A normal form requiring that a table is in 4NF and contains no join dependencies, ensuring that every valid table decomposition can be joined losslessly.