CSS Computer Science Databases, Image Processing & Web Technologies Flashcards

24 sample cards from the Databases, Image Processing & Web Technologies deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

1. What is the closure of an attribute set X (X+)?

   X+ is the set of all attributes functionally determined by X under a given set of FDs. It is used to test whether X is a superkey (X+ = all attributes) and to verify whether an FD is implied.

2. Distinguish a partial dependency from a transitive dependency.

   A partial dependency is when a non-prime attribute depends on part of a composite candidate key (violates 2NF). A transitive dependency is when a non-prime attribute depends on another non-prime attribute (violates 3NF).

3. What is the goal of normalization, and what two problems does it reduce?

   Normalization decomposes relations to minimize redundancy and avoid update anomalies (insertion, deletion, modification anomalies) by ensuring attributes depend only on keys.

4. State the requirements for First Normal Form (1NF).

   A relation is in 1NF if all attribute values are atomic (single-valued) and there are no repeating groups, multivalued attributes, or nested relations.

5. State the rule for Second Normal Form (2NF).

   A relation is in 2NF if it is in 1NF and every non-prime attribute is fully functionally dependent on every candidate key (no partial dependency on part of a composite key).

6. State the rule for Third Normal Form (3NF).

   A relation is in 3NF if it is in 2NF and has no transitive dependency of a non-prime attribute on a candidate key; equivalently, for every FD X→A either X is a superkey or A is a prime attribute.

7. State the condition for Boyce-Codd Normal Form (BCNF).

   A relation is in BCNF if for every nontrivial functional dependency X → Y, X is a superkey. BCNF is stricter than 3NF and removes anomalies caused by overlapping candidate keys.

8. What dependency does Fourth Normal Form (4NF) address?

   4NF eliminates nontrivial multivalued dependencies (MVDs): a relation is in 4NF if it is in BCNF and for every nontrivial MVD X ↠ Y, X is a superkey.

9. What are the two desirable properties of a relational decomposition?

   Lossless-join (the natural join of the decomposed relations exactly reconstructs the original, no spurious tuples) and dependency preservation (all original FDs are enforceable on the decomposed relations without joins).

10. Differentiate a primary (clustering) index from a secondary index.

    A primary/clustering index is on the field by which the file is physically ordered (one per file). A secondary index is on a non-ordering field; there can be many, and they are typically dense.

11. What is the difference between a dense index and a sparse index?

    A dense index has one index entry for every search-key value (every record). A sparse index has entries only for some search-key values (e.g., one per data block), requiring the file to be ordered on the key.

12. What is a B+-tree and why is it preferred for database indexing?

    A B+-tree is a balanced multi-way search tree where all data pointers reside in the leaf nodes (linked sequentially) and internal nodes hold only keys. It keeps height low for fast equality and range queries and stays balanced under insertion/deletion.

13. How does hashing-based indexing differ from B+-tree indexing in access patterns?

    Hash indexes give O(1) average access for exact-match (equality) lookups but cannot efficiently support range queries; B+-trees support both equality and ordered range queries via their sorted leaf structure.

14. What are the typical phases of SQL query processing?

    Parsing and translation (SQL to relational algebra/internal form), optimization (choosing an efficient execution plan based on cost estimates), and evaluation/execution (running the chosen plan to produce results).

15. Distinguish heuristic (rule-based) optimization from cost-based optimization.

    Heuristic optimization applies transformation rules (e.g., push selections and projections down early) to improve the query tree without cost estimates. Cost-based optimization enumerates alternative plans and selects the one with the lowest estimated cost using statistics.

16. State the ACID properties of a transaction.

    Atomicity (all-or-nothing), Consistency (preserves database integrity constraints), Isolation (concurrent transactions appear serial), and Durability (committed changes survive failures).

17. Name three concurrency problems that arise without proper isolation.

    Lost update, dirty read (reading uncommitted data), and unrepeatable read / phantom read. These motivate concurrency-control mechanisms like locking and timestamping.

18. What is two-phase locking (2PL) and what does it guarantee?

    2PL is a protocol with a growing phase (only acquire locks) and a shrinking phase (only release locks); once a lock is released no new lock may be acquired. It guarantees conflict-serializable schedules; strict 2PL also avoids cascading aborts.

19. What does it mean for a schedule to be conflict-serializable, and how is it tested?

    A schedule is conflict-serializable if it can be transformed into a serial schedule by swapping non-conflicting adjacent operations. It is tested by building a precedence (serialization) graph and checking that it has no cycles.

20. Define data fragmentation in distributed databases and its main types.

    Fragmentation splits a relation across sites. Horizontal fragmentation divides by rows (subsets of tuples via selection), vertical fragmentation divides by columns (subsets of attributes via projection, keeping the key), and mixed/hybrid combines both.

21. What is the difference between replication and fragmentation transparency in distributed databases?

    Replication transparency hides that multiple copies of data exist across sites; fragmentation transparency hides that a relation is split into fragments. Both let users query the global schema as if it were a single centralized database.

22. What is the two-phase commit (2PC) protocol used for in distributed databases?

    2PC ensures atomic commitment across sites: in the prepare/voting phase the coordinator asks all participants to vote commit or abort; in the decision phase it commits only if all voted yes, otherwise aborts, ensuring all-or-nothing globally.

23. What characterizes an object-oriented database (OODBMS)?

    An OODBMS stores data as objects, integrating OOP concepts — object identity (OID), encapsulation, classes, inheritance, and complex/user-defined types — directly into the database, reducing the impedance mismatch with OO programming languages.

24. What is the impedance mismatch that object-oriented and object-relational databases aim to solve?

    It is the mismatch between the set-oriented, flat relational model and the navigational, object structures (objects, inheritance, references) of object-oriented programming languages, which forces tedious data conversion between the two.

What this deck covers

Databases, Image Processing & Web Technologies flashcards FAQ