NACCQ - Qualifications

Information and Communications
Technology Qualifications

| Back to list of Prescriptions

Prescription: FS600 (FS200)File Structures

Aim of Module	To enable students to identify appropriate physical file structures in a given application, and be able to implement these in a representative exercise.
Credits	7
Student Learning hours	70
Content Revised	1998
Prescription Expiry Date	Nov 2005

Level and Assessment Schedule
Topics	Highest Skill Level	Suggested Assessment Percentage
1 Fundamentals of File Recording	C	10
2 Fundamental File Types	C	10
3 Recording Blocking	A	5
4 Complex Direct Access	A	70
5 Multi-User Access	C	5

		100

The Student Will

1	Fundamentals of File Recording


C	1.1	Logical vs Physical Files



		Describe the concept of mapping from the logical view of the ''record'' to the Stored Record Address(es) of the element(s) and relate this to the structures and techniques noted below. [SRA after Codd et al.]



C	1.2	Management of sets of files



		Describe how each of the following is established and utilised:



		-Directories e.g. for disk volumes

		-File Allocation Tables ( FATs)

		-File Headers

2	Fundamental File Types


C	2.1	Simple Serial Files



		Explain the relevance of:



		-Contiguous data elements

		-Implementation of variable length records

		-Economy of storage

		-Requirement for sequencing ( sorting )

		-Full file re-write for update



C	2.2	Simple Relative/ Direct Access



		Explain the relevance of:



		-Requirement for fixed length

		-SRA calculation from the relative record number (RRN)

		-‘’Hit rate’’ (a measure of file activity based on the percentage of records accessed in a single processing cycle)

		-''In situ'' update of single records

3	Recording Blocking


C	3.1	Describe the justification for and the mechanisms of record blocking.



A	3.2	Given the relevant facts, correctly select an appropriate blocking factor for several different applications, eg.



		-real time

		-master file create / update

4	Complex Direct Access


		Explain and illustrate each of the following:



C	4.1	Using keys to locate records



		-Translation to SRA, Hashing algorithms, pointer lists, indexes, direct mapping

		-Collisions/synonyms



C	4.2	Concepts of overflow



C	4.3	Methods of catering for overflow



C	4.4	Indexing



	4.4.1	Relate various indexing techniques to the compromise between search efficiency and update efficiency.



		-Single-index

		-Multi-level single-key index

		-Binary balanced tree

		-Multiple indexes for a single base file



	4.4.2	Index Management



		-Static Index - re-index periodically after batch update

		-Dynamic Index - the indexes are continually revised to reflect the updates transaction by transaction.

		-Virtual Storage Index Sequential

		-Describe the working characteristics of 2 specific indexing implementations.



C	4.5	Inverted Files



		-Partially inverted files

		-Fully inverted files

		-Relationship between inverted file structures and third normal form



C	4.6	Lists (also known as Linked Lists, Pointer Lists or Chained Data sets)



	4.6.1	Single linked lists



		-Forward chained

		-Backward chained



	4.6.2	Double linked lists (both ways)



		Illustrate the use of these in the following ‘’service’’ applications.



		-‘’free space’’ management e.g. directories, FAT's

		-binary trees

		-indexing

		-sorting



C	4.7	Briefly illustrate the main technical features of file structures within a particular DBMS.



A	4.8	Demonstrate one of the complex direct access methods outlined in Section 4.

5	Multi-User Access


	C	Describe the reasons for, the problems associated with, and the main techniques involved in:



		-Record locking

		-Field Locking

		-Contention Avoidance

top