MC0067 Database Management System (DBMS and Oracle 9i) 1.

Write about: Linear Search and Collision Chain

a) Linear Search While inserting a new record, if it is found that the location at the hash address is already occupied by a previously inserted record, search for the next free location available in the disk and store the new record at this location. A pointer from the first record at the original hash address to the new record will also be stored. During retrieval, the hash address is computed to locate the record. When it is seen that the record is not available at the hash address, the pointer from the record at that address is followed to locate the required record.

In this method, the over head incurred is the time taken for the linear search to locate the next free location while inserting a record. Collision Chain Here, the hash address location contains the head of a list of pointers linking together all records which hash to that address.

In this method, an overflow area needs to be used if the number of records mapping on to the same hash address exceeds the number of locations linked to it.

2. Write about:
Integrity Rules Relational Operators with examples for each Linear Search Collision Chain

Integrity Rules
An Integrity constraint is a rule which data in the database should follow. One integrity constraint may be that the department number for a faculty must be that of a department which actually exists. A database has integrity if data in the database satisfies all integrity constraints, which have been established.

Relational Operators
There are six Relational Operators in SQL, and after introducing them, well see how theyre used: = Equal < or != (see manual) Not Equal < Less Than

> Greater Than <= Less Than or Equal To >= Greater Than or Equal To The WHERE clause is used to specify that only certain rows of the table are displayed, based on the criteria described in that WHERE clause. It is most easily understood by looking at a couple of examples. If you wanted to see the EMPLOYEEIDNOs of those making at or over $50,000, use the following:
SELECT EMPLOYEEIDNO FROM EMPLOYEESTATISTICSTABLE WHERE SALARY >= 50000;

Notice that the >= (greater than or equal to) sign is used, as we wanted to see those who made greater than $50,000, or equal to $50,000, listed together. This displays:
EMPLOYEEIDNO 010 105 152 215 244

The WHERE description, SALARY >= 50000, is known as a condition (an operation which evaluates to True or False). The same can be done for text columns:
SELECT EMPLOYEEIDNO FROM EMPLOYEESTATISTICSTABLE WHERE POSITION = 'Manager';

This displays the ID Numbers of all Managers. Generally, with text columns, stick to equal to or not equal to, and make sure that any text that appears in the statement is surrounded by single quotes (). Note: Position is now an illegal identifier because it is now an unused, but reserved, keyword in the SQL-92 standard.

Linear Search
While inserting a new record, if it is found that the location at the hash address is already occupied by a previously inserted record, search for the next free location available in the disk and store the new record at this location. A pointer from the first record at the original hash address to the new record will also be stored. During retrieval, the hash address is computed to locate the record. When it is seen that the record is not available at the hash address, the pointer from the record at that address is followed to locate the required record.

In this method, the over head incurred is the time taken for the linear search to locate the next free location while inserting a record. Collision Chain Here, the hash address location contains the head of a list of pointers linking together all records which hash to that address.

In this method, an overflow area needs to be used if the number of records mapping on to the same hash address exceeds the number of locations linked to it.

3. Discuss the correspondences between the ER model constructs and the relational model constructs. Show how each ER model construct can be mapped to the relational model, and discuss any alternative mappings
We now describe the steps of an algorithm for ER-to-relational mapping. We will use the COMPANY database example to illustrate the mapping procedure. The COMPANY ER schema is shown again in Figure 4.1, and the corresponding COMPANY relational database schema is shown in Figure 4.2 to illustrate the mapping steps.

Figure 4.1: The er conceptual schema diagram for the company database

Figure 4.2: Result of Mapping the company ER schema into a relational database schema Step 1: Mapping of Regular Entity Types For each regular (strong) entity type E in the ER schema, create a relation R that includes all the simple attributes of E. Include only the simple component attributes of a composite attribute. Choose one of the key attributes of E as primary key for R. If the chosen key of E is composite, the set of simple attributes that form it will together form the primary key of R. If multiple keys were identified for E during the conceptual design, the information describing the attributes that form each additional key is kept in order to specify secondary (unique) keys of relation R. Knowledge about keys is also kept for indexing purposes and other types of analyses. In our example, we create the relations EMPLOYEE, DEPARTMENT, and PROJECT in to correspond to the regular entity types EMPLOYEE, DEPARTMENT, and PROJECT. The foreign key and relationship attributes, if any, are not included yet; they will be added during subsequent steps. These include the attributes SUPERENO and DNO of EMPLOYEE, MGRENO and MGRSTARTDATE of DEPARTMENT, and DNUM of PROJECT. In Our example, we choose eno, dnumber, and PNUMBER as primary keys for the relations employee, department, and PROJECT, respectively. Knowledge that DNAME of DEPARTMENT and PNAME of PROJECT are secondary keys is kept for possible use later in the design. The relations that are created from the mapping of entity types are sometimes called entity relations because each tuple (row) represents an entity instance. Step 2: Mapping of Weak Entity Types For each weak entity type W in the ER schema with owner entity type E, create a relation R and include all simple attributes (or simple components of composite attributes). In addition, include as foreign key attributes of R the primary key attribute (s) of the relation (s) that correspond to the owner entity type(s); this takes care of the identifying relationship type of W. The primary key of R is the combination of the primary key(s) of the owner(s) and the partial key of the weak entity type W, if any. If there is a weak entity type E2 whose owner is also a weak entity type E,, then E, should be mapped before E2 to determine its primary key first. In our example, we create the relation dependent in this step to correspond to the weak entity type dependent. We include the primary key ENO of the EMPLOYEE relation which corresponds to the owner entity type as a foreign key attribute of DEPENDENT; we renamed it EENO, although this is not necessary. The primary key of

the dependent relation is the combination {eeno, dependentjname} because DEPENDENT_NAME is the partial key of DEPENDENT. It is common to choose the propagate (CASCADE) option for the referential triggered action on the foreign key in the relation corresponding to the weak entity type, since a weak entity has an existence dependency on its owner entity. This can be used for both ON UPDATE and ON DELETE. Step 3: Mapping Of Binary 1:1 Relationship Types: For each binary 1:1 relationship type R in the ER schema, identify the relations S and T that correspond to the entity types participating in R. There are three possible approaches: (1) the foreign key approach, (2) the merged relationship approach, and (3) the cross-reference or relationship relation approach. Approach 1 is the most useful and should be followed unless special conditions exist, as we discuss below. 1. Foreign key approach: Choose one of the relationsS, sayand include as a foreign key in S the primary key of T. It is better to choose an entity type with total participation in R in the role of S. Include all the simple attributes (or simple components of composite attributes) of the 1:1 relationship type R as attributes of S. In our example, we map the 1:1 relationship type MANAGES from Figure 4.1 by choosing the participating entity type department to serve in the role of S, because its participation in the MANAGES relationship type is total (every department has a manager). We include the primary key of the employee relation as foreign key in the department relation and rename it MGRENO. We also include the simple attribute STARTDATE of the MANAGES relationship type in the DEPARTMENT relation and rename it mgrstartdate. Note that it is possible to include the primary key of S as a foreign key in T instead. In our example, this amounts to having a foreign key attribute, say DEPARTMENT_MANAGED in the EMPLOYEE relation, but it will have a null value for employee tuples who do not manage a department. If only 10 percent of employees manage a department, then 90 percent of the foreign keys would be null in this case. Another possibility is to have foreign keys in both relations S and T redundantly, but this incurs a penalty for consistency maintenance. 2. Merged relation option: An alternative mapping of a 1:1 relationship type is possible by merging the two entity types and the relationship into a single relation. This may be appropriate when both participations are total. 3. Cross-reference or relationship relation option: The third alternative is to set up a third relation R for the purpose of cross-referencing the primary keys of the two relations S and T representing the entity types. As we shall see, this approach is required for binary M:N relationships. The relation R is called a relationship relation, (or sometimes a lookup table), because each tuple in R represents a relationship instance that relates one tuple from S with one tuple of T. Step 4: Mapping of Binary 1:N Relationship Types For each regular binary 1:N relationship type R, identify the relation S that represents the participating entity type at the N-side of the relationship type. Include as foreign key in S the primary key of the relation T that represents the other entity type participating in R; this is done because each entity instance on the N-side is related to at most one entity instance on the I 1-side of the relationship type. Include any simple attributes (or simple components of composite attributes) I of the 1:N relationship type as attributes of S. In our example, we now map the 1:N relationship types WORKS_FOR, CONTROLS, and SUPERVISION from I Figure 6.1. For WORKS_FOR we include the primary key dnumber of the DEPARTMENT relation as foreign key in I the employee relation and call it DNO. For SUPERVISION we include the primary key of the EMPLOYEE relation as I foreign key in the EMPLOYEE relation itself because the relationship is recursive and call it SUPERENO. The I CONTROLS relationship is mapped to the foreign key attribute dnum of PROJECT, which references the primary key DNUMBER of the DEPARTMENT relation. An alternative approach we can use here is again the relationship relation (cross-reference) option as in the case of binary 1:1 relationships. We create a separate relation R whose attributes are the keys of S and T, and whose primary key is the same as the key of S. This option can be used if few tuples in S participate in the relationship to avoid excessive null values in the foreign key.

Step 5: Mapping of Binary M:N Relationship Types For each binary M:N relationship type R, create a new relation S to represent R. Include as foreign key attributes in S the primary keys of the relations that represent the participating entity types; their combination will form the primary key of S. Also include any simple attributes of the M:N relationship type (or simple components of composite attributes) as attributes of S. Notice that we cannot represent an M:N relationship type by a single foreign key attribute in one of the participating relations (as we did for 1:1 or 1:N relationship types) because of the M:N cardinality ratio; we must create a separate relationship relation S. In our example, we map the M:N relationship type WORKS_ON from Figure 4.1 by creating the relation WORKS_ON. We include the primary keys of the PROJECT and EMPLOYEE relations as foreign keys in WORKSJDN and rename them PNO and EENO, respectively. We also include an attribute HOURS in WORKS_ON to represent the HOURS attribute of the relationship type. The primary key of the WORKS_ON relation is the combination of the foreign key attributes {EENO, PNO}. The propagate (CASCADE) option for the referential triggered action should be specified on the foreign keys in the relation corresponding to the relationship R, since each relationship instance has an existence dependency on each of the entities it relates. This can be used for both ON UPDATE and ON DELETE. Notice that we can always map 1:1 or 1:N relationships in a manner similar to M:N relationships by using the cross-reference (relationship relation) approach, as we discussed earlier. This alternative is particularly useful when few relationship instances exist, in order to avoid null values in foreign keys. In this case, the primary key of the relationship relation will be only one of the foreign keys that reference the participating entity relations. For a 1 :N relationship, the primary key of the relationship relation will be the foreign key that references the entity relation on the N-side. For a 1:1 relationship, either foreign key can be used as the primary key of the relationship relation as long as no null entries are present in that relation. Step 6: Mapping of Multivalued Attributes: For each multivalued attribute A, create a new relation R. This relation R will include an attribute corresponding to A, plus the primary key attribute K-as a foreign key in R-of the relation that represents the entity type or relationship type that has A as an attribute. The primary key of R is the combination of A and K. If the multivalued attribute is composite, we include its simple components. In our example, we create a relation DEPT_LOCATIONS. The attribute DLOCATION represents the multivalued attribute LOCATIONS of DEPARTMENT, while dnumber-as foreign key-represents the primary key of the DEPARTMENT relation. The primary key of DEPT_LOCATIONS is the combination of {dnumber, DLOCATION}. A separate tuple will exist in dept_L0CATI0NS for each location that a department has. The propagate (CASCADE) option for the referential triggered action should be specified on the foreign key in the relation R corresponding to the multivalued attribute for both ON UPDATE and ON DELETE. We should also note that the key of R when mapping a composite, multivalued attribute requires some analysis of the meaning of the component attributes. In some cases when a multivalued attribute is composite, only some of the component attributes are required to be part of the key of R; these attributes are similar to a partial key of a weak entity type that corresponds to the multivalued attribute. Step 7: Mapping of N-ary Relationship Types: For each n-ary relationship type R, where n > 2, create a new relation S to represent R. Include as foreign key attributes in S the primary keys of the relations that represent the participating entity types. Also include any simple attributes of the n-ary relationship type (or simple components of composite attributes) as attributes of S. The primary key of S is usually a combination of all the foreign keys that reference the relations representing the participating entity types. However, if the cardinality constraints on any of the entity types E participating in R is 1, then the primary key of S should not include the foreign key attribute that references the relation Ecorresponding to E.

4. Define the following terms: disk, disk pack, track, block, cylinder, sector, interblock gap,
read/write head.

Disk:
A round plate on which data can be encoded. There are two basic types of disks: magnetic disks and optical disks. On magnetic disks, data is encoded as microscopic magnetized needles on the disk's surface. You can record and erase data on a magnetic disk any number of times, just as you can with a cassette tape. Magnetic disks come in a number of different forms: Floppy Disk, Hard Disk, Removable USB Optical disks record data by burning microscopic holes in the surface of the disk with a laser. To read the disk, another laser beam shines on the disk and detects the holes by changes in the reflection pattern. Optical disks come in three basic forms: CD-ROM, WORM, and Erasable Optical
Disk Pack :

An early removable hard disk module used in minicomputers and mainframes that contained two or more platters housed in a dust-free container. For mounting, the protective bottom of the unit was removed, and the disk pack was placed into the drive. Then the top part of the disk pack was unscrewed and removed. Disk Packs
Disk drives used to be huge washing machine-like devices. These were the kinds of removable disk modules that were used in them. The Actual Devices Taken in the 1970s, this picture shows the disk pack being loaded into the drive. Such disks held only a couple of hundred megabytes. (Image courtesy of Unisys Corporation.) Track:

A ring on a disk where data can be written. A typical floppy disk has 80 (double-density) or 160 (high-density) tracks. For hard disks, each platter is divided into tracks, and a single track location that cuts through all platters (and both sides of each platter) is called a cylinder. Hard disks have many thousands of cylinders. Each track is further divided into a number of sectors. The operating system and disk drive remember where information is stored by noting its track and sector numbers. The density of tracks (how close together they are) is measured in terms of tracks per inch (TPI).

Block:
In data management, a block is a group of records on a storage device. Blocks are manipulated as units. For example, disk drives often read and write data in 512-byte blocks

Cylinder:
A single track location on all the platters making up a hard disk. For example, if a hard disk has four platters, each with 600 tracks, then there will be 600 cylinders, and each cylinder will consist of 8 tracks (assuming that each platter has tracks on both sides).

Sector

The smallest unit that can be accessed on a disk. When a disk undergoes a low-level format, it is divided into tracks and sectors. The tracks are concentric circles around the disk and the sectors are segments within each circle. For example, a formatted disk might have 40 tracks, with each track divided into 10 sectors. The operating system and disk drive keep tabs on where information is stored on the disk by noting its track and sector number. Modern hard disk drives use a technique called zoned-bit recording in which tracks on the outside of the disk contain more sectors than those on the inside. A sector that cannot be used due to a physical flaw on the disk is called a bad sector.

Interblock Gap
The empty space generated between blocks of data on early magnetic tapes, which was created by the starting and stopping of the reel. Today's drives do not use erase heads and write the entire tape, filling stop and start areas with padded blocks or special frequencies for synchronization.

Interrecord Gaps In the old days, the gaps between the records were often larger than the blocks of data. Read/Write Head
Disk read/write heads are the small parts of a disk drive, that move above the disk platter and transform platter's magnetic field into electrical current (read the disk) or vice versa transform electrical current into magnetic field (write the disk).[1] The heads have gone through a number of changes over the years. Description In a hard drive, the heads 'fly' above the disk surface with clearance of as little as 3 nanometres. The "flying height" is constantly decreasing to enable higher areal density. The flying height of the head is controlled by the design of an air-bearing etched onto the disk-facing surface of the slider. The role of the air bearing is to maintain the flying height constant as the head moves over the surface of the disk. If the head hits the disk's surface, a catastrophic head crash can result.