BLOCK-1 UNIT-1
RELATIONAL DATABASE DESIGN
Q1. Write short note on DKNF.
Ans. The Domain-Key Normal Form (DKNF) offers a complete solution to avoid the anomalies. Thus, it is an important Normal form. A set of relations that are in DKNF must be free of anomalies. The DKNF is based on the Fagin’s theorem that states: “A relation is in DKNF if every constraint on the relation is a logical consequence of the definitions of keys and domains.”
Key can be either the primary keys or the candidate keys.
Key declaration: Let R be a relation schema with K ⊆ R. A key K requires that K be a superkey for schema R such that K R. Please note that a key declaration is a functional dependency but not all functional dependencies are key declarations.
Domain is the set of definitions of the contents of attributes and any limitations on the kind of data to be stored in the attribute.
Domain declaration: Let A be an attribute and dom be a set of values. The domain declaration stated as A ⊆ dom requires that the values of A in all the tuples of R be values from dom.
Constraint is a well defined rule that is to be uphold by any set of legal data of R.
General constraint: A general constraint is defined as a predicate on the set of all the relations of a given schema. The MVDs, JDs are the examples of general constraints. A general constraint need not be a functional, multivalued, or join dependency. For example, in the student’s enrolment number the first two digit represents year. Assuming all the students are MCA students and the maximum duration of MCA is 6 years, in the year 2006, the valid students will have enrolment number that consists of 00 as the first two digits. Thus, the general constraint for such a case may be: “If the first two digit of t[enrolment number] is 00, then t[marks] are valid.”
The constraint suggests that our database design is not in DKNF. To convert this design to DKNF design, we need two schemas as:
Valid student schema =(enrolment number, subject, marks)
Invalid student schema = (enrolment number, subject, marks)
Please note that the schema of valid account number requires that the enrolment number of the student begin with the 00. The resulting design is in DKNF.
Please note that the constraints that are time-dependent or relate to changes made in data values were excluded from the definition of DKNF. This implies that a timedependent constraint (or other constraint on changes in value) may exist in a table and may fail to be a logical consequence of the definitions of keys and domains, yet the table may still be in DKNF.
How to convert a relation to DKNF? There is no such direct procedure for converting a table into one or more tables each of which is in DKNF. However, as a matter of practice, the effort to replace an arbitrary table by a set of single-theme tables may covert a set of tables to DKNF.
A result of DKNF is that all insertion and deletion anomalies are removed. DKNF represents an “ultimate” normal form because it allows constraints, rather than dependencies. DKNF allows efficient testing of the constraints. Of course, if a schema is not in DKNF, we may have to perform decomposition, but such decompositions are not always dependency-preserving. Thus, although DKNF is an aim of a database designer, it may not be implemented in a practical design.
Q2. What is functional dependency?
Ans. When a single constraint is established between two sets of attributes from the atabase it is called functional dependency. Let us consider a single universal relation scheme “A”. A functional dependency denoted by X → Y, between two sets of attributes X and Y that are subset of universal relation “A” specifies a constraint on the possible tuples that can form a relation state of “A”. The constraint is that, for any two tuples t1 and t2 in “A” that have t1(X) = t2 (X), we must also have t1(Y) = t2(Y). It means that, if tuple t1 and t2 have same values for attributes X then X→Y to hold t1 and t2 must have same values for attributes Y.
Thus, FD X→Y means that the values of the Y component of a tuple in “A” depend on or is determined by the values of X component. In other words, the value of Y component is uniquely determined by the value of X component. This is functional dependency from X to Y (but not Y to X) that is, Y is functionally dependent on X.
The relation schema “A” determines the function dependency of Y on X (X→Y) when and only when:
1) if two tuples in “A”, agree on their X value then
2) they must agree on their Y value.
Please note that if X → Y in “A”, does not mean Y→ X in “A”.
This semantic property of functional dependency explains how the attributes in “A” are related to one another. A FD in “A” must be used to specify constraints on its attributes that must hold at all times.
Consider a relation
STUDENT-COURSE (enrolno, sname, cname, classlocation, hours)
We know that the following functional dependencies (we identify these primarily from constraints, there is no thumb rule to do so otherwise) should hold:
• enrolno →sname (the enrolment number of a student uniquely determines the student names alternatively, we can say that sname is functionally determined/dependent on enrolment number).
• classcode → cname, classlocation, (the value of a class code uniquely determines the class name and class location.
• enrolno, classcode → Hours (a combination of enrolment number and class code values uniquely determines the number of hours and students study in the class per week (Hours).
BLOCK-1 UNIT-2
DATABASE IMPEMENTATION AND TOOLS
Q1 Explain the information system life cycle.
Ans
(1) Communication: This basically includes:
• Analysing potential application areas.
• Identifying the economics of information.
• Performing preliminary cost-benefit studies.
• Determining complexity of data and processes.
• Setting up priorities among applications.
• Gathering detailed requirements by interacting with users and user groups.-
• Identification of inter-application dependencies, communication and reporting procedures.
(2) Planning: This basically includes:
• Estimating the cost and time.
• Estimating the resource requirements.
• Identification of step-by-step (micro) procedure for each phase of SDLC.
• Scheduling of resources as per the needs.
• Tracking the resources as the project progresses.
(3) Modeling: Now let us see what we do in modeling:
• We create and refine analysis and design models.
• The information system is designed, it includes:
o Design of the database system and the design of Application systems.
o Design of information needs at different levels, system architecture design.
o Forms and report design.
o Design of Database Transactions and processes in detail.
(4) Construction: Construction mainly includes:
• Coding and implementing the system as per the detailed design.
• Creation of database and loading some sample data.
• Implementation of database transactions.
• Testing of all the above.
• Checking acceptability of the system in meeting user’s requirements and performance criteria.
• The system is tested against performance criteria and behaviour specifications.
(5) Deployment: This is the last stage but necessarily an important one:
• Operational phase checks whether all system functions are operational and have been validated.
• New requirements and applications are validated and tested.
• Maintenance and monitoring of system performance is an important activity done here.
Q2. Explain Database Application Life Cycle.
Ans. The database application life cycle defines the phases of development of a database application. Let us list the activities that help us to create a database:
(1) System definition: In this activity, the scope of the database system, its users and its applications are defined with the help of users information. Other activities of this phase are:
• to find the interfaces for various categories of users.
• to find the response time constraints.
• to identify the storage and processing needs.
(2) Design of Conceptual Database Application: It involves design of the complete conceptual schema of the database and the transaction and Data processing.
(3) Logical and Physical Database Design: This involves creation of views, creation of storage structure, indexes etc.
(4) Database Implementation: This is the process by which we implement the following:
• Conceptual Database
• External Database
• Internal Database
• The mappings among these designs
• Creating empty database files
• Implementing the software applications.
(5) Application Conversion: Any software application from a previous system is converted to the new system. The data is populated either by loading the data directly or by converting existing files into the database system format.
(6) Testing and Validations: The new system, which is made needs to be tested and validated for good results. Testing and validation is done for this particular purpose.
(7) Operations: During this phase, the old as well as the new systems are operated in parallel.
(8) Monitoring and Maintenance: Change is an unchanging phenomenon. Similarly, modifications and reorganisation are unavoidable and may be needed from time to time. During this phase, the system is constantly monitored and maintained.
BLOCK-1 UNIT-3
ADVANCED SQL
Q1 What are assertions? What is the syntax for declaration of an assertion? Also give an example of assertion.
Ans Assertions are constraints that are normally of general nature. For example, the age of the student in a hypothetical University should not be more than 25 years or the minimum age of the teacher of that University should be 30 years. Such general constraints can be implemented with the help of an assertion statement.
The syntax for creating assertion is:
Syntax:
CREATE ASSERTION <Name>
CHECK (<Condition>);
Thus, the assertion on age for the University as above can be implemented as:
CREATE ASSERTION age-constraint
CHECK (NOT EXISTS (
SELECT *
FROM STUDENT s
WHERE s.age > 25
OR s.age > (
SELECT MIN (f.age)
FROM FACULTY f
));
The assertion name helps in identifying the constraints specified by the assertion. These names can be used to modify or delete an assertion later. But how are these assertions enforced? The database management system is responsible for enforcing the assertion on to the database such that the constraints stated in the assertion are not violated. Assertions are checked whenever a related relation changes.
Now try writing an assertion for a university system that stores a database of faculty as:
FACULTY (code, name, age, basic salary, medical-allow, other benefits)
MEDICAL-CLAIM (code, date, amount, comment)
Assertion: The total medical claims made by a faculty member in the current financial year should not exceed his/her medial allowance.
CREATE ASSERTION med-claim
CHECK (NOT EXISTS (
SELECT code, SUM (amount), MIN(medical-allow)
FROM (FACULTY NATRUAL JOIN MEDICAL-CLAIM)
WHERE date>”31-03-2006”
GROUP BY code
HAVING MIN(medical-allow) < SUM(amount)
));
OR
CREATE ASSERTION med-claim
CHECK (NOT EXISTS (
SELECT *
FROM FACULT f
WHERE (f.code IN
(SELECT code, SUM(amount)
FROM MEDICAL-CLAIM m
WHERE date>”31-03-2006” AND f.code=m.code AND
f.medical-allow<SUM(amount)
Q2. What is views? What are the SQL commands
-to specify a view
-for updating of views
-for deleting of views
Illustrate with an example
Ans A view is a virtual table, which does not actually store data. But if it does not store any data, then what does it contain?
A view actually is a query and thus has a SELECT FROM WHERE ….. clause which works on physical table which stores the data. Thus, the view is a collection of relevant information for a specific entity.
The SQL commands for creating views, with the help of an example.
Example: A student’s database may have the following tables:
STUDENT (name, enrolment-no, dateofbirth)
MARKS (enrolment-no, subjectcode, smarks)
For the database above a view can be created for a Teacher who is allowed to view only the performance of the student in his/her subject, let us say MCS-043.
CREATE VIEW SUBJECT-PERFORMANCE AS
(SELECT s.enrolment-no, name, subjectcode, smarks
FROM STUDENT s, MARKS m
WHERE s.enrolment-no = m.enrolment-no AND
subjectcode ‘MCS-043’ ORDER BY s.enrolment-no;
A view can be dropped using a DROP statement as:
DROP VIEW SUBJECT-PERFORMANCE;
The table, which stores the data on which the statement of the view is written, is sometimes referred to as the base table. You can create views on two or more base tables by combining the data using joins. Thus, a view hides the logic of joining the tables from a user. You can also index the views too. This may speed up the performance. Indexed views may be beneficial for very large tables. Once a view has been created, it can be queried exactly like a base table. For example:
SELECT *
FROM STUDENT-PERFORMANCE
WHERE smarks >50
Q3. Explain Embedded SQL and Dynamic SQL.
Ans. The embedded SQL statements can be put in the application program written in C,
Java or any other host language. These statements sometime may be called static. Why are they called static? The term ‘static’ is used to indicate that the embedded SQL commands, which are written in the host program, do not change automatically during the lifetime of the program. Thus, such queries are determined at the time of database application design. For example, a query statement embedded in C to determine the status of train booking for a train will not change. However, this query may be executed for many different trains. Please note that it will only change the input parameter to the query that is train-number, date of boarding, etc., and not the query itself.
Example: Write a C program segment that prints the details of a student whose enrolment number is input.
Let us assume the relation
STUDENT (enrolno:char(9), name:Char(25), phone:integer(12), prog-code:char(3))
/* add proper include statements*/
/*declaration in C program */
EXEC SQL BEGIN DECLARE SECTION;
Char enrolno[10], name[26], p-code[4];
int phone;
int SQLCODE;
char SQLSTATE[6]
EXEC SQL END DECLARE SECTION;
/* The connection needs to be established with SQL*/
/* program segment for the required function */
printf (“enter the enrolment number of the student”);
scanf (“% s”, &enrolno);
EXEC SQL
SELECT name, phone, prog-code INTO
:name, :phone, :p-code
FROM STUDENT
WHERE enrolno = :enrolno;
If (SQLCODE ==0)
printf (“%d, %s, %s, %s”, enrolno, name, phone, p-code)
else
printf (“Wrong Enrolment Number”);
Please note the following points in the program above:
• The program is written in the host language ‘C’ and contains embedded SQL statements.
• Although in the program an SQL query (SELECT) has been added. You can embed any DML, DDL or views statements.
• The distinction between an SQL statement and host language statement is made by using the key word EXEC SQL; thus, this key word helps in identifying the Embedded SQL statements by the pre-compiler.
• Please note that the statements including (EXEC SQL) are terminated by a semi-colon (;),
• As the data is to be exchanged between a host language and a database, there is a need of shared variables that are shared between the environments. Please note that enrolno[10], name[20], p-code[4]; etc. are shared variables, colon (:) declared in ‘C’.
• Please note that the shared host variables enrolno is declared to have char[10] whereas, an SQL attribute enrolno has only char[9]. Why? Because in ‘C’ conversion to a string includes a ‘\ 0’ as the end of the string.
• The type mapping between ‘C’ and SQL types is defined in the following table:
• Please also note that these shared variables are used in SQL statements of the program. They are prefixed with the colon (:) to distinguish them from database attribute and relation names. However, they are used without this prefix in any C language statement.
• Please also note that these shared variables have almost the same name (except p-code) as that of the attribute name of the database. The prefix colon (:) this distinguishes whether we are referring to the shared host variable or an SQL attribute. Such similar names is a good programming convention as it helps in identifying the related attribute easily.
• Please note that the shared variables are declared between BEGIN DECLARE SECTION and END DECLARE SECTION and there typed is defined in ‘C’ language.
Two more shared variables have been declared in ‘C’. These are:
• SQLCODE as int
• SQLSTATE as char of size 6
• These variables are used to communicate errors and exception conditions between the database and the host language program. The value 0 in SQLCODE means successful execution of SQL command. A value of the SQLCODE =100 means ‘no more data’. The value of SQLCODE if less than 0 indicates an error. Similarly, SQLSTATE is a 5 char code the 6th char is for ‘\0’ in the host language ‘C’. Value “00000” in an SQLSTATE indicate no error.
• In order to execute the required SQL command, connection with the database server need to be established by the program. For this, the following SQL statement is used:
CONNECT <name of the server> AS <name of the connection>
AUTHORISATION <username, password>,
TO DISCONNECT we can simply say
DISCONNECT <name of the connection>;
However, these statements need to be checked in the commercial database management system, which you are using.
Execution of SQL query in the given program: To create the SQL query, first, the given value of enrolment number is transferred to SQL attribute value, the query then is executed and the result, which is a single tuple in this case, is transferred to shared host variables as indicated by the key word INTO after the SELECT statement. The SQL query runs as a standard SQL query except the use of shared host variables. Rest of the C program has very simple logic and will print the data of the students whose enrolment number has been entered.
Cursors and Embedded SQL
Let us first define the terminate ‘cursor’. The Cursor can be defined as a pointer to the current tuple. It can also be defined as a portion of RAM allocated for the internal processing that has been set aside by the database server for database interactions. This portion may be used for query processing using SQL. But, what size of memory is to be allotted for the cursor? Ideally, the size allotted for the cursor should be equal to the memory required to hold the tuples that result from a query. However, the available memory puts a constraint on this size. Whenever a query results in a number of tuples, we can use a cursor to process the currently available tuples one by one. How? Let us explain the use of the cursor with the help of an example:
Since most of the commercial RDBMS architectures are client-server architectures, on execution of an embedded SQL query, the resulting tuples are cached in the cursor. This operation is performed on the server. Sometimes the cursor is opened by RDBMS itself – these are called implicit cursors. However, in embedded SQL you need to declare these cursors explicitly – these are called explicit cursors. Any cursor needs to have the following operations defined on them:
DECLARE – to declare the cursor
OPEN AND CLOSE - to open and close the cursor
FETCH – get the current records one by one till end of tuples.
In addition, cursors have some attributes through which we can determine the state of the cursor. These may be:
ISOPEN – It is true if cursor is OPEN, otherwise false.
FOUND/NOT FOUND – It is true if a row is fetched successfully/not successfully.
ROWCOUNT – It determines the number of tuples in the cursor.
Let us explain the use of the cursor with the help of an example:
Example: Write a C program segment that inputs the final grade of the students of MCA programme.
Let us assume the relation:
STUDENT (enrolno:char(9), name:Char(25), phone:integer(12), prog-code:char(3)); grade: char(1));
The program segment is:
/* add proper include statements*/
/*declaration in C program */
EXEC SQL BEGIN DECLARE SECTION;
Char enrolno[10], name[26], p-code[4], grade /* grade is just one character*/
int phone;
int SQLCODE;
char SQLSTATE[6]
EXEC SQL END DECLARE SECTION;
/* The connection needs to be established with SQL*/
/* program segment for the required function */
printf (“enter the programme code);
scanf (“%s, &p-code);
EXEC SQL DECLARE CURSOR GUPDATE
SELECT enrolno, name, phone, grade
FROM STUDENT
WHERE progcode =: p-code
FOR UPDATE OF grade;
EXEC SQL OPEN GUPDATE;
EXEC SQL FETCH FROM GUPDATE
INTO :enrolno, :name, :phone, :grade;
WHILE (SQLCODE==0) {
printf (“enter grade for enrolment number, “%s”, enrolno);
scanf (“%c”, grade);
EXEC SQL
UPDATE STUDENT
SET grade=:grade
WHERE CURRENT OF GUPDATE
EXEC SQL FETCH FROM GUPDATE;
}
EXEC SQL CLOSE GUPDATE;
• Please note that the declared section remains almost the same. The cursor is declared to contain the output of the SQL statement. Please notice that in this case, there will be many tuples of students database, which belong to a particular programme.
• The purpose of the cursor is also indicated during the declaration of the cursor.
• The cursor is then opened and the first tuple is fetch into shared host variable followed by SQL query to update the required record. Please note the use of CURRENT OF which states that these updates are for the current tuple referred to by the cursor.
• WHILE Loop is checking the SQLCODE to ascertain whether more tuples are pending in the cursor.
• Please note the SQLCODE will be set by the last fetch statement executed just prior to while condition check.
How are these SQL statements compiled and error checked during embedded SQL?
• The SQL pre-compiler performs the type of checking of the various shared host variables to find any mismatches or errors on each of the SQL statements. It then stores the results into the SQLCODE or SQLSTATE variables. Is there any limitation on these statically embedded SQL statements? They offer only limited functionality, as the query must be known at the time of application development so that they can be pre-compiled in advance. However, many queries are not known at the time of development of an application; thus we require dynamically embedded SQL also.
Dynamic SQL
Dynamic SQL, unlike embedded SQL statements, are built at the run time and placed in a string in a host variable. The created SQL statements are then sent to the DBMS for processing. Dynamic SQL is generally slower than statically embedded SQL as they require complete processing including access plan generation during the run time. However, they are more powerful than embedded SQL as they allow run time application logic. The basic advantage of using dynamic embedded SQL is that we need not compile and test a new program for a new query. Let us explain the use of dynamic SQL with the help of an example:
Example: Write a dynamic SQL interface that allows a student to get and modify permissible details about him/her. The student may ask for subset of information also.
Assume that the student database has the following relations.
STUDENT (enrolno, name, dob)
RESULT (enrolno, coursecode, marks)
In the table above, a student has access rights for accessing information on his/her enrolment number, but s/he cannot update the data. Assume that user names are enrolment number.
Solution: A sample program segment may be (please note that the syntax may change
for different commercial DBMS).
/* declarations in SQL */
EXEC SQL BEGIN DECLARE SECTION;
char inputfields (50);
char tablename(10)
char sqlquery ystring(200)
EXEC SQL END DECLARE SECTION;
printf (“Enter the fields you want to see \n”);
scanf (“SELECT%s”, inputfields);
printf (“Enter the name of table STUDENT or RESULT”);
scanf (“FROM%s”, tablename);
sqlqueryystring = “SELECT” +inputfields +“ ”+
“FROM” + tablename
+ “WHERE enrolno + :USER”
/*Plus is used as a symbol for concatenation operator; in some DBMS it may be ||*/
/* Assumption: the user name is available in the host language variable USER*/
EXEC SQL PREPARE sqlcommand FROM :sqlqueryystring;
EXEC SQL EXECUTE sqlcommand;
Please note the following points in the example above.
• The query can be entered completely as a string by the user or s/he can be suitably prompted.
• The query can be fabricated using a concatenation of strings. This is language dependent in the example and is not a portable feature in the present query.
• The query modification of the query is being done keeping security in mind.
• The query is prepared and executed using a suitable SQL EXEC commands.
Q4. What is SQLJ? Explain the syntax of Declarations and Executable Statements. Also show that SQLJ uses Embedded SQL.
Ans. Till now we have talked about embedding SQL in C, but how can we embed SQL
statements into JAVA Program? For this purpose we use SQLJ. In SQLJ, a preprocessor called SQLJ translator translates SQLJ source file to JAVA source file. The JAVA file compiled and run on the database. Use of SQLJ improves the productivity and manageability of JAVA Code as:
• The code becomes somewhat compact.
• No run-time SQL syntax errors as SQL statements are checked at compile time.
• It allows sharing of JAVA variables with SQL statements. Such sharing is not possible otherwise.
Please note that SQLJ cannot use dynamic SQL. It can only use simple embedded SQL. SQLJ provides a standard form in which SQL statements can be embedded in JAVA program. SQLJ statements always begin with a #sql keyword. These embedded SQL statements are of two categories – Declarations and Executable Statements.
Declarations have the following syntax:
#sql <modifier> context context_classname;
The executable statements have the following syntax:
#sql {SQL operation returning no output};
OR
#sql result = {SQL operation returning output};
Example:
Let us write a JAVA function to print the student details of student table, for the student who have taken admission in 2005 and name are like ‘Shyam’. Assuming that the first two digits of the 9-digit enrolment number represents a year, the required input conditions may be:
• The enrolno should be more than “05000000” and
• The name contains the sub string “Shyam”.
Please note that these input conditions will not be part of the Student Display function, rather will be used in the main ( ) function that may be created separately by you. The following display function will accept the values as the parameters supplied by the main ( ).
Public void DISPSTUDENT (String enrolno, String name, int phone)
{
try {
if ( name equals ( “ ” ) )
name = “%”;
if (enrolno equals (“ ”) )
enrolno = “%”;
SelRowIter srows = null;
# sql srows = { SELECT Enrolno, name, phone
FROM STUDENT
WHERE enrolno > :enrolno AND name like :name
};
while ( srows.next ( ) ) {
int enrolno = srows. enrolno ( );
String name = srows.name ( );
System.out.println ( “Enrollment_No = ” + enrolno);
System.out.println (“Name =” +name);
System.out.println (“phone =” +phone);
}
} Catch (Exception e) {
System.out.println ( “ error accessing database” + e.to_string);
}
}
Q5. What are Stored Procedures?
Ans. Stored procedures are collections of small programs that are stored in compiled form and have a specific purpose. For example, a company may have rules such as:
• A code (like enrolment number) with one of the digits as the check digit, which checks the validity of the code.
• Any date of change of value is to be recorded.
These rules are standard and need to be made applicable to all the applications that may be written. Thus, instead of inserting them in the code of each application they may be put in a stored procedure and reused. The use of procedure has the following advantages from the viewpoint of database application development.
• They help in removing SQL statements from the application program thus making it more readable and maintainable.
• They run faster than SQL statements since they are already compiled in the database.
Stored procedures can be created using CREATE PROCEDURE in some commercial DBMS.
Syntax:
CREATE [or replace] PROCEDURE [user]PROCEDURE_NAME
[(argument datatype
[, argument datatype]….)]
BEGIN
Host Language statements;
END;
For example, consider a data entry screen that allows entry of enrolment number, first name and the last name of a student combines the first and last name and enters the complete name in upper case in the table STUDENT. The student table has the following structure:
STUDENT (enrolno:char(9), name:char(40));
The stored procedure for this may be written as:
CREATE PROCEDURE studententry (
enrolment IN char (9);
f-name INOUT char (20);
l-name INOUT char (20)
BEGIN
/* change all the characters to uppercase and trim the length */
f-name TRIM = UPPER (f-name);
l-name TRIM = UPPER (l-name);
name TRIM = f-name . . l-name;
INSERT INTO CUSTOMER
VALUES (enrolment, name);
END;
INOUT used in the host language indicates that this parameter may be used both for input and output of values in the database.
While creating a procedure, if you encounter errors, then you can use the show errors command. It shows all the error encountered by the most recently created procedure object.
You can also write an SQL command to display errors. The syntax of finding an error in a commercial database is:
SELECT *
FROM USER_ERRORS
WHERE Name=‘procedure name’ and type=‘PROCEDURE’;
Procedures are compiled by the DBMS. However, if there is a change in the tables, etc. referred to by the procedure, then the procedure needs to be recompiled. You can recompile the procedure explicitly using the following command:
ALTER PROCEDURE procedure_name COMPILE;
You can drop a procedure by using DROP PROCEDURE command.
Q6. What are Triggers?
Ans Triggers are somewhat similar to stored procedures except that they are activated
automatically. When a trigger is activated? A trigger is activated on the occurrence of a particular event. What are these events that can cause the activation of triggers? These events may be database update operations like INSERT, UPDATE, DELETE etc. A trigger consists of these essential components:
• An event that causes its automatic activation.
• The condition that determines whether the event has called an exception such that the desired action is executed.
• The action that is to be performed.
Triggers do not take parameters and are activated automatically, thus, are different to stored procedures on these accounts. Triggers are used to implement constraints among more than one table. Specifically, the triggers should be used to implement the constraints that are not implementable using referential integrity/constraints. An instance, of such a situation may be when an update in one relation affects only few tuples in another relation. However, please note that you should not be over enthusiastic for writing triggers – if any constraint is implementable using declarative constraints such as PRIMARY KEY, UNIQUE, NOT NULL, CHECK, FOREIGN KEY, etc. then it should be implemented using those declarative constraints rather than triggers, primarily due to performance reasons. You may write triggers that may execute once for each row in a transaction – called Row Level Triggers or once for the entire transaction Statement Level Triggers. Remember, that you must have proper access rights on the table on which you are creating the trigger. For example, you may have all the rights on a table or at least
have UPDATE access rights on the tables, which are to be used in trigger. The following is the syntax of triggers in one of the commercial DBMS:
CREATE TRIGGER <trigger_name>
[BEFORE | AFTER|
<Event>
ON <tablename>
[WHEN <condition> | FOR EACH ROW]
<Declarations of variables if needed is – may be used when creating trigger using host
language>
BEGIN
<SQL statements OR host language SQL statements>
[EXCEPTION]
<Exceptions if any>
END:
Let us explain the use of triggers with the help of an example:
Example:
Consider the following relation of a students database
STUDENT(enrolno, name, phone)
RESULT (enrolno, coursecode, marks)
COURSE (course-code, c-name, details)
Assume that the marks are out of 100 in each course. The passing marks in a subject are 50. The University has a provision for 2% grace marks for the students who are failing marginally – that is if a student has 48 marks, s/he is given 2 marks grace and if a student has 49 marks then s/he is given 1 grace mark. Write the suitable trigger for this situation.
Please note the requirements of the trigger:
Event: UPDATE of marks
OR
INSERT of marks
Condition: When student has 48 OR 49 marks
Action: Give 2 grace marks to the student having 48 marks and 1 grace mark to the student having 49 marks.
The trigger for this thus can be written as:
CREATE TRIGGER grace
AFTER INSERT OR UPDATE OF marks ON RESULT
WHEN (marks = 48 OR marks =49)
UPDATE RESULT
SET marks =50;
We can drop a trigger using a DROP TRIGGER statement
DROP TRIGGER trigger_name;
The triggers are implemented in many commercial DBMS. Please refer to them in the respective DBMS for more details.
BLOCK-1 UNIT-4
DATABASE SYSTEM CATALOGUE
Q1. What is Data Dictionary? Write the benefits and advantages of Data Dictionary.
Ans. A Data Dictionary is a data structure that stores meta-data, i.e., data about data. The software package for a stand-alone data dictionary or data repository may interact with the software modules of theDBMS, but it is mainly used by the designers, users, and administrators of a computer system for information resource management. These systems are used to maintain information on system hardware and software configurations, documentation, applications, and users, as well as other information relevant to system administration.
If a data dictionary system is used only by designers, users, and administrators, and not by the DBMS software, it is called a passive data dictionary; otherwise, it is called an active data dictionary or data directory. An active data dictionary is automatically updated as changes occur in the database. A passive data dictionary must be manually updated.
The data dictionary consists of record types (tables) created in the database by system-generated command files, tailored for each supported back-end DBMS. Command files contain SQL statements for CREATE TABLE, CREATE UNIQUE INDEX, ALTER TABLE (for referential integrity), etc., using the specific SQL statement required by that type of database.
Data Dictionary Features
A comprehensive data dictionary product will include:
• support for standard entity types (elements, records, files, reports, programs, systems, screens, users, terminals, etc.), and their various characteristics (e.g., for elements, the dictionary might maintain Business name, Business definition, name, Data type, Size, Format, Range(s), Validation criteria, etc.)
• support for user-designed entity types (this is often called the “extensibility” feature); this facility is often exploited in support of data modelling, to record and cross-reference entities, relationships, data flows, data stores, processes, etc.
• the ability to distinguish between versions of entities (e.g., test and production)
• enforcement of in-house standards and conventions.
• comprehensive reporting facilities, including both “canned” reports and a reporting language for user-designed reports; typical reports include:
• detail reports of entities
• summary reports of entities
• component reports (e.g., record-element structures)
• cross-reference reports (e.g., element keyword indexes)
• where-used reports (e.g., element-record-program cross-references).
• a query facility, both for administrators and casual users, which includes the ability to perform generic searches on business definitions, user descriptions, synonyms, etc.
• language interfaces, to allow, for example, standard record layouts to be automatically incorporated into programs during the compile process.
• automated input facilities (e.g., to load record descriptions from a copy library).
• security features
• adequate performance tuning abilities
• support for DBMS administration, such as automatic generation of DDL (Data Definition Language).
Data Dictionary Benefits
The benefits of a fully utilised data dictionary are substantial. A data dictionary has the potential to:
• facilitate data sharing by
• enabling database classes to automatically handle multi-user coordination, buffer layouts, data validation, and performance optimisations,
• improving the ease of understanding of data definitions,
• ensuring that there is a single authoritative source of reference for all users
• facilitate application integration by identifying data redundancies,
• reduce development lead times by
• simplifying documentation
• automating programming activities.
• reduce maintenance effort by identifying the impact of change as it affects:
• users,
• data base administrators,
• programmers.
• improve the quality of application software by enforcing standards in the development process
• ensure application system longevity by maintaining documentation beyond project completions
• data dictionary information created under one database system can easily be used to generate the same database layout on any of the other database systems BFC supports (Oracle, MS SQL Server, Access, DB2, Sybase, SQL Anywhere, etc.)
These benefits are maximised by a fully utilised data dictionary. As the next section will show, our environment is such that not all of these benefits are immediately available to us.
Disadvantages of Data Dictionary
A DDS is a useful management tool, but it also has several disadvantages. It needs careful planning. We would need to define the exact requirements designing its contents, testing, implementation and evaluation. The cost of a DDS includes not only the initial price of its installation and any hardware requirements, but also the cost of collecting the information entering it into the DDS, keeping it up-to-date and enforcing standards. The use of a DDS requires management commitment, which is not easy to achieve, particularly where the benefits are intangible and long term.
BLOCK-2 UNIT-2
TRANSACTION MANAGEMENT AND RECOVERY
Q1. What is two phase locking protocol?
Ans. This is a protocol, which ensures conflict-serialisable schedules read before write of transaction kindly (these transactions read a value before writing it). It consists of two
phases:
Phase 1: Growing Phase
• Transaction may obtain locks
• Transaction may not release locks.
Phase 2: Shrinking Phase
• Transaction may release locks
• Transaction may not obtain locks.
The protocol assures serialisability. It can be proved that the transactions can be serialised in the order of their lock points (i.e., the point where a transaction acquires its final lock). Two-phase locking does not ensure freedom from deadlocks. Cascading roll-back is possible under two-phase locking as uncommitted values can be seen. To avoid this, follow a modified protocol called strict two-phase locking. Here a transaction must hold all its exclusive locks till it commits/aborts. Rigorous twophase locking is even stricter, here all locks are held till commit/abort. In this protocol transactions can be serialised in the order in which they commit.
There can be serialisable schedules that cannot be obtained if two-phase locking is used. However, in the absence of extra information (e.g., ordering of access to data), two-phase locking is needed for serialisability in the following sense:
Given a transaction Ti that does not follow two-phase locking, we may find another transaction Tj that uses two-phase locking, and a schedule for Ti and Tj that is not conflict serialisable.
Lock Conversions
Sometimes shared lock may need to be upgraded to an exclusive lock. The two-phase locking with lock conversions can be defined as:
First Phase:
• can acquire a lock-S on item
• can acquire a lock-X on item
• can convert a lock-S to a lock-X (upgrade)
Second Phase:
• can release a lock-S
• can release a lock-X
• can convert a lock-X to a lock-S (downgrade)
This protocol assures serialisability. But still relies on the programmer to insert the various locking instructions.
Automatic Acquisition of Locks
A transaction Ti issues the standard read/write instruction, without explicit locking calls.
The operation read(D) is processed as: For
if Ti has a lock on D
then
read(D)
else
begin
if necessary wait until no other
transaction has a lock-X on D
grant Ti a lock-S on D;
read(D)
end
write(D) is processed as:
if Ti has a lock-X on D
then
write(D)
else
begin
if necessary wait until no other transaction has any lock on D,
if Ti has a lock-S on D
then
upgrade lock on D to lock-X
else
grant Ti a lock-X on D
write(D)
end;
All locks are released after commit or abort.
Implementation of Locking
A Lock manager can be implemented as a separate process to which transactions send lock and unlock requests. The lock manager replies to a lock request by sending a lock grant messages (or a message asking the transaction to roll back, in case of a deadlock)
The requesting transaction waits until its request is answered. The lock manager maintains a data structure called a lock table to record granted locks and pending requests. The lock table is usually implemented as an in-memory hash table indexed on the name of the data item being locked.
Q2. What is Shadow Paging?
Ans Shadow paging is an alternative to log-based recovery; this scheme is useful if transactions are executed serially. In this two page tables are maintained during the lifetime of a transaction–the current page table, and the shadow page table. It stores the shadow page table in nonvolatile storage, in such a way that the state of the database prior to transaction execution may be recovered (shadow page table is never modified during execution). To start with, both the page tables are identical. Only the current page table is used for data item accesses during execution of the transaction. Whenever any page is about to be written for the first time a copy of this page is made on an unused page, the current page table is then made to point to the copy and the update is performed on the copy.
To commit a transaction:
1) Flush all modified pages in main memory to disk
2) Output current page table to disk
3) Make the current page table the new shadow page table, as follows:
• keep a pointer to the shadow page table at a fixed (known) location on disk.
• to make the current page table the new shadow page table, simply update the pointer to point at the current page table on disk.
Once pointer to shadow page table has been written, transaction is committed. No recovery is needed after a crash — new transactions can start right away, using the shadow page table. Pages not pointed to from current/shadow page table should be freed (garbage collected).
Advantages of shadow-paging over log-based schemes:
• It has no overhead of writing log records,
• The recovery is trivial.
Disadvantages:
• Copying the entire page table is very expensive, it can be reduced by using a page table structured like a B+-tree (no need to copy entire tree, only need to copy paths in the tree that lead to updated leaf nodes).
• Commit overhead is high even with the above extension (Need to flush every updated page, and page table).
• Data gets fragmented (related pages get separated on disk).
• After every transaction is completed, the database pages containing old versions is completed, of modified data need to be garbage collected/freed.
• Hard to extend algorithm to allow transactions to run concurrently (easier to extend log based schemes).
Q3. Explain Deadlock Handling.
Ans
Deadlock Prevention
Deadlock prevention protocols ensure that the system will never enter into a deadlock state. The basic prevention strategies are:
• The strategies require that each transaction lock all its data items before it begins execution (pre declaration).
• They impose partial ordering of all data items and require that a transaction can lock data items only in the order specified by the partial order (graph-based protocol).
Two common techniques for deadlock prevention are wait-die and wound-wait. In both the wait-die and wound-wait schemes, a rolled back transaction is restarted with its original timestamp. Older transactions thus have precedence over newer ones, and deadlock is hence avoided.
These schemes use transaction timestamps for the prevention of deadlock.
Wait-die scheme — non-preemptive
• Older transaction may wait for younger one to release data item. Younger transactions never wait for older ones; they are rolled back instead.
• A transaction may die several times before acquiring the needed data item
Wound-wait scheme — preemptive
• Older transaction wounds (forces rollback) of younger transaction instead of waiting for it. Younger transactions may wait for older ones.
• May be fewer rollbacks than wait-die scheme.
Timeout-Based Schemes:
The timeout-based schemes have the following characteristics:
1) A transaction waits for a lock only for a specified amount of time. After that, the wait times out and transaction are rolled back. Thus deadlocks are prevented.
2) Simple to implement; but starvation may occur. Also it is difficult to determine the good value of timeout interval.
Deadlock Detection
Deadlocks can be detected using a wait-for graph, which consists of a pair G = (V,E),
• V is a set of vertices (all the transactions in the system)
• E is a set of edges; each element is an ordered pair Ti →Tj.
If Ti → Tj is in E, then there is a directed edge from Ti to Tj, implying that Ti is waiting for Tj to release a data item. When Ti requests a data item currently being held by Tj, then the edge Ti →Tj is inserted in the wait-for graph. This edge is removed only when Tj is no longer holding a data item needed by Ti.
The system is in a state of deadlock if the wait-for graph has a cycle. You must make use of a deadlock-detection algorithm periodically to look for such cycles.
Deadlock Recovery
When a deadlock is detected, some transaction will have to be rolled back to break the deadlock. Selecting that transaction, as a victim will incur minimum cost. Rollback will determine the distance the transaction needs to be rolled back. Total rollback aborts the transaction and then restarts it. The more effective method of deadlock recovery is to rollback transaction only as far as necessary to break the deadlock. Starvation occurs if the same transaction is always selected as a victim. You can include the number of rollbacks in the cost factor calculation in order to avoid starvation.
BLOCK 2 UNIT 3
DATABASE SECURITY AND AUTHORISATION
Q1. What do you mean by statistical database security? How can you protect your database from Statistical Query attacks?
Ans There are many database systems where information can be determined without having the access rights to do so. This is a breach of data confidentiality.
Types of Disclosures
Data of an organisation is a very sensitive resource. Even the characteristics of data are quite sensitive. For example, existence of a piece of data such as “use of health related drugs” is sensitive information and is a form of disclosure. The various type of disclosure may be:
• Exact Data: It may be defined as the determination of the value of an item by using a sequence of complex queries.
• Bounds: It is defined as finding the value of data item between two values. The bounds in such cases may be lowered using binary search. This may lead to a very narrow range.
• Negative Result: Sometimes it may be possible to determine a negative result. This is also a form of disclosure.
• Existence: The existence of data value in itself is a sensitive piece of information, regardless of the actual value. For example, existence of a record regarding defence expenses may be a disclosure.
“A good security scheme needs to protect data using access control while avoiding such indirect disclosures”.
Let us discuss some of the queries that may result in the disclosure of sensitive data. Consider the relation in the following Table:
Assume that a student can not only view his/her details in the Table, but also the names of his/her colleagues, and that s/he is allowed to make queries as well. Let us see how s/he can attack the database.
Simple Attacks: A simple form of direct attack may be by using the following type of query:
SELECT name
FROM STUDENT
WHERE (Hostel = ‘Yamuna’ AND Gender = ‘F’).
The query above will show the result as ‘Himani’. Thus, the information that Himani stays in Yamuna hostel has been disclosed. Please note this is a direct query and can be caught, but a person can hide this query in many ways, without changing the basic meaning of the query.
But how do we stop such disclosures? A very simple solution in this case may be: If a query that processes N records, however produces very few records (M) such that N>>M then this query may compromise security and should not be allowed to produce results.
Inference Based Attacks: Such an attack is very interesting case for determination of data through mathematical logic. For example, to determine the age of the female candidate, a series of commands can be used for determining the required information.
These commands may be:
(i) Determine the sum of age of all the female candidates,
(ii) Determine the sum age of female candidates not residing in Hostel Yamuna. Since all these queries will result in a sizable number of records they would be answered, however, they can be used to determine the age of ‘Himani’ who stays in Yamuna and is a sole female student staying there as:
Age of Himani= Result of Query (i) – Result of Query (ii).
Similarly many statistical functions like average, count, sum and their combinations can be used on various combinations of records. This sequence may be used to disclose the sensitive database values.
Thus, the database security has been compromised. In such situation the solution may be – not to allow consecutive queries whose output record set intersection is very small.
The two possible ways of securing database against such attacks may be:
i) Controlling the queries themselves, (such solutions may help in solving the queries that can be identified as causing problems).
ii) The queries that result in limited value can be checked by either rejecting a query. If the result set size is too small, it is also called ‘suppression’ or if the information that is to be displayed as a result of the query is changed slightly so that it does not match the actual value it is also called concealing.
Q2. What is Multilevel Security?
Ans. In certain applications data items can be classified under various levels of security.
Some such security levels may be Secret, Classified, etc. The database system that supports such security features are known as Multilevel Sensitive Databases. Such systems may have the following three security features:
1. Security of different objects may be different from the other attribute values of that tuple or security may be different from the other values of the attributes.
2. Thus, every individual element is the micro item for security.
3. In addition, security against statistical queries may also need to be provided.
4. A number of security level needs to be defined for such security.
There are many techniques to support multi-level security. Two important methods of
these are:
Partitioning
In this approach the original database is divided into partitions. Each of the partitions has a different level of security.
However, the major drawback of this approach is that the database looses the advantage of a relation.
Encryption
Encryption of critical information may help in maintaining security as a user who accidentally receives them cannot interpret the data. Such a scheme may be used when a user password file is implemented in the database design. However, the simple encryption algorithms are not secure, also since data is available in the database it may also be obtained in response to a query.
Q3. Explain examples of vendor-specific e-security?
Ans Individual vendors largely determine the security schemes that may be implemented to provide the link between the database and its interfaces. Following are some of the security components provided by the major vendors.
Oracle
Oracle, provides SSL and S-HTTP security. Oracle uses Java as a basic component of its security model. The company created its Oracle Web Server to work most effectively with Oracle clients such as the solutions created with the Developer/2000 or other development tools.
Oracle modified the HTTP protocol to allow a straight/direct connection between the client and the server. This connection defines a session in which the user is identified by a generated ID.
These enhancements are also present in the Secure Network Server (SNS) that is included in the Oracle Universal Database a single login permits access to any Oracle database in an enterprise system.
The Java security classes are used by the oracle development tools to give complete security integration to the client.
Sybase
Sybase provides a rather elegant way of protecting data access through the Web. It extends the logon security present in the Web server to the database server for authentication. Thus, it takes advantage of the native security present in the database. Sybase provides a middleware called Web.sql that is used to interface with the Netscape Web servers.
Informix
Informix, like Sybase, relies on the logon security present in the Web server. Therefore, any database access is specified through traditional ODBC-type login channels that passes the user and password information through the connectivity middleware. Specific drivers known as Universal Web Connect integrates Informix database security with Microsoft Web servers.
Microsoft
Microsoft has included most of the key security technologies with Internet Information Server (IIS). For user authentication, Microsoft provides its tried-and-true challenge/response mechanism. Traditional login on the Web presents the same security as in the basic Windows NT login. Unfortunately, only Microsoft Internet Explorer browser supports this login approach. For database access, IIS security has been integrated with Microsoft SQL Server through the Internet Database Connector. Although, users must login through an HTML login form, the information may be verified by a SQL Server stored procedure.Microsoft has also integrated the Kerberos security architecture into Windows NT Server. By releasing the server, Microsoft hopes to integrate the Kerberos native to the NT Server with public key security. Microsoft has already released a Certificate Server API in an attempt to create a Certificate Server standard.
Netscape
Netscape Communications intends its suite of servers as a complete system for security on the Internet. Login occurs originally through the browser and then, as in the Novell Directory Services, all certification is unified in this model. Therefore, once login to the browser occurs, any resources that are permitted to the user are now accessible.
Currently, user authentication occurs by passing information to the data source via the middleware. Most companies, including Sybase, Oracle, and Informix, provide the necessary connectors for this process.
Q4. What are the levels of database security?
Ans Securing the database is a fundamental tenet for any security personnel while developing his or her security plan. The database is a collection of useful data and
can be treated as the most essential component of an organisation and its economic growth. Therefore, any security effort must keep in mind that they need to provide the strongest level of control for the database.
As is true for any other technology, the security of database management systems
depends on many other systems. These primarily include the operating system, the applications that use the DBMS, services that interact with the DBMS, the web server that makes the application available to end users, etc.
Basically database security can be broken down into the following levels:
• Server Security
• Database Connections
• Table Access Control
• Restricting Database Access.
Server Security
Server security is the process of controlling access to the database server. This is the most important aspect of security and should be carefully planned.
The basic idea here is “You cannot access what you do not see”.
For security purposes, you should never let your database server be visible to the world. If a database server is supplying information to a web server then it should be configured in such a manner that it is allowed connections from that web server only. Such a connection would require a trusted IP address.
Trusted IP Addresses
To connect to a server through a client machine, you would need to configure the server to allow access to only trusted IP addresses. You should know exactly who should be allowed to access your database server. For example, if it is the back end of a web server, then only that web server address should be allowed access to the database server. If the database server is the back end of a local application that is running on the internal network, then it should only talk to addresses from within the internal network.
Database Connections
With the ever-increasing number of Dynamic Applications, an application may allow immediate unauthenticated updates to some database. If you are going to allow users make updates to some database via a web page, please ensure that you validate all such updates. This will ensure that all updates are desirable and safe. For example, you may remove any possible SQL code from a user-supplied input. If a normal user does not input SQL code then we need not allow such data to be submitted.
Table Access Control
Table access control is probably one of the most overlooked but one of the very strong forms of database security because of the difficulty in applying it. Using a table access control properly would require the collaboration of both the system administrator as well as the database developer. In practise, however such “collaboration” is relatively difficult to find.
Q5. Write some common database security failures.
Ans. Database security is of paramount importance for an organisation, but many organisations do not take this fact into consideration, till an eventual problem occurs. The common pitfalls that threaten database security are:
Weak User Account Settings: Many of the database user accounts do not contain the user settings that may be found in operating system environments. For example, the user accounts name and passwords, which are commonly known, are not disabled or modified to prevent access.
The user account settings allow limited capabilities for security, without password controls on dictionary checks or account controls supporting expiration of user account.
Insufficient Segregation of Duties: No established security administrator role is defined in the database management of the organisation. This results in database administrators (DBAs) performing both the functions of the administrator (for users accounts), as well as the performance and operations expert. This may result in management inefficiencies.
Inadequate Audit Trails: The auditing capabilities of databases since it require keeping track of additional requirements, are often ignored for enhanced performance or disk space. Inadequate auditing results in reduced accountability. It also reduces the effectiveness of data history analysis. The audit trails records information about the actions taken on certain critical of data. They log events directly associated with the data, thus, they are essential for monitoring the access and the activities on a database system.
Unused DBMS Security Features: The security of an individual application is usually independent of the security of the DBMS. Please note that security measures that are built into an application apply to users of the client software only. The DBMS itself and many other tools or utilities that can connect to the database directly through ODBC or any other protocol, may bypass this application level security completely. Thus, you must try to use security restrictions that are reliable, for instance, try using security mechanism that are defined within the database.
BLOCK 2 UNIT 4
DISTRIBUTED DATABASES
Q1. Compare Cenralised and Non-Centralised databases.
Ans If the data of an organisation is stored at a single location under the strict control of the DBMS, then, it is termed as a centralised database system. A centralised system has the advantage of controlling data under a central authority, so, the chances of integrity loss, inaccuracy are very low. In such a system it is easier to enforce business rules and the system can also be made very secure.
When the organisation is geographically dispersed and the data is created and used at many distributed offices of the same organisation. In such a case the centralised database may act, as a bottleneck as all accesses to data has to be from the central site. The reliability and availability of such a system will not only be dependent on the centralised system but also on the communication links. The load on the central system may also be very high if multiple transactions are going on. Compounding the problem would be the delay that may be caused because of source access through a communication channel.
On the other hand, if we keep the data in databases at local ends that could to an extent solve these problems, as most of the data access now can be local, however, it adds overheads on part of maintaining databases at several sites. The sites must coordinate if a global query is to be handled. Thus, it will increase the overall complexity of the system.
Decision to maintain a centralised or non-centralised data will depend entirely on the nature and structure of an organisation.
Q2. Explain DDBMS and its function.
Ans. Distributed Database: A distributed database defines the distribution of a database application system in many different computer sites supporting their own DBMS environment. However, these databases from the viewpoint of a user are a single application.
A distributed database system is managed by a distributed database management system (DDBMS). A DDBMS can be classified as a homogeneous or heterogeneous system.
Heterogeneous Distributed Databases
In a heterogeneous distributed database system various sites that are participating in the distributed database may be using different DBMSs, or different data model, or may not even be a database system (non-system). Thus, the major challenge for the heterogeneous distributed database system would be to make these systems appear as a single application system for the user.
A heterogeneous database system may have to allow data access from various type of data and thus, have to know about such data formats, file formats and management related details for such data. A heterogenous database system may need to develop some standard forms that could be used for bringing the heterogeneous sources of data to a common interface. Therefore, heterogeneous DDBMS are very complex in nature.
Homogeneous Distributed Databases
The homogeneous distributed database systems contain identical DBMS across cooperating sites. These sites are aware of each other and need to compromise a little on their individual autonomy. In this unit, we have discussed details regarding these types of distributed database systems.
Q3. Briefly describe the functions of a DDBMS.
Ans. • It allows access to remote sites using standard SQL interfaces, thus allowing transfer of queries or components of queries as well as data of the database over a network.
• It has complete control over the system catalogue that stores the details of data distribution. Please note that this catalogue itself may however, be distributed.
• It performs distributed query processing, optimisation and evaluation. Please note that distributed query processing involves even access to remote data over the network.
• One of the major functions of the distributed database system is the control of distributed concurrent transactions to maintain consistency of the data that may be replicated accross various sites.
• Access to the databases under the replicated environment should be controlled. Thus, a distributed database management system should follow proper authorisation/access privileges to the distributed data.
• Distributed recovery mechanisms in addition to dealing with the failure of participating sites may also need to deal with the failure of communication links.
Q4. Explain distributed concurrency control.
Ans The basic objectives of concurrency control mechanism in a distributed database are:
(1) to ensure that various data items and their replications are in a consistent state,
when concurrent transactions are going on at the same time, and
(2) to ensure that all the concurrent transactions get completed in finite time.
A distributed database system has to deal with the following two types of problems that occur due to distributed concurrent transactions:
• Concurrent transactions related problems that occur in a centralised database, (namely, lost updates, read uncommitted and inconsistent analysis).
• In addition, concurrency related problems arise due to data distribution and replication. For example, the need to update a data item that is located at multiple locations. Such data item require to be updated at all the locations or on none at all.
Q5. Explain distributed comit protocols 2PC.
Ans A transaction is a unit of work as well as the unit of recovery. A transaction has four basic properties – atomicity, consistency, isolation and durability. Thus, it is the responsibility of any DBMS to ensure that the transaction is executed as a single unit, that is, completely or not at all. It should leave the database in a consistent state, the effect of execution of one transaction should not be visible to other transactions till commit, and the transaction once committed cannot be undone. A DDBMS is also expected to preserve these properties of the transaction. However, in order to do so, it needs to do much more than the centralised databases. The key here is to design a commit protocol for distributed transactions.
Two-Phase Commit (2PC)
In a DDBMS since a transaction is being executed at more than one site, the commit protocol may be divided into two phases. The basic objective of this two-phase commit protocol is to make sure that a transaction and all its sub-transactions commit together or do not commit at all. Please note that, a two-phase commit protocol ensures integrity and handles remote procedure calls and triggers.
A 2PC consists of two phases:
• voting phase and
• decision phase.
For each transaction, there is a coordinator who controls the 2PC. The sub-transaction sites act as participants. The logical steps of 2PC are:
• coordinator asks its participants whether they are prepared to commit the transaction, or not
• participants may votes to commit, abort or fail to respond within a time-out period,
• the coordinator makes a decision to commit if all participants say commit or abort even if one participant says so or, even if, one of the participant does not respond,
• global decision is communicated to all the participants,
• if a participant votes to abort, then it is free to abort the transaction immediately as the result of this voting will definitely be abort. This is known as a unilateral abort,
• if a participant votes to commit, then it waits for the coordinator to send the global commit or global abort message,
• each participant maintains its local log so that it can commit or rollback the local sub-transaction reliably. In 2PC participants wait for messages from other sites, thus, unnecessarily blocking the participating processes, even though a system of timeouts is used.
The steps for the coordinator in 2PC commit is as follows:
Coordinator
Phase 1
• Writes a start-commit record to its log file.
• Sends a PREPARE message to all the participants.
• Waits for participants to respond within a time period.
Phase 2
• If even a single participant returns ABORT vote, then write abort record to its log and send a GLOBAL-ABORT message to all the participants. It then waits for participants to acknowledge the global message within a time period.
• If a participant returns a COMMIT vote, then update the list of responses. Check if all participants have voted COMMIT, if so it writes a commit record to its log file. It then sends a GLOBAL-COMMIT message to all participants and then waits for acknowledgements in a specific time period.
• If all acknowledgements are received then the coordinator writes an endtransaction message to its log file. If a site does not acknowledge then the coordinator re-sends the global decision until an acknowledgement is received.
In Phase1 the coordinator should wait until it has received the vote from all participants. If a site fails to vote, then the coordinator assumes an ABORT vote by default and takes a decision to GLOBAL-ABORT and sends this message to all participants.
The steps at the participant in 2PL is as follows:
Participant
Phase 1
• On receiving a PREPARE message, a participant:
(a) writes a ready to commit record to its local log file and send a COMMIT vote message to the coordinator, or
(b) writes an abort record to its log file and send an ABORT message to the coordinator. It can now abort the transaction unilaterally.
• It then waits for the coordinator to respond within a time period.
Phase 2
• If the participant receives a GLOBAL-ABORT message, it writes an abort record to its log file. It then aborts the transaction and on completion of this step, it sends an acknowledgement to the coordinator. Please note in case this transaction has sent an abort message in phase 1 then it may have completed the unilateral abort. In such a case only the acknowledgement needs to be sent.
• If the participant receives a GLOBAL-COMMIT message, it writes a commit record to its log file. It then commits the transaction, releases all the locks it holds, and sends an acknowledgement to the coordinator.
What happens when a participant fails to receive the GLOBAL – COMMIT or GLOBAL – ABORT from the coordinator or the coordinator fails to receive a response from a participant? In such a situation a termination protocol may be invoked. A termination protocol is followed by only the active sites. The failed sites need to follow those when they recover. In practice, these protocols are quite complex in nature but have been implemented in most of the distributed database management system.
BLOCK -3 UNIT-1
OBJECT ORIENTED DATABASE
Q1. What is the difference between Object Relational DBMS and Object Oriented DBMS?
Ans.
Q2. What are the limitations of relational database?
Ans Relational database technology was not able to handle complex application systems such as Computer Aided Design (CAD), Computer Aided Manufacturing (CAM), and Computer Integrated Manufacturing (CIM), Computer Aided Software Engineering (CASE) etc. The limitation for relational databases is that, they have been designed to represent entities and relationship in the form of two-dimensional tables. Any
complex interrelationship like, multi-valued attributes or composite attribute may result in the decomposition of a table into several tables, similarly, complex interrelationships result in a number of tables being created. Thus, the main asset of relational databases viz., its simplicity for such applications, is also one of its weaknesses, in the case of complex applications.
The data domains in a relational system can be represented in relational databases as standard data types defined in the SQL. However, the relational model does not allow extending these data types or creating the user’s own data types. Thus, limiting the types of data that may be represented using relational databases.
Another major weakness of the RDMS is that, concepts like inheritance/hierarchy need to be represented with a series of tables with the required referential constraint. Thus they are not very natural for objects requiring inheritance or hierarchy.
However, one must remember that relational databases have proved to be commercially successful for text based applications and have lots of standard features including security, reliability and easy access. Thus, even though they, may not be a very natural choice for certain applications, yet, their advantages are far too many. Thus, many commercial DBMS products are basically relational but also support object oriented concepts.
Q3. What is the need for Object Oriented Databases?
Ans. The objects may be complex, or they may consists of low-level object (for example, a window object may consists of many simpler objects like menu bars scroll bar etc.). However, to represent the data of these complex objects through relational database
models you would require many tables – at least one each for each inherited class and a table for the base class. In order to ensure that these tables operate correctly we would need to set up referential integrity constraints as well. On the other hand, object oriented models would represent such a system very naturally through, an inheritance hierarchy. Thus, it is a very natural choice for such complex objects.
Consider a situation where you want to design a class, (let us say a Date class), the advantage of object oriented database management for such situations would be that they allow representation of not only the structure but also the operation on newer user defined database type such as finding the difference of two dates. Thus, object oriented database technologies are ideal for implementing such systems that support complex inherited objects, user defined data types (that require operations in addition to standard operation including the operations that support polymorphism).
Another major reason for the need of object oriented database system would be the seamless integration of this database technology with object-oriented applications. Software design is now, mostly based on object oriented technologies. Thus, object oriented database may provide a seamless interface for combining the two technologies.
The Object oriented databases are also required to manage complex, highly interrelated information. They provide solution in the most natural and easy way that is closer to our understanding of the system.
BLOCK-3 UNIT-3
INTORDUCTION TO DATA WAREHOUSING
Q1. What is data warehousing?
Ans A data warehouse is a tool that manage of data after and outside of operational systems. Thus, they are not replacements for the operational systems but are major tools that acquires data from the operational system. Data warehousing technology has evolved in business applications for the process of strategic decision making.
A data warehouse is a subject-oriented, integrated, nonvolatile, time-variant collection of data that supports decision-making of the management. Data warehouses provide controlled access to data for complex analysis, knowledge discovery, and decision-making.
Q2. Write the uses of data warehousing in various industries.
Ans
Q3. What are the advantages of data warehouse?
Ans. A data warehouse offers the following advantages:
• It provides historical information that can be used in many different forms of comparative and competitive analysis.
• It enhances the quality of the data and tries to make it complete.
• It can help in supporting disaster recovery although not alone but with other back up resources.
One of the major advantages a data warehouse offers is that it allows a large collection of historical data of many operational databases, which may be heterogeneous in nature, that can be analysed through one data warehouse interface, thus, it can be said to be a ONE STOP portal of historical information of an organisation. It can also be used in determining many trends through the use of data mining techniques.
Data warehouse supports various business intelligence applications. Some of these may be - online analytical processing (OLAP), decision-support systems (DSS), data mining etc.
Q4. Explain the architecture of a Data warehouse wit the help of a figure.
Ans A data warehouse basically consists of three components:
The Data Sources
The ETL and
The Schema of data of data warehouse including meta data.
The Data Warehouse Architecture
The Data Sources
The data of the data warehouse can be obtained from many operational systems. A data warehouse interacts with the environment that provides most of the source data for the data warehouse. By the term environment, we mean, traditionally developed applications. In a large installation, hundreds or even thousands of these database systems or files based system exist with plenty of redundant data.
This data needs to be integrated into the warehouse. But how do we integrate the data of these large numbers of operational systems to the data warehouse system? We need the help of ETL tools to do so. These tools capture the data that is required to be put in the data warehouse database.
Data of Data Warehouse
A data warehouse has an integrated, “subject-oriented”, “time-variant” and “nonvolatile” collection of data. The basic characteristics of the data of a data warehouse can be described in the following way:
i) Integration: Integration means bringing together data of multiple, dissimilar operational sources on the basis of an enterprise data model. The enterprise data model can be a basic template that identifies and defines the organisation’s key data items uniquely.
ii) Subject Orientation: The second characteristic of the data warehouse’s data is that its design and structure can be oriented to important objects of the organisation.
iii) Time-Variance: The third defining characteristic of the database of data warehouse is that it is time-variant, or historical in nature. The entire data in the data warehouse is/was accurate at some point of time. This is, in contrast with operational data that changes over a shorter time period. The data warehouse’s data contains data that is date-stamped, and which is historical data. Figure 4 defines this characteristic of data warehouse.
iv) Non-volatility (static nature) of data: Data warehouse data is loaded on to the data warehouse database and is subsequently scanned and used, but is not updated in the same classical sense as operational system’s data which is updated through the transaction processing cycles.
Decision Support and Analysis Tools
A data warehouse may support many OLAP and DSS tools. Such decision support applications would typically access the data warehouse database through a standard query language protocol; an example of such a language may be SQL. These applications may be of three categories: simple query and reporting, decision support systems and executive information systems.
Meta Data Directory
The meta data directory component defines the repository of the information stored in the data warehouse. The meta data can be used by the general users as well as data administrators. It contains the following information:
i) the structure of the contents of the data warehouse database,
ii) the source of the data,
iii) the data transformation processing requirements, such that, data can be passed
from the legacy systems into the data warehouse database,
iv) the process summarisation of data,
v) the data extraction history, and
vi) how the data needs to be extracted from the data warehouse.
Meta data has several roles to play and uses in the data warehouse system. For an end user, meta data directories also provide some additional information, such as what a particular data item would mean in business terms. It also identifies the information on reports, spreadsheets and queries related to the data of concern. All database management systems (DBMSs) have their own data dictionaries that serve a similar purpose. Information from the data dictionaries of the operational system forms a valuable source of information for the data warehouse’s meta data directory.
Q5. Describe the process of ELT for a data warehouse.
Ans. The first step in data warehousing is, to perform data extraction, transformation, and loading of data into the data warehouse. This is called ETL that is Extraction,
Transformation, and Loading. ETL refers to the methods involved in accessing and manipulating data available in various sources and loading it into a target data warehouse. Initially the ETL was performed using SQL programs, however, now there are tools available for ETL processes. The manual ETL was complex as it required the creation of a complex code for extracting data from many sources. ETL tools are very powerful and offer many advantages over the manual ETL. ETL is a step-by-step process. As a first step, it maps the data structure of a source system to the structure in the target data warehousing system. In the second step, it cleans up the data using the process of data transformation and finally, it loads the data into the target system.
The ETL is three-stage process. During the Extraction phase the desired data is identified and extracted from many different sources. These sources may be different databases or non-databases. Sometimes when it is difficult to identify the desirable data then, more data than necessary is extracted. This is followed by the Identification of the relevant data from the extracted data. The process of extraction sometimes, may involve some basic transformation.
The extraction process involves data cleansing and data profiling. Data cleansing can be defined as the process of removal of inconsistencies among the data. For example, the state name may be written in many ways also they can be misspelt too. For example, the state Uttar Pradesh may be written as U.P., UP, Uttar Pradesh, Utter Pradesh etc. The cleansing process may try to correct the spellings as well as resolve such inconsistencies.
One of the most time-consuming tasks - data transformation and loading follows the extraction stage. This process includes the following:
Use of data filters,
Data validation against the existing data,
Checking of data duplication, and
Information aggregation.
Transformations are useful for transforming the source data according to the requirements of the data warehouse. The process of transformation should ensure the quality of the data that needs to be loaded into the target data warehouse. Some of the common transformations are:
Filter Transformation: Filter transformations are used to filter the rows in a mapping that do not meet specific conditions. For example, the list of employees of the Sales department who made sales above Rs.50,000/- may be filtered out.
Joiner Transformation: This transformation is used to join the data of one or more different tables that may be stored on two different locations and could belong to two different sources of data that may be relational or from any other sources like XML data.
Aggregator Transformation: Such transformations perform aggregate calculations on the extracted data. Some such calculations may be to find the sum or average.
Sorting Transformation: requires creating an order in the required data, based on the application requirements of the data warehouse.
Q6. How can one gain competitive edge in business by using data warehouse?
Ans A data warehouse is an integrated collection of data and can help the process of making better business decisions. Several tools and methods are available to that enhances advantage of the data of data warehouse to create information and knowledge that supports business decisions. Two such techniques are Decision support systems and online analytical processing.
Decision Support Systems (DSS)
The DSS is a decision support system and NOT a decision-making system. DSS is a specific class of computerised information systems that support the decision-making activities of an organisation. A properly designed DSS is an interactive software based system that helps decision makers to compile useful information from raw data,
documents, personal knowledge, and/or business models to identify and solve
problems and make decisions.
A decision support system may gather or present the following information:
• Accessing current information from data warehouse or legacy databases or other
data resources.
• Presenting comparative sales figures of several months for an organisation.
• Creating projected revenue details based on new product sales assumptions.
• Demonstrating the consequences of different decision alternatives based on past experiences.
The DSS assists users in evaluating appropriate analysis or performing different types of studies on the datasets. For example, a spreadsheet can be used to store answers to a series of questionnaires in the form of Excel spreadsheets. This information then, can be passed on to decision makers.
On Line Analytical Processing (OLAP) is an approach for performing analytical
queries and statistical analysis of multidimensional data. OLAP tools can be put in the category of business intelligence tools along with data mining. Some of the typical applications of OLAP may include reporting of sales projections, judging the performance of a business, budgeting and forecasting etc.
OLAP tools require multidimensional data and distributed query-processing capabilities. Thus, OLAP has data warehouse as its major source of information and query processing. But how do OLAP tools work?
In an OLAP system a data analyst would like to see different cross tabulations by interactively selecting the required attributes. Thus, the queries in an OLAP are expected to be executed extremely quickly. The basic data model that may be supported by OLAP is the star schema, whereas, the OLAP tool may be compatible to a data warehouse.
OLAP Implementation
This classical form of OLAP implementation uses multidimensional arrays in the
memory to store multidimensional data. Such implementation of OLAP is also referred to as Multidimensional OLAP (MOLAP). MOLAP is faster as it stores data in an already processed aggregated data form using dimension and fact tables. The other important type of OLAP implementation is Relational OLAP (ROLAP), which stores data directly in the relational databases. ROLAP creates multidimensional views upon request rather than in advance as in MOLAP. ROLAP may be used on complex data with a wide number of fields.
Q7 Describe the steps involved in designing and implementation of Datawarehouse.
Ans. The data warehouse lifecycle model fundamentally can be defined as the model consisting of five major phases – design, prototype, deploy, operation and enhancement.
Let us introduce these terms:
1) Design: The design of database is to be done for available data inventories, DSS analyst requirements and analytical needs. It needs to produce a robust star schema or snowflake schema. Key activities in the design phase may include communication with the end users, finding the available catalogues, defining key performance and quality indicators, mapping of decision-making processes as per the information needs at various end user levels, logical and physical schema design etc.
2) Prototype: A data warehouse is a high cost project, thus, it may be a good idea to deploy it partially for a select group of decision-makers and database practitioners in the end user communities. This will help in developing a system that will be easy to accept and will be mostly as per the user’s requirements.
3) Deploy: Once the prototype is approved, then the data warehouse can be put to actual use. A deployed data warehouse comes with the following processes; documentation, training, maintenance.
4) Operation: Once deployed the data warehouse is to be used for day-to-day operations. The operation in data warehouse includes extracting data, putting it in database and output of information by DSS.
5) Enhancement: These are needed with the updating of technology, operating processes, schema improvements etc. to accommodate the change.
Data Warehouse Implementation
After the design of the data warehouse, the next step for building the data warehouse may be its implementation. Please remember that implementing a data warehouse is a very challenging process. It tests the ability of an organisation to adjust to change. The implementation of the data warehouse may require the following stages:
Implementation of Data Model: The data model that is to be implemented should be checked to ensure that it has the key entities and their interrelationships. It also should see that the system records of the data warehouse must be as per the data warehouse data model and should be possible best matches for the operational system data. The physical design should support the schema design.
Implementation of Data Transformation Programs: Now, the transformation programs that will extract and transform the data from the system of record should be implemented. They should be tested to load the required data in the data warehouse database.
Populating Data Warehouse and Maintenance: Once the data transformation programs are found to be ok, they can be used to populate the data warehouse. Once the data warehouse is operation at it needs to be maintained properly.
Q8. What are data marts? What is the significance of creating them?
Ans. Data marts can be considered as the database or collection of databases that are designed to help managers in making strategic decisions about business and the organisation. Data marts are usually smaller than data warehouse as they focus on some subject or a department of an organisation (a data warehouses combines databases across an entire enterprise). Some data marts are also called dependent data marts and may be the subsets of larger data warehouses.
A data mart is like a data warehouse and contains operational data that helps in making strategic decisions in an organisation. The only difference between the two is that data marts are created for a certain limited predefined application. Even in a data mart, the data is huge and from several operational systems, therefore, they also need a multinational data model.
A dependent data mart can be considered to be a logical subset (view) or a physical subset (extraction) of a large data warehouse. A dependent data mart may be isolated for the following reasons.
(i) For making a separate schema for OLAP or any other similar system.
(ii) To put a portion of the data warehouse or a separate machine to enhance performance.
(iii) To create a highly secure subset of data warehouse.
The data organisation of a data mart is a very simple star schema. A simple data mart may extract its contents directly from operational databases. However, in complex multilevel data warehouse architectures the data mart content may be loaded with the help of the warehouse database and Meta data directories.
BLOCK-3 UNIT-4
INTRODUCTION TO DATA MINING
Q1. What is data mining?
Ans. Data is growing at a phenomenal rate today and the users expect more sophisticated information from this data. There is need for new techniques and tools that can automatically generate useful information and knowledge from large volumes of data. Data mining is one such technique of generating hidden information from the data.
Data mining can be defined as: “an automatic process of extraction of non-trivial or implicit or previously unknown but potentially useful information or patterns from data in large databases, data warehouses or in flat files”.
Data mining is related to data warehouse in this respect that, a data warehouse is well equipped for providing data as input for the data mining process. The advantages of using the data of data warehouse for data mining are many some of them are listed below:
• Data quality and consistency are essential for data mining, to ensure, the accuracy of the predictive models. In data warehouses, before loading the data, it is first extracted, cleaned and transformed. We will get good results only if we have good quality data.
• Data warehouse consists of data from multiple sources. The data in data warehouses is integrated and subject oriented data. The data mining process performed on this data.
• In data mining, it may be the case that, the required data may be aggregated or summarised data. This is already there in the data warehouse.
• Data warehouse provides the capability of analysing data by using OLAP operations. Thus, the results of a data mining study can be analysed for hirtherto, uncovered patterns.
As defined earlier, data mining generates potentially useful information or patterns from data. In fact, the information generated through data mining can be used to create knowledge.
Q2. What is Knowledge Discovery in Databases (KDD)?
Ans Knowledge Discovery in Databases (KDD) is the process of finding useful information, knowledge and patterns in data while data mining is the process of using of algorithms to automatically extract desired information and patterns, which are derived by the Knowledge Discovery in Databases process.
The different steps of KDD are as follows:
• Extraction: Obtains data from various data sources.
• Preprocessing: It includes cleansing the data which has already been extracted by the above step.
• Transformation: The data is converted in to a common format, by applying some technique.
• Data Mining: Automatically extracts the information/patterns/knowledge.
• Interpretation/Evaluation: Presents the results obtained through data mining to the users, in easily understandable and meaningful format.
Q3. What are the tasks in KDD process?
Ans The different tasks in KDD are as follows:
• Obtains information on application domain: It gathers knowledge from the domain relevant to the user.
• Extracting data set: It includes extracting required data which will later, be used for analysis.
• Data cleansing process: It involves basic operations such as, the removal of noise, collecting necessary information to from noisy data, such as, deciding on strategies for handling missing data fields.
• Data reduction and projection: Using dimensionality reduction or transformation methods it reduces the effective number of dimensions under consideration.
• Selecting data mining task: In this stage we decide what the objective of the KDD process is. Whether it is classification, clustering, association rules etc.
• Selecting data mining method: In this stage, we decide the methods and the parameter to be used for searching for desired patterns in the data.
• Extraction of patterns: It includes searching for desired patterns only, because, the data-mining model may generate a lot of patterns.
• Interpretation and presentation of pattern/model.
Q4. What is the difference between data mining and OLTP?
Ans The query language of OLTP is well defined and it uses SQL for it, while, for data mining the query is poorly defined and there is no precise query language. The data used in OLTP is operational data while in data mining it is historical data. The output of the query of OLTP is precise and is the subset of the data while in the case of data mining the output is fuzzy and it is not a subset of the data.
Q5. What are the approaches to perform datamining?
Ans The approaches to data mining problems are based on the type of information/ knowledge to be mined. We will emphasis on three different approaches: Classification, Clustering, and Association Rules.
The classification task maps data into predefined groups or classes. The class of a
tuple is indicated by the value of a user-specified goal attribute. Tuples consists of a set of predicating attributes and a goal attribute. The task, is to discover, some kind of relationship between the predicating attributes and the goal attribute, so that, the discovered information/ knowledge can be used to predict the class of new tuple(s).
A few very simple examples to elucidate classification could be:
• Teachers classify students’ marks data into a set of grades as A, B, C, D, or F.
• Classification of the height of a set of persons into the classes tall, medium or short.
The task of clustering is to group the tuples with similar attribute values into the same class. Given a database of tuples and an integer value k, the Clustering is to define a mapping, such that, tuples are mapped to different cluster.
The principle is to maximise intra-class similarity and minimise the interclass similarity. In clustering, there is no goal attribute. So, classification is supervised by the goal attribute, while clustering is an unsupervised classification.
The task of association rule mining is to search for interesting relationships among items in a given data set. Its original application is on “market basket data”. The rule has the form X->Y, where X and Y are sets of items and they do not intersect. Each rule has two measurements, support and confidence. Given the user-specified minimum support and minimum confidence, the task is to find, rules with support and confidence above, minimum support and minimum confidence.
Q6. What is ID3 Algorithm for Classification?
Ans. This algorithm creates a tree using the algorithm given below and tries to reduce the expected number of comparisons.
Algorithm: ID3 algorithm for creating decision tree from the given training
data.
Input: The training data and the attribute-list.
Output: A decision tree.
Process:
Step 1: Create a node N
Step 2: If sample data are all of the same class, C (that is probability is 1 ) then return N as a leaf node labeled class C
Step 3: If attribute-list is empty
then return N as a leaf node label it with the most common class in
the training data; // majority voting
Step 4: Select split-attribute, which is the attribute in the attribute-list with the
highest information gain;
Step 5: label node N with split-attribute;
Step 6: for each known value Ai, of split-attribute // partition the samples
Create a branch from node N for the condition: split-attribute = Ai;
// Now consider a partition and recursively create the decision tree:
Let xi be the set of data from training data that satisfies the condition:
split-attribute = Ai
if the set xi is empty then
attach a leaf labeled with the most common class in the prior
set of training data;
else
attach the node returned after recursive call to the program
with training data as xi and
new attribute list = present attribute-list – split-attribute;
End of Algorithm.
Q7. What is clustering? How is clustering and segmentation related to data minging ? Explain partitioning clustering algorithm.
Ans. Clustering is grouping thing with similar attribute values into the same group. Given a database D={t1,t2,…,tn} of tuples and an integer value k, the Clustering problem is to define a mapping where each tuple ti is assigned to one cluster Kj, 1<=j<=k.
A Cluster, Kj, contains precisely those tuples mapped to it. Unlike the classification problem, clusters are not known in advance. The user has to the enter the value of the number of clusters k.
In other words a cluster can be defined as the collection of data objects that are similar in nature, as per certain defining property, but these objects are dissimilar to the objects in other clusters.
Some of the clustering examples are as follows:
• To segment the customer database of a departmental store based on similar buying patterns.
• To identify similar Web usage patterns etc.
Clustering is a very useful exercise specially for identifying similar groups from the given data. Such data can be about buying patterns, geographical locations, web information and many more.
Some of the clustering Issues are as follows:
• Outlier handling: How will the outlier be handled? (outliers are the objects that
do not comply with the general behaviour or model of the data) Whether it is to be considered or it is to be left aside while calculating the clusters?
• Dynamic data: How will you handle dynamic data?
• Interpreting results: How will the result be interpreted?
• Evaluating results: How will the result be calculated?
• Number of clusters: How many clusters will you consider for the given data?
• Data to be used: whether you are dealing with quality data or the noisy data? If, the data is noisy how is it to be handled?
• Scalability: Whether the algorithm that is used is to be scaled for small as well as large data set/database.
Partitioning Clustering
The partitioning clustering algorithms constructs k partitions from a given n objects of the data. Here k ≤ n and each partition must have at least one data object while one object belongs to only one of the partitions. A partitioning clustering algorithm normally requires users to input the desired number of clusters, k.
Some of the partitioning clustering algorithms are as follows:
• Squared Error
• K-Means
Squared Error Algorithms
The most frequently used criterion function in partitioning clustering techniques is the squared error criterion. The method of obtaining clustering by applying this approach is as follows:
Squared Error Clustering Method:
(1) Select an initial partition of the patterns with a fixed number of clusters and cluster centers.
(2) Assign each pattern to its closest cluster center and compute the new cluster centers as the centroids of the clusters. Repeat this step until convergence is achieved, i.e., until the cluster membership is stable.
(3) Merge and split clusters based on some heuristic information, optionally repeating step 2.
Some of the parameters that are used in clusters are as follows:
Q8. What is association rule mining? Explain the Apriori Algorithm.
Ans The task of association rule mining is to find certain association relationships among a set of items in a dataset/database. The association relationships are described in association rules. In association rule mining there are two measurements, support and confidence. The confidence measure indicates the rule’s strength, while support corresponds to the frequency of the pattern.
A typical example of an association rule created by data mining often termed to as
“market basket data” is: “ 80% of customers who purchase bread also purchase
butter.”
Apriori Algorithm: For finding frequent itemsets
The apriori algorithm applies the concept that if an itemset has minimum support, then all its subsets also have minimum support. An itemset having minimum support is called frequent itemset or large itemset. So any subset of a frequent itemset must also be frequent.
Apriori algorithm generates the candidate itemsets to be counted in the pass, by using only the large item set found in the previous pass – without considering the
transactions in the database.
It starts by finding all frequent 1-itemsets (itemsets with 1 item); then consider 2-
itemsets from these 1-itemsets, and so forth. During each iteration only candidates
found to be frequent in the previous iteration are used to generate a new candidate set during the next iteration. The algorithm terminates when there are no frequent
k-itemsets.
Notations that are used in Apriori algorithm are given below:
Apriori algorithm function takes as argument Lk-1 and returns a superset of the set of all frequent k-itemsets. It consists of a join step and a prune step. The Apriori algorithm is given below :
APRIORI
1. k = 1
2. Find frequent set Lk from Ck of all candidate itemsets
3. Form Ck+1 from Lk; k = k + 1
4. Repeat 2-3 until Ck is empty
Details about steps 2 and 3
Step 2: Scan the data set D and count each itemset in Ck , if it is greater
than minimum support, it is frequent
Step 3:
• For k=1, C1 = all frequent 1-itemsets. (all individual items).
• For k>1, generate Ck from Lk-1 as follows:
The join step
Ck = k-2 way join of Lk-1 with itself
If both {a1, …,ak-2, ak-1} & {a1, …, ak-2, ak} are in Lk-1, then
add {a1, …,ak-2, ak-1, ak} to Ck
(We keep items sorted).
The prune step
Remove {a1, …,ak-2, ak-1, ak} if it contains a non-frequent
(k-1) subset.
{In the prune step, delete all itemsets c∈ Ck such that some
(k-1)-subset of C is not in Lk-1.}
Q9. Write the applications of data mining problem.
Ans. Some of the applications of data mining are as follows:
• Marketing and sales data analysis: A company can use customer transactions in their database to segment the customers into various types. Such companies may launch products for specific customer bases.
• Investment analysis: Customers can look at the areas where they can get good returns by applying the data mining.
• Loan approval: Companies can generate rules depending upon the dataset they have. On that basis they may decide to whom, the loan has to be approved.
• Fraud detection: By finding the correlation between faults, new faults can be detected by applying data mining.
• Network management: By analysing pattern generated by data mining for the networks and its faults, the faults can be minimised as well as future needs can be predicted.
• Risk Analysis: Given a set of customers and an assessment of their riskworthiness, descriptions for various classes can be developed. Use these descriptions to classify a new customer into one of the risk categories.
• Brand Loyalty: Given a customer and the product he/she uses, predict whether the customer will change their products.
• Housing loan prepayment prediction: Rule discovery techniques can be used to accurately predict the aggregate number of loan prepayments in a given quarter as a function of prevailing interest rates, borrower characteristics and account data.
BLOCK-4 UNIT-1
EMERING DATABASE MODELS, TECHNOLOGY AND APPLICATIOS-1
Q1. What are knowledge databases?
Ans. Knowledge databases are the database for knowledge management. But what is knowledge management? Knowledge management is the way to gather, manage and use the knowledge of an organisation. The basic objectives of knowledge management are to achieve improved performance, competitive advantage and higher levels of innovation in various tasks of an organisation.
Knowledge is the key to such systems. Knowledge has several aspects:
• Knowledge can be implicit (called tacit knowledge) which are internalised or can be explicit knowledge.
• Knowledge can be captured before, during, or even after knowledge activity is conducted.
• Knowledge can be represented in logical form, semantic network form or database form.
• Knowledge once properly represented can be used to generate more knowledge using automated deductive reasoning.
• Knowledge may sometimes be incomplete. In fact, one of the most important aspects of the knowledge base is that it should contain upto date and excellent quality of information.
Simple knowledge databases may consist of the explicit knowledge of an organsiation including articles, user manuals, white papers, troubleshooting information etc. Such a knowledge base would provide basic solutions to some of the problems of the less experienced employees.
A good knowledge base should have:
• good quality articles having up to date information,
• a good classification structure,
• a good content format, and
• an excellent search engine for information retrieval.
Q2. Write short note on Deductive Databases and Semantic Databases.
Ans. A deductive database is a database system that can be used to make deductions from the available rules and facts that are stored in such databases. The following are the
key characteristics of the deductive databases:
• the information in such systems is specified using a declarative language in the form of rules and facts,
• an inference engine that is contained within the system is used to deduce new facts from the database of rules and facts,
• these databases use concepts from the relational database domain (relational calculus) and logic programming domain (Prolog Language),
• the variant of Prolog known as Datalog is used in deductive databases. The Datalog has a different way of executing programs than the Prolog and
• the data in such databases is specified with the help of facts and rules. For example, The fact that Rakesh is the manager of Mohan will be represented as:
Manager(Rakesh, Mohan) having the schema:
Manager(Mgrname, beingmangaed)
Similarly the following represents a rule:
Manager(Rakesh, Mohan) :- Managedby(Mohan, Rakesh)
• Please note that during the representation of the fact the data is represented using the attribute value only and not the attribute name. The attribute name determination is on the basis of the position of the data. For instance, in the example above Rakesh is the Mgrname.
• The rules in the Datalog do not contain the data. These are evaluated on the basis of the stored data in order to deduce more information.
Deductive databases normally operate in very narrow problem domains. These databases are quite close to expert systems except that deductive databases use, the database to store facts and rules, whereas expert systems store facts and rules in the main memory. Expert systems also find their knowledge through experts whereas deductive database have their knowledge in the data. Deductive databases are applied to knowledge discovery and hypothesis testing.
Semantic Databases
Information in most of the database management systems is represented using a simple table with records and fields. However, simple database models fall short of applications that require complex relationships and rich constructs to be represented using the database. Semantic modeling provides a far too rich set of data structuring capabilities for database applications. A semantic model contains far too many constructs that may be able to represent structurally complex inter-relations among data in a somewhat more natural way. Please note that such complex interrelationships typically occur in commercial applications.
Semantic modeling is one of the tools for representing knowledge especially in Artificial Intelligence and object-oriented applications. Thus, it may be a good idea to model some of the knowledge databases using semantic database system.
Some of the features of semantic modeling and semantic databases are:
• these models represent information using high-level modeling abstractions,
• these models reduce the semantic overloading of data type constructors,
• semantic models represent objects explicitly along with their attributes,
• semantic models are very strong in representing relationships among objects, and
• they can also be modeled to represent IS A relationships, derived schema and also complex objects.
Some of the applications that may be supported by such database systems in addition to knowledge databases may be applications such as bio-informatics, that require support for complex relationships, rich constraints, and large-scale data handling.
BLOCK-4 UNIT-2
EMERING DATABASE MODELS, TECHNOLOGY AND APPLICATIOS-1
Q1. What are mobile databases? Explain the characteristics of mobile databases.
Ans. In recent years, wireless technology has become very useful for the communication of information. Many new applications of wireless technology are already emerging such as electronic valets which allow electronic money anywhere, anytime, mobile cells, mobile reporting, etc. The availability of portable computing devices that supports wireless base a communication helps database users access relevant
information from anywhere, at anytime.
The basic framework for mobile computing
A mobile computing environment consists of:
• host Computers which are fixed,
• mobile support stations,
• mobile client units, and
• networks.
Please note that the basic network may be a wired network but there are possibilities
of Wireless LANs as well.
The following are the characteristics of mobile databases:
• Mobile database relies on the broadcast of data
• Mobile stations may be working in standalone mode most of the time
• The data on a mobile workstation may be inconsistent
• Mobile database may be made scalable
• Mobile database are closer to distributed database technology
• A mobile unit may be changing its physical location. It is to be reached at all locations.
A mobile support station covers a large geographic area and will service all the mobile hosts that are available in that wireless geographical area − sometimes referred to as the cell. A mobile host traverses many mobile zones or cells, requiring its information to be passed from one cell to another, not necessarily adjacent, as there is an overlapping of cells. However, with the availability of wireless LANS now, mobile hosts that are in some LAN areas may be connected through the wireless LAN rather than a wide area cellular network.Thus, reducing the cost of communication as well as overheads of the cell movement of the host.
With wireless LAN technology it is now possible that some of the local mobile hosts may communicate directly with each other without the mobile support station. However, please note that such a communication should be based on some standard protocol/technology. Fortunately, the Blue tooth standard is available. This standard allows wireless connectivity on short ranges (10-50 metres) and has nearly 1 megabytes per second speed, thus allowing easy use of PDA mobile phones and intelligent devices. Also there are wireless LAN standards such as 801.11 and 802.16. In addition, wireless technology has improved and packet based cellular networking has moved to the third generation or is even more advanced allowing high-speed digital data transfer and applications. Thus, a combination of all these technologies viz., blue tooth, wireless LANs and 3G cellular networks allows low cost infrastructure for wireless communication of different kinds of mobile hosts.
This has opened up a great potential area for mobile applications where large, realtime, low cost database applications can be created for areas such as, just in time accounting, teaching, monitoring of resources and goods etc. The major advantage here would be that the communication of real time data through these networks would now be possible at low costs.
Major drawback of mobile databases – is the limitation of power and available size of the display unit has found newer technologies like use of flash, power-saving disks, low-powered and power saving displays. However, the mobile devices since are normally smaller in size requires creation of presentation standards. One such protocol in the areas of wireless networking is the Wireless Access Protocol (WAP).
Q2. What is ODBC? What are the requirements of ODBC? Describe the components required for implementation of ODBC.
Ans Open Database Connectivity (ODBC)
Open Database Connectivity (ODBC) is a standard API (Application Programming Interface) that allows access to as database that is a part of any DBMS that supports this standard. By using ODBC statements in your program you may access any database in MS-Access, SQL Server, Oracle, DB2, even an Excel file, etc. to work with ODBC driver for each of the database that is being accessed from the ODBC. The ODBC allows program to use standard SQL commands for accessing database. Thus, you need not master the typical interface of any specific DBMS.
For implementing ODBC in a system the following components will be required:
• the applications themselves,
• a core ODBC library, and
• the database drives for ODBC.
The library functions as the transitory/ interpreter between the application and the database drivers. Database drivers are written to hide DBMS specific details. Such layered configurations allow you to use standard types and features in your DBMS applications without, knowing details of specific DBMS that the applications may encounter. It also simplifies the implementations of database driver as they need to know only the core library. This makes ODBC modular. Thus, ODBC provides the standard data access using ODBC drivers that exist for a large variety of data sources including drivers for non-relational data such as spreadsheet, XML files.
ODBC also has certain disadvantages. These are:
• if a large number of client machines require different drivers, and DLLs are to be connected through ODBC then it has a complex and large administration overhead. Thus, large organisations are on the lookout for server side ODBC technology.
• the layered architecture of ODBC may introduce minor performance penalty.
Connecting Database to ODBC
A database application needs to have the following types of statements for connecting to ODBC:
• linkage of core ODBC Library to client program,
• call results in communication to the request of the client library to the server, and
• results fetched at the client end.
But how do we actually write a code using ODBC? The following steps are needed to write a code using ODBC:
• establish the connection,
• run a SQL query that may be written by using embedded SQL, and
• release the connection.
Q3. What is JDBC?
Ans Java Database Connectivity (JDBC) provides a standard API that is used to access databases, regardless of the DBMS, through JAVA. There are many drivers for JDBC that support popular DBMSs. However, if no such driver exits for the DBMS that you have selected then, you can use a driver provided by Sun Microsystems to connect to any ODBC compliant database. This is called JDBC to ODBC Bridge. For such an application, you may need to create, an ODBC data source for the database before, you can access it from the Java application.
Connecting to a Database
In order to connect to a database, let us say an oracle database, the related JDBC driver has to be loaded by the Java Virtual Machine class loader successfully.
// Try loading the oracle database driver
try
{
Class.forName(“oracle.jdbc.driver.OracleDriver”).newInstance( ) ;
}
catch (ClassNotFoundException ce) // driver not found
{
System.err.println (“Drivernotfound”);
// Code to handle error
}
Q4. What is datagrid ? Show typical structure of datagrid. What are the application areas of datagrid ? Explain with an example.
Ans. A data grid can be seen as the process of creating a virtual database across hardware of almost the entire data that exists in some form. Thus, the key concept is Virtual Database. The basic tenet behind a data grid is that an application need not know either the place or the DBMS where the data is stored; rather the application is only interested in getting the correct results.
A data grid should address the following issues:
• It should allow data security and domain specific description of data. Domain specific data helps in the identification of correct data in response to a query.
• It should have a standard way of representing information. [The possible candidates in this category may be XML].
• It should allow simple query language like SQL for accessing information.
• The data requirements should be fulfilled with a level of confidence, (that is there has to be a minimum quality of service in place).
• There needs to be a different role assigned to the data administrator. The data administrators should not be concerned with what the data represent. Data domain specification should be the sole responsibility of the data owner. Unfortunately, this does not happen in the present database implementations.
• The separation of the data administration and the data manager will help the database administrator to concentrate on data replication and query performance issues based on the DBMS statistics.
Thus, a data grid virtualises data. Many DBMSs today, have the ability to separate the roles of the database administrator and the data owner from the application access.
This needs to be extended to the grid across a heterogeneous infrastructure.
An application written in a data grid, references a virtual data source with a specified quality of service. Such an application need not be compiled again even if the data moves from one server to another or, there is a change in the infrastructure or due to changes in the data access methods. This happens as in the data grid, data sources are transparent to the application. Thus, it moves the concept of data independence further up the ladder.
A data grid permits a data provider with facilities that need not explicitly mention the location and structure of current and future applications. This information can be published in the data dictionary or Registry. A grid middleware then, is needed, to query the registry in order to locate this information for the applications. An administrator in a data grid is primarily concerned with the infrastructure and its optimum uses and providing the required qualities of service. Some of the things that the administrator is allowed to do based on the statistics stored in the data dictionary includes, - enabling replication, failure recovery, partitioning, changing the infrastructure etc.
Data Grid Applications
A data grid includes most of the relational database capabilities including schema integration, format conversion of data, distributed query support etc. In addition, a data grid should be scalable, reliable and should support efficient file access. These things are not easy to do. However, in this sub-section let us try to define some of the applications that a data grid may have.
A Medical Grid: Consider a situation in which a patient is admitted to a hospital where s/he has no record. By querying the data grid on a key field (may be a voter’s id number) all the information about the previous medical history of the patient can be obtained using the data grid of hospitals. The data grid of hospitals may have their independent database systems, which is a part of the data grid. A hospital need not hand over all the confidential data as part of the data grid. Please note that the main feature here is that the hospital is in complete control of its data. It can change, hide, and secure any part of its own database while, participating in the data grid federation. Thus, a virtual medical database that is partitioned across hospitals can be made. Please note that a query can be run across the whole set of hospitals and can retrieve consolidated results. A query may not need to retrieve data from all the hospitals participating in the grid to get significant information, for example, a query about the symptoms of a disease that has been answered by 70 percent of the hospitals can return meaningful results. However, on the other hand some queries would require all the data grid members to participate. For instance, a query to find the patient's complete medical record wherever its parts are stored, would require all the hospitals to answer.
BLOCK-4 UNIT-3
POSTGRESQL
Q1. What is PostgreSQL? Discuss the salient features of PostgreSQL. What are the processes involved in the working of PostgreSQL?
Ans. PostgreSQL is an object relational database management system. It supports basic
object oriented features including inheritance and complex data types along with special functions to deal with these data types. But, basically most of it is relational. In fact, most users of PostgreSQL do not take advantage of its extensive object oriented functionality.
Following are the features of PostgreSQL that make it a very good DBMS:
:
PostgreSQL supports the following features:
• ANSI SQL 2 compliance,
• Support for transactions, triggers, referential integrity and constraints,
• High level language support,
• Inheritance, complex data types and polymorphism,
• Built in complex data types like IP address,
• Aggregate functions, collections and sequences,
• Portability, and
• ODBC and JDBC drivers.
PostgreSQL has the following three processes:
• Postmaster
• Server process
• Client processes
The single postmaster process manages the collection of a database (also called an installation or site) on a single host machine. The client applications that want access to a database stored at a particular installation make calls to the client interface library. The library sends user requests over the network to the postmaster, in turn starts a new backend server process. The postmaster then connects the client process to the new server. Exam this point onwards, the client process and the backend server process communicate with each other without any intervention on the part of the postmaster. Thus, the postmaster process is always running – waiting for requests from the new clients. Please note, the client and server processes will be created and destroyed over a period of time as the need arises.
Can a client process, make multiple connections to a backend server process? The libpq library allows a single client to make multiple connections to backend server processes. However, please note, that these client processes are not multi-threaded processes. At present the multithreaded front-end/backend connections are not supported by libpq. This client server or font-end/back-end combination of processes on different machines files that can be accessed on a client machine that permits may not be accessible (or may only be accessed using a different filename) on the database server machine.
Please, also note that the postmaster and postgres servers run with the user-id of the Postgres superuser or the administrator. Please also note, that the Postgres superuser does not have to be a special user and also that the Postgres superuser should definitely not be the UNIX superuser (called root). All the files related to database belong to this Postgres superuser.
BLOCK-4 UNIT-4
ORACLE
Q1.