Preparation for Second Test, 15-4-99

• Logical File Formats
  • Single level, two level, and multi level indexes and I-nodes.
  • Calculating maximum supported file sizes
  • Calculating expected file access times for random and sequential modes.
• Creating and Using Indexes
  • ISAM (a linear index)
    • How it works; the binary chop access method, etc.
    • Speed of access using an index
    • How to create an index, and how long creation would take:
      • by quadratic sorting methods: Bubble, Selection, Insertion
      • by "nlogn" sorting methods: quicksort, mergesort
    • Time taken to maintain an index after insertions/deletions
  • Hash Indexes
    • Principles of operation, hash function, buckets, overflow, etc.
    • Speed of access using an index
    • How to create an index and how long creation would take
    • Time taken to maintain an index after insertions/deletions
  • B-Trees
    • Principles of operation, search methods, splitting full nodes, etc.
    • Speed of access using an index
    • How to create an index and how long creation would take
    • Time taken to maintain an index after insertions/deletions
  • Why can only some indexing methods take advantage of multiple-record disc reads?
• Entity Relationship model and the Philosophy of Relational Databases
  • Components: Entity, Relationship, Attribute
  • Importance of primary keys and connection with indexes; weak entities
  • Duality/Interchangability of Tables and Relations
  • ER diagrams: understanding and creating
• Data Compression
  • Huffman Coding: the idea behind it; how to do it.
• Relational Algebra and Query Optimisation
  • Basic operations Select (sigma), Project (pi), Join (butterfly)
    • What they mean, how they are used
    • Composition rules (e.g. sigma_A(sigma_B(T))=sigma_A-and-B(T))
  • The Canonical Query Tree
    • Using relational algebra rules to move pi and sigma up the tree
    • Estimating time to answer query before and after optimisation
    • The need to try all possible join orders for the tables