MC 0067 01
Database Management
1) Write about . Linear Search
. Collision Chain
With respect to Hashing echni!ues.
Hashing is a method used for making retrievals faster. This method provides direct
access to record on basis of the value of a specific field called the hash _ field.
When a new record is inserted here, it is physically stored at an address which is
computed by applying amathematical function (hash function) to the value of the
hash field. Therefore, for every new record, hash _ address f (Hash _ field),
where f is the hash function. when a record is to be retrieved later, the same hash
function is ised to compute the address where the record is stored. !etrievals are
faster since a direct access is provided and there is no search involved in the
process., "s hashing relates the field value to the address of the record, multiple
hash fields will map a record to multiple addresses at the same time. Hence there
can be only one has field per file.
There are two methods to resolve a collision. They are as follows#
a. Linear Search
While inserting a new record, if it is fouind that the location at the has address is
already occupied by a previously inserted record. search for the ne$t free location
available in the disk and store the new record at the location. "pointer from the
first record at the original hash address to the new record will also be stored.
%uring 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 re'uired record. (n this method the overhead
incurred is the time taken for the linear search to locate the ne$t free location
while inserting a record.
b. Collision Chain
(n this method, the has address location contains the head of a list of pointers
linking together all records which hash to that address. Here, an overflow area
needs to be used if the number of records mapping on to the same hash address
e$ceeds the number of locations lined to it.
") Write about#
hree Le$el %rchitecture o& a 'atabase
Ser$ices o& a Database S(stem
a) hree Le$el %rchitecture o& a 'atabase#
" commonly used view of data approach is the there)level architecture suggested
by "*+(,+-"!.. (t produced an interim report in &/01 followed by a final report
in &/00. the reports proposed an architectural framework for databases. 2nder
this approach, a database is considered as containing data about an enterprise. The
three levels of the architecture are 3 different views of the data are as follows)
4$ternal 5 individual user view
.onceptual 5 community user view
(nternal physical or storage view
The three level database architecture allows a clear separation of the information
meaning i.e., conceptual view from the e$ternal data representation and from the
1
physical data structure layout." database system that is able to separate the three
different views of data is likely to be fle$ible and adaptable.
The e$ternal level is the view that the individual user of the database has. This
view is often a restricted view of the database and the same database may provide
a number of different views for different classes of users. (n general. the end users
and even the applications programmers are only interested in a subset of the
database.
The conceptual view is the information model of the enterprise and contains the
view of the whole enterprise without any concern for the physical implementation.
This view is normally more stable than the other two views. (n a database, it may
be desirable to change the internal view to improve performance while there has
been no change in the conceptual view of the database. The conceptual view is the
overall community view of the database and it includes all the information that is
going to be represented in the database. The conceptual view is defined by the
conceptual scheme which includes definitions of each of the various types of data.
The internal view is the view about the actual physical storage of data. (t tells us
what data is stored in the database and how. 4fficiency considerations are the most
important at this level and the data structures are chosen to provide an efficient
database. The internal view doesnot deal with the physical devices directly, but it
views a physical device as a collection of physical pages and allocates space in
terms of logical pages.
The separation of the conceptual view from the internal view enables us to provide
a logical description of the database without the need to specify physical
structures. This is often called -hysical %ata (ndependence. +eperating the
e$ternal views from the conceptual view enables us to change the conceptual view
3
without affecting the e$ternal views. This separation is called 6ogical %ata
(ndependence.
b) Ser$ices o& a Database s(stem#
"ny full scale %78+ provides the following services#)
&. %ata storage, !etrieval and 2pdate
" %78+ must furnish users with the ability to store, retrieve and update data in
the database.
1. " user "ccessible catalog
" %78+ must furnish a catalog in which descriptions of data items are stored
which is accessible to users.
3. Transaction support.
" %78+ must furnish a mechanism, which will ensure that either all the updates
corresponding to a given transaction are made, or that none of them is made.
9. .oncurrency control services.
" %78+ must furnish a mechanism to ensure that the database is updated
correctly when multiple users are updating the database at the same time.
:. !ecovery +ervices.
" %78+ must furnish a mechanism for recovering the database if the database is
damaged in any way.
;. "uthori<ation +ervices.
" %78+ must furnish a mechanism to ensure that only authori<ed users can have
access to the database.
0. +upport for data communication.
" %78+ must be able to integrate with communication software.
=. (ntegrity +ervices.
" %78+ must furnish a mechanism to ensure that both the data in the database
and changes to the data follow certain rules.
9
/. +ervices to -romote %ata (ndependence.
" %78+ must include facilities to support the independence of programs from the
actual structure of the database.
&>. 2tility services.
" %78+ should provide a set of utility services.
)) Compare an' Contrast the Centrali*e' an' Client + Ser$er %rchitecture
&or D,MS.
Centrali*e' D,MSs %rchitecture#
"rchitecture for %78+s have followed trends similar to those for general
computer system architectures. (n earlier days architecture used mainframe computers
to provide the main processing for all functions of the system, including user application
programs and user interface programs, as well as all the %78+ functionality. Here,
most users accessed such systems via computer terminals that did not have processing
power and only provided display capabilities. and because of this, all the processing was
performed remotely on the computer system, and only display information and controls
were sent from the system to the display terminals, which were connected to the central
computer via various types of communications networks. *ow a days as the prices of
hardware are slashed, most users replaced their terminals with -.s and workstations. "t
first, the database systems used these computers in the same way as they had used
display terminals, so that the functionality, application program e$ecution, and user
interface processing were carried out on one machine. ?radually, the %78+ systems
started to e$ploit the available processing power at the user side, which gave way to
client,server %78+ architecture.
:
Client+Ser$er %rchitecture o& D,MS#
The client,server architecture was developed to deal with
computing environments in which a large number of -.s, workstations, file servers,
printers, database servers, Web servers, and other e'uipment are connected via a
network. the idea is to define speciali<ed servers with specific functionalities. @or e$, a
number of -cs or small workstations as clients can be connected to a @ile server that
maintains the files of the client machines. "nd like wise, printer server is where, all the
printer are connected. Web servers or e)mail servers also fall into the speciali<ed server
category. The client machines provides the user with the appropriate interfaces to utili<e
these servers, as well as with local processing power to run local applications. This
concept can be dealt with a speciali<ed software, like a %78+ or a ."% (computer
aided design) package being stored on specific server machines and being made
accessible to multiple clients.
This concept of client,server architecture assumes an underlying framework that consists
of many -.s and workstations as well as a smaller number of mainframe machines
connected via local area networks and other types of computer networks. " client in this
framework is typically a user machine that provides user interface capabilities and local
processing. When a client re'uires access to additional functionality)such as a database
access)that does not e$ist at that machine, it connects to a server that provides the
needed functionality. " +erver is a machine that can provide services to the client
machines, such as, file access, printing, archiving, or database access. (n general, some
machines install only client software, some others only server software and still others
both client and server software. (t is more common that client and server software
usually run on separate machines.
;
7) -llustrate .ith an e/ample o& (our o.n the 0elational Mo'el notations
The following is the notationA)
) " relation +chema ! of degree n is denoted by ! (",. "1,BB"n).
) "n n)tuple t in a relation r(!) is denoted by t Cv&, v1,B.vnD, where v& is the
value corresponding to attribute "D. The following notation refers to component
values of tuples#)
7oth tE"F and t."G, (and sometimes tEiG refer to the value v, in t for attribute ",.
7oth tE",,,H,B., "F and t.(",,,"I,,B.,"<), where H, "I,B,", is a list of attributes from !,
refer to the subtuple of values Cfu, vw,Bv<Dfrom t coreresponding to the attributes
specified in the list.
) The letters J, !, + denote relation names.
) The letters ', r, s denotes relationa states.
) The letters t, u, v denote tuples.
) (n general, the name of a relation schema such as +T2%4*T also indicates the
current set of tuples in that relation 5 the current relation state 5 whereas
+T2%4*T(*ame, !oll*o,..) refers only to the relation schema.
) "n attribute " can be 'ualified with the relation name ! to which it belongs by
using the dot notation !.") for e$. +T2%4*T.*ame or +T2%4*T."?4. This is
because the same name may be used for two attributes in different relations.
However all attribute names in a particular relation must be distinct.
4$#)
.onsider the tuple t CK"nkit +harmaK, L:333);/)&13=K, L>9919;:&39K, L+under+treet,
.hennaiK, null, 1>, 3.1:D
We have tE*ameG C"nkit +harmaKD, and tE!oll*o, ?-", "geG CK:33);/)&13=K, &/.
0
6) a1ing an e/ample 2nterprise S(stem3 List out the 2ntit( t(pes3 2ntit( sets3
%ttributes an' 1e(s.
" database usually contains groups of entities that are similar. @or e$., a company
employing hundreds of employees may want to store similar information concerning
each of the employees. These employees entities share the same attributes, but each
entity has its own value(s) for each attribute. "n entity type defines a collection (or set)
of entities that have the same attributes. 4ach entity type in the database is described by
its name and attributes. The collection of all entities of a particular entity type in the
database at any point in time is called an entity setA the entity set is usually referred to
using the same name as the entity type. @or e$., 48-6MN44 refers to both a type of
entity as well as the current set of all employee entities in the database.
"n entity type is represented as a rectangular bo$ enclosing the entity type name.
"ttribute names are enclosed in ovals and are attached to their entity type by straight
lines. .omposite attributes are attached to their component attributes by straight lines.
8ultivalued attributes are displayed in double ovals.
"n entity type describes the schema or intension for a set of entities that share the
same structure. The collection of entities of a particular entity type are grouped into an
entity set, which is also called the e$tension of the entity type.
"n important constraint on the entities of an entity type is the key or uni'ueness
constraint on attributes. "n entity type usually has an attribute whose value are distinct
for each individual entity in the entity set. +uch an attribute is called key attribute, and
its values can be used to identify each entity uni'uely. @or e$., the *ame attribute is a
key of the .M8-"*N entity type in the following figure, because no two companies are
allowed to have the same name. +ometimes, several attributes together forma key,
meaning that the combination of the attribute values must be distinct for each entity.
=
/
