Chapter 17- Database Final

Front 1

Database is usually stored in the form of

Back 1

records

Front 2

Each record consists of a collection of related data _______

Back 2

values or items

Front 3

Each data value corresponds to a particular ______ of the record

Back 3

Field

Front 4

Records usually describe

Back 4

entities and their attributes

Front 5

A collection of field names and their corresponding data types constitutes a _________ _________ definition.

Back 5

record type or record format

Front 6

What does a data type specify?

Back 6

The types of values a field can take.

Front 7

Four main categories of data types:

Back 7

numeric, string of characters, boolean, and sometimes specially coded date and time data types

Front 8

What is a BLOB?

Back 8

Binary large objects. Large unstructured objects that may represent images, digitized video, or audio streams.

Front 9

How is a BLOB data item typically stored?

Back 9

Separately from its record in a pool of disk blocks.

(Note: also includes a pointer to the BLOB in the record)

Front 10

________ is a sequence of records.

Back 10

A file

Front 11

What are fixed-length records?

Back 11

When every record in the file has exactly the same size.

Front 12

What are variable-length records?

Back 12

When different records in the file have different sizes.

Front 13

What are four reasons a file may have variable-length records?

Back 13

1. The file records are of the same type but one or more fields are of varying size.

2. Files have same record type but one or more fields have multiple values for individual records (repeating fields or repeating groups)

3. Same record type but one or more fields are optional

4. File contains different record types (mixed file) (page 595-596)

Front 14

When do we use special separator characters (ex: ?, %, $)?

Back 14

To terminate variable-length fields. Used to determine the bytes within a particular record that represent each field.

Front 15

When do we assign a short field type code (ex: an integer number) to each field?

Back 15

With optional fields. Used to record a sequence of pairs.

Front 16

When do we use record type indicators?

Back 16

For a file that includes records of different types.

Front 17

What does a repeating field need to separate?

Back 17

A separator character to separate the repeating values of the field and another to indicate termination of the field.

Front 18

What is a block?

Back 18

The unit of data transfer.

Front 19

Records of a file must be allocated to ____________.

Back 19

disk blocks.

Front 20

What is blocking factor (bfr)?

Back 20

Block size/records

(bfr=b/r)

Front 21

What does it mean when records are spanned?

Back 21

When records can span more than one block.

Front 22

How do pointers function in blocks?

Back 22

A pointer at the end of the first block points to the block containing the remainder of the record on another in case it's not the next consecutive block on disk.

Front 23

What does it mean when records are unspanned?

Back 23

When records are not allowed to cross block boundaries.

Front 24

What is contagious allocation?

Back 24

The file blocks are allocated to consecutive disk blocks.

(This makes reading the file very fast using double buffering, but makes expanding the file difficult.)

Front 25

What is linked allocation?

Back 25

Each file block contains a pointer to the next block.

(This makes it easy to expand the file but slow to read.)

Front 26

What is a combination between linked and contiguous allocation called?

Back 26

Clusters.

(Clusters are linked.)

Front 27

What is another term for a cluster?

Back 27

File segments or extents.

Front 28

What is indexed allocation?

Back 28

One or more index blocks contain pointers to the actual file blocks.

Front 29

What does a file header or file descriptor do?

Back 29

Contains information about a file needed by the system programs that access the file records. It also includes information to determine the disk address and information to record format descriptions (like field length).

Front 30

When do you need a linear search?

Back 30

If the address of the block that contains the record is not known.

Front 31

What is heap or pile file organization?

Back 31

When records are placed in the file in the order in which they are inserted.

Front 32

True or false. Inserting a new record is very efficient.

Back 32

True

Front 33

How do you insert and delete records?

Back 33

See page 602

Front 34

What is a deletion marker?

Back 34

An extra byte or bit stored with each record. A record is deleted by setting the deletion marker to a certain value.

Front 35

What is the purpose of periodic reorganization?

Back 35

Reclaim unused space of deleted records.

Front 36

What are relative or direct files?

Back 36

Can easily be accessed directly by their relative positions.

Front 37

What is the ordering field?

Back 37

The field we use to physically order the records of a file on a disk. This leads to an ordered or sequential file.

Front 38

What is a key field?

Back 38

A field guaranteed to have a unique value in each record.

Front 39

What if the ordering field is a key field?

Back 39

Then the field is the ordering key for the file.

Front 40

What are the advantages to having ordered records?

Back 40

Efficiency in reading, usually requires no additional block accesses because next record in same block as previous one, using a search condition is faster when binary search technique is used.

Front 41

What is a binary search?

Back 41

See page 603

Front 42

True or false: Inserting and deleting files are expensive operations for an ordered file because the records must remain in order.

Back 42

True

Front 43

What is an overflow or transaction file?

Back 43

A temporary unordered file.

Front 44

What is a main or master file?

Back 44

When an overflow file is added, the ordered file becomes the main or master file. New records inserted at end of overflow and then periodically the overflow will be sorted.

Front 45

Ordered files are rarely used in db applications unless an additional access path called a ______________ is used.

Back 45

primary index

Front 46

Using a primary index results in a ______________ file.

Back 46

index-sequential

Front 47

If the ordering attribute is not a key, this results in a ____________ file.

Back 47

clustered

Front 48

What is a hash file?

Back 48

Type of file organization based on hashing.

Front 49

The search condition must be an equality condition on a single field called the __________

Back 49

hash field

Front 50

Typically the hash field is also a key field of the file called the ________ ________

Back 50

hash key

Front 51

What does a hash function (or randomizing function) do?

Back 51

It is applied to the hash field value of a record and yields the address of the disk block in which the record is stored. Search can be carried out in main memory buffer.

Front 52

Hashing is typically implemented as a __________

Back 52

hash table

Front 53

What is folding?

Back 53

A hash technique that involves applying an arithmetic function to different portions of the hash field to calculate the hash address.

Front 54

What is the hash field space?

Back 54

The number of possible values a hash field can take.

Front 55

True or false: The hash field space is smaller than the address space.

Back 55

FALSE

Front 56

What is the address space?

Back 56

The number of available addresses for records

Front 57

What is a collision?

Back 57

When the hash field value of a record that is being inserted hashes to an address that already contains a different record.

Front 58

What is collision resolution?

Back 58

The process of finding another position in a collision.

Front 59

What is open addressing?

Back 59

Collision resolution strategy. Checks subsequent positions in order until an unused (empty) position is found.

Front 60

What is chaining?

Back 60

Collision resolution strategy. Various overflow locations are kept. Pointer field is added to each record location. Collision is resolved by placing the new record in an unused overflow location and setting the pointer of the occupied hash address to the address of the overflow location.

Front 61

What is multiple hashing?

Back 61

Collision resolution strategy. Applies a second hash function if the first results in a collision. If another collision results, the program uses open addressing OR a third hash function and then open addressing as necessary.

Front 62

What is the goal of a good hashing function?

Back 62

To distribute the records uniformly over the address space so to minimize collisions while not leaving many unused locations.

Front 63

What is external hashing? What is the target address space made of.

Back 63

Hashing for disk files. Buckets. Review pg 609.

Front 64

What do record pointers include?

Back 64

A block address and a relative record position within the block.

Front 65

What do order preserving hash functions do?

Back 65

They maintain records in order of hash field values.

Front 66

What is static hashing?

Back 66

Hashing with a fixed number of buckets. Major drawbacks due to fixed hash address space.

Front 67

What is dynamic hashing?

Back 67

Uses an access structure based on binary tree data structures.

Front 68

Hash access structure is built on ______ representation of the hashing function result.

Back 68

binary

Front 69

What is the global depth of a 2^d bucket addresses?

Back 69

d. Value can be increased or decreased one at a time doubling or halving the number of entries in the directory array.

Front 70

What is the difference between global and local depth.

Back 70

Local stored with each bucket and specifies the number of bits on which the bucket contents are based.

Front 71

What is a file?

Back 71

Sequence of records.