Relational databases are probably the most common type of database used for general-purpose tasks. In a relational database, information is grouped according to its type, generally in tables (see below). For example, in a database designed to hold fleet information you may include a table of employees and a table of vehicles.
- In addition to separating information according to its data structure, a relational database allows relationships to be created. A relationship defines a possible link between data types; the actual linkage of data is dependent upon the information held.
- Relational databases use the concept of normalization. Normalization is a design technique that minimizes the duplication of information. It also reduces the risk of errors. By using relationships, the duplication required can be lessened or eliminated completely.
A Relational model is the basis for any relational database management system (RDBMS). A relational model has mainly three components:
- A collection of objects or relations.
- Operators that act on the objects or relations.
- Data integrity methods.
Elements of a Relational Database Schema :
There are several key elements to a relational database. Each of these forms a part of the database's schema. The schema is the logical data model that determines the information that may be stored in the database and how it is to be arranged. To design a database we need three things:
- Table : A table is one of the most important ingredient to design the database. It is also known as a relation, and is a two dimensional structure used to hold related information. A database consists of one or more tables.
- Rows : A table contains rows. Rows are collection of instance of one thing.
- Columns : A table contains the columns. Columns contains all the information of a single type. Each column in a table is a category of information referred to as a field.
- Indexes : One of the greatest benefits of holding information in a database is the ability to quickly retrieve it. When querying a database, it is possible to apply criteria to ask for a specific set of rows.
- Keys : A primary key is a single column, or group of several columns (compound key), that can be used to uniquely identify rows in a table. Each table in a database may have a single primary key. Once defined, no two rows in the table may contain matching data in the primary key columns. Foreign keys are used when defining relationships between tables. A foreign key is a single column, or group of columns, in a table that reference the primary key in another table. This creates a link between the two tables.
- Constraints : Constraints are rules that are applied to the information in a database. These are usually used to enforce business rules upon the tabular data.
- Views : Views provide the useful concept of virtual tables. A view gathers specific information from one or more sources and presents it in the format of a single table. The information may be filtered within the view to remove unnecessary information.
- Stored Procedures : A stored procedure is a predefined set of statements that can be executed when required. Stored procedures provide the main means of creating programs within SQL Server databases.
Domain and Integrity Constraints :
* Domain Constraints
o limit the range of domain values of an attribute
o specify uniqueness and `nullness' of an attribute
o specify a default value for an attribute when no value is provided.
* Entity Integrity
o every tuple is uniquely identified by a unique non-null attribute, the primary key.
* Referential Integrity
o rows in different tables are correctly related by valid key values (`foreign' keys refer to primary keys).
Tuesday, September 8, 2009
Introduction to Relational Databases
Posted by
Sunflower
at
9/08/2009 08:16:00 PM
0
comments
Labels: Columns, Databases, keys, Relational databases, Relational model, Rows, Tables
|
| Subscribe by Email |
|
Monday, September 7, 2009
Database Normalization
Normalization is the process of efficiently organizing data in a database. There are two goals of the normalization process: eliminating redundant data (for example, storing the same data in more than one table) and ensuring data dependencies make sense (only storing related data in a table).
Database normalization can essentially be defined as the practice of optimizing table structures. Optimization is accomplished as a result of a thorough investigation of the various pieces of data that will be stored within the database, in particular concentrating upon how this data is interrelated. An analysis of this data and its corresponding relationships is advantageous because it can result both in a substantial improvement in the speed in which the tables are queried, and in decreasing the chance that the database integrity could be compromised due to tedious maintenance procedures.
Why Normalize?
- To reduce redundancy : One obvious drawback of data repetition is that it consumes more space and resources than is necessary. Redundancy introduces the possibility for error.
- Unforeseen Scalability Issues : as a database grows in size, initial design decisions will continue to play a greater role in the speed of and resources allocated to this database.
NORMAL FORMS :
The process towards database normalization progressing through a series of steps, typically known as Normal Forms.
- First Normal Form (1NF): A relation is in 1NF if and only if all underlying domains contain scalar values only. 1NF is often refered to the atomic rule. In a database, this means that each column should only be designed to hold one and only one piece of information.
- Second Normal Form (2NF): It further addresses the concept of removing duplicative data:
* Meet all the requirements of the first normal form.
* Remove subsets of data that apply to multiple rows of a table and place them in separate tables.
* Create relationships between these new tables and their predecessors through the use of foreign keys.
- Third Normal Form (3NF): It goes one large step further:
* Meet all the requirements of the second normal form.
* Remove columns that are not dependent upon the primary key.
- Fourth Normal Form (4NF): It has one additional requirement:
* Meet all the requirements of the third normal form.
* A relation is in 4NF if it has no multi-valued dependencies.
Posted by
Sunflower
at
9/07/2009 11:53:00 PM
0
comments
Labels: database normalization, Databases, Normal forms, Normalization
|
| Subscribe by Email |
|
Temporal Database Concepts
A temporal database is a database with built-in time aspects, e.g. a temporal data model and a temporal version of structured query language. More specifically the temporal aspects usually include valid-time and transaction-time. These attributes go together to form bitemporal data.
* Valid time denotes the time period during which a fact is true with respect to the real world.
* Transaction time is the time period during which a fact is stored in the database.
* Bitemporal data combines both Valid and Transaction Time.
- Temporal DBMS manages time-referenced data, and times are associated with database entities.
- Modeled reality.
- Database entities.
- Fact: any logical statement than can meaningfully be assigned a truth value, i.e., that is either true or false.
- Valid Time (vt).
- Valid time is the collected times when the fact is true.
- Possibly spanning the past, present & future.
- Every fact has a valid time.
- Transaction Time (tt).
- The time that a fact is current in the database.
- Maybe associated with any database entity, not only with facts.
- TT of an entity has a duration: from insertion to deletion.
- Deletion is pure logical operation.
- Time domain may be discrete or continuous.
- Typically assume that time domain is finite and discrete in database.
- Assume that time is totally ordered.
- Uniqueness of “NOW”.
- The current time is ever-increasing.
- All activities is happed at the current time.
- Current time separates the past from the future.
- “NOW” <> “HERE”.
- Time cannot be reused!
- A challenge to temporal database management.
Most applications of database technology are temporal in nature:
- Financial applications : portfolio management, accounting & banking.
- Record-keeping applications : personnel, medical record and inventory management.
- Scheduling applications : airline, car, hotel reservations and project management.
- Scientific applications : weather monitoring.
Posted by
Sunflower
at
9/07/2009 11:31:00 PM
0
comments
Labels: Data Model, Databases, Temporal Databases
|
| Subscribe by Email |
|
Sunday, September 6, 2009
Deductive Object-Oriented Databases
Deductive Object Oriented databases (DOODs) came about through the integration of the OO paradigm and logic programming. The following broad approaches have been adopted in the design of DOOD systems:
- Language Extension : An existing deductive language model is extended with object oriented features. For example, Datalog is extended to support identity, inheritance, and other OO features.
- Language Integration : A deductive language is integrated with an imperative programming language in the context of an object model or type system. The resulting system supports a range of standard programs, while allowing different and complementary programming paradigms to be used for different tasks, or for different parts of the same task.
- Language Reconstruction : An object model is reconstructed, creating a new logic language that includes object-oriented features. in this strategy, the goal is to develop an object logic that captures the essentials of the object-oriented paradigm and that can also be used as a deductive programming language in DOODs.
Validity combines deductive capabilities with the ability to manipulate complex objects. The ability to declaratively specify knowledge as deduction and integration rules brings knowledge independence. Moreover, the logic-based language of deductive databases enables advanced tools, such as those for checking the consistency of a set of rules, to be developed. VALIDITY provides the following :
- A DOOD data model and language, called DEL (Datalog Extended Language).
- An engine working along a client-server model.
- A set of tools for schema and rule editing, validation, and querying.
The DEL data model provides object-oriented capabilities, similar to those offered by the ODMG data model, and includes both declarative and imperative features. The declarative features include deductive and integrity rules, with full recursion, stratified negation, disjunction, grouping, and quantification. The imperative features allow functions and methods to be written.
Posted by
Sunflower
at
9/06/2009 11:40:00 PM
0
comments
Labels: Data Model, Deductive Databases, Object Oriented, validity
|
| Subscribe by Email |
|
What is the ARIES Recovery Algorithm ?
'Algorithms for Recovery and Isolation Exploiting Semantics', or ARIES is a recovery algorithm designed to work with a no-force, steal database approach; it is used by IBM DB2, Microsoft SQL Server and many other database systems.
Three main principles lie behind ARIES:
- Write ahead logging: Any change to an object is first recorded in the log, and the log must be written to stable storage before changes to the object are written to disk.
- Repeating history during Redo: On restart after a crash, ARIES retraces the actions of a database before the crash and brings the system back to the exact state that it was in before the crash. Then it undo the transactions still active at crash time.
- Logging changes during Undo: Changes made to the database while undoing transactions are logged to ensure such an action isn't repeated in the event of repeated restarts.
The ARIES recovery procedure consists of three main steps :
- Analysis : It identifies the dirty (updated) pages in the buffer and the set of transactions active at the time of crash. The appropriate point in the log where REDO operation should start is also determined.
- REDO phase : It actually reapplies updates from the log to the database. Generally the REDO operation is applied to only committed transactions. However, in ARIES, this is not the case. Certain information in the ARIES log will provide the start point for REDO, from which REDO operations are applied until the end of the log is reached. Thus only the necessary REDO operations are applied during recovery.
- UNDO phase : The log is scanned backwards and the operations of transactions that were active at the time of the crash are undone in reverse order. The information needed for ARIES to accomplish its recovery procedure includes the log, the transaction table, and the dirty page table. In addition, checkpointing is used.
DATA STRUCTURES USED IN ARIES RECOVERY ALGORITHM :
Log records contain following fields :
- LSN
- Type (CLR, update, special)
- TransID
- PrevLSN (LSN of prev record of this txn)
- PageID (for update/CLRs)
- UndoNxtLSN (for CLRs)
* indicates which log record is being compensated
* on later undos, log records upto UndoNxtLSN can be skipped
- Data (redo/undo data); can be physical or logical.
Transaction Table :
- Stores for each transaction:
* TransID, State.
* LastLSN (LSN of last record written by txn).
* UndoNxtLSN (next record to be processed in rollback).
- During recovery:
* Initialized during analysis pass from most recent checkpoint.
* Modified during analysis as log records are encountered, and during undo.
Dirty Pages Table
- During normal processing :
* When page is fixed with intention to update
"Let L = current end-of-log LSN (the LSN of next log record to be generated).
" if page is not dirty, store L as RecLSN of the page in dirty pages table.
* When page is flushed to disk, delete from dirty page table.
* Dirty page table written out during checkpoint.
* (Thus RecLSN is LSN of earliest log record whose effect is not reflected in page on disk).
- During recovery :
* Load dirty page table from checkpoint.
* Updated during analysis pass as update log records are encountered.
Checkpoints :
- Begin_chkpt record is written first.
- Transaction table, dirty_pages table and some other file mgmt information are written out.
- End_chkpt record is then written out.
* For simplicity all above are treated as part of end_chkpt record.
- LSN of begin_chkpt is then written to master record in well known place on stable storage.
- Incomplete checkpoint.
* if system crash before end_chkpt record is written.
- Pages need not be flushed during checkpoint
* They are flushed on a continuous basis.
- Transactions may write log records during checkpoint.
- Can copy dirty_page table fuzzily (hold latch, copy some entries out, release latch, repeat).
Posted by
Sunflower
at
9/06/2009 11:02:00 PM
0
comments
Labels: Algorithm, ARIES, ARIES recovery algorithm, Recovery
|
| Subscribe by Email |
|
Database Recovery Techniques - Overview
The main goal of recovery is to ensure the atomicity property of a transaction. If a transaction fails before completing its execution, the recovery mechanism has to make sure that the transaction has no lasting effects on the database. The different approaches to recovery :
- Deferred Update : These techniques postpone any actual updating of the database on disk until a transaction reaches its commit point. The transaction force writes the log to disk before recording the updates in the database. This approach, when used with certain concurrency control methods, is designed never to require transaction rollback, and recovery simply consists of redoing the operations of transactions committed after the last checkpoint from the log.
Disadvantage : Too much buffer space may be needed, since updates are kept in the buffers and are not applied to disk until a transaction commits.
Deferred update can lead to a recovery algorithm known as NO-UNDO/REDO. Immediate update techniques may apply changes to the database on disk before the transaction reaches a successful conclusion. Any changes applied to the database must be first recorded in the log and force-written to disk so that these operations can be undone if necessary.
- Another algorithm, known as UNDO/NO-REDO, can also be developed for immediate update if all transaction actions are recorded in the database before commit.
- There is another technique, called shadow paging technique, which keeps track of old database pages by using a shadow directory. This technique, which is classified as NO UNDO/NO-REDO, does not require a log in single-user systems but still needs the log for multiuser systems.
- ARIES, a specific recovery scheme is used in some of IBM's relational database products.
- Two-phase commit protocol is used for recovery from failures involving multi-database transactions.
- Recovery from catastrophic failures is typically done by backing up the database and the log to tape. The log can then be backed up more frequently than the database, and the backup log can be used to redo operations starting from the last database backup.
Posted by
Sunflower
at
9/06/2009 03:16:00 PM
1 comments
Labels: Databases, Deferred technique, Recovery Techniques, Shadow Paging
|
| Subscribe by Email |
|
How is shadow paging performed ?
Shadow paging is an alternative to log-based recovery techniques, which has both advantages and disadvantages. It may require fewer disk accesses, but it is hard to extend paging to allow multiple concurrent transactions. The paging is very similar to paging schemes used by the operating system for memory management.
How Shadow Paging is performed ?
- To commit a transaction :
* Flush all modified pages in main memory to disk.
* Output current page table to disk.
* Make the current page table the new shadow page table, as follows:
1. Keep a pointer to the shadow page table at a fixed (known) location on disk.
2. To make the current page table the new shadow page table, simply update the pointer to point to 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 technique:
- No overhead of writing log records.
- Recovery is trivial.
Disadvantages of shadow-page technique:
- Commit overhead : The commit of a single transaction using shadow paging requires multiple blocks to be output -- the current page table, the actual data and the disk address of the current page table. Log-based schemes need to output only the log records.
- Data fragmentation : Shadow paging causes database pages to change locations (therefore, no longer contiguous.
- Garbage collection : Each time that a transaction commits, the database pages containing the old version of data changed by the transactions must become inaccessible. Such pages are considered to be garbage since they are not part of the free space and do not contain any usable information. Periodically it is necessary to find all of the garbage pages and add them to the list of free pages. This process is called garbage collection and imposes additional overhead and complexity on the system.
Posted by
Sunflower
at
9/06/2009 03:06:00 PM
0
comments
Labels: Advantages, Databases, Disadvantages, Implemeted, pages, Shadow Paging
|
| Subscribe by Email |
|