Database
|
|
A database is a collection of information stored in a computer in a systematic way, such that a computer program can consult it to answer questions. The software used to manage and query a database is known as a database management system (DBMS). The properties of database systems are studied in information science.
At the core of the concept of a database is the idea of a collection of facts, or pieces of knowledge. Facts may be structured in a number of ways, known as data models. For instance, one model is to associate each fact with a record representing an entity (such as a person), and to arrange these entities into trees or hierarchies -- the hierarchical data model. Another model is to arrange facts into sets of values which satisfy logical predicates -- the relational model.
Strictly speaking, the "database" is the collection of facts and the software is the "database management system" or DBMS. However, in practice, many database administrators and programmers use the term "database" to cover both meanings.
Database management systems range from the extremely simple to the highly complex. Differences among DBMSes include whether they are capable of ensuring the integrity of the data; whether they may be used by many users at once; and what sorts of conclusions they can be programmed to compute from a set of data.
The first database management systems were developed in the 1960s. A pioneer in the field was Charles Bachman. Two key data models arose at this time: the network model (developed by CODASYL) followed by the hierarchical model (as implemented in IMS). These were later usurped by the relational model, which was contemporary with the so-called flat model designed for very small tasks. Another contemporary of the relational model is the object-oriented database (OODB).
While the relational model is based on set theory, one proposed modification suggests fuzzy set theory (based on fuzzy logic) as an alternative.
| Contents |
Database Models
Various techniques are used to model data structure. Certain models are more easily implemented by some types of database management systems than others. For any one logical model various physical implementations may be possible. An example of this is the relational model: In larger systems the physical implementation often has indexes which point to the data - this is similar to some aspects of common implementations of the network model. But in small relational databases the data is often stored in a set of files, one per table, in a flat, unindexed structure. There is some confusion below and elsewhere in this article as to logical data model vs its physical implementation.
Flat Model
The flat (or table) model consists of a single, two-dimensional array of data elements, where all members of a given column are assumed to be similar values, and all members of a row are assumed to be related to one another. For instance, columns for name and password might be used as a part of a system security database. Each row would have the specific password associated with a specific user. Columns of the table often have a type associated with them, defining them as character data, date or time information, integers, or floating point numbers. This model is the basis of the spreadsheet.
Network model
The network model allows multiple datasets to be used together through the use of pointers (or references). Some columns contain pointers to different tables instead of data. Thus, the tables are related by references, which can be viewed as a network structure. A particular subset of the network model, the hierarchical model, limits the relationships to a tree structure, instead of the more general directed graph structure implied by the full network model.
Relational model
The relational model was introduced in an academic paper (http://www.acm.org/classics/nov95/toc.html) by E. F. Codd in 1970 as a way to make database management systems more independent of any particular application. It is a mathematical model defined in terms of predicate logic and set theory.
Although the basic idea of a relational database has been very popular, relatively few people understand the mathematical definition and only a few, obscure DBMSs implement it completely and without extension. An Oracle database, for example, can be used in a purely relational way, but it also allows tables to be defined that allow duplicate rows -- an extension (or violation) of the relational model. In common English usage, a DBMS is called relational if it supports relational operations, regardless of whether it enforces strict adherence to the relational model. The following is an informal, non-technical explanation of how "relational" database management systems commonly work.
A relational database contains multiple tables, each similar to the one in the "flat" database model. However, unlike network databases, the tables are not linked by pointers. Instead, keys are used to match up rows of data in different tables. A key is just one or more columns in one table that correspond to columns in other tables. Any column can be a key, or multiple columns can be grouped together into a single key. Unlike pointers, it is not necessary to define all the keys in advance; a column can be used as a key even if it was not originally intended to be one.
A key that can be used to uniquely identify a row in a table is called a unique key. Typically one of the unique keys is the preferred way to refer to row; this is defined as the table's primary key.
When a key consists of data that has an external, real-world meaning (such as a person's name, a book's ISBN, or a car's serial number), it's called a "natural" key. If no natural key is suitable (think of the many people named Brown), an arbitrary key can be assigned (such as by giving employees ID numbers). In practice, most databases have both generated and natural keys, because generated keys can be used internally to create links between rows that cannot break, while natural keys can be used, less reliably, for searches and for integration with other databases. (For example, records in two independently developed databases could be matched up by social security number, except when the social security numbers are incorrect, missing, or have changed.)
Relational Operations
You request data from a relational database by sending it a query that is written in a special language, usually a dialect of SQL. Although SQL was originally intended for end-users, it is much more common for SQL queries to be embedded into software that provides an easier user interface. (Many web sites perform SQL queries when generating pages.)
In response to a query, the database returns a result set, which is just a list of rows containing the answers. The simplest query is just to return all the rows from a table, but more often, the rows are filtered in some way to return just the answer wanted.
Often, data from multiple tables gets combined into one, by doing a join. Conceptually, this is done by taking all possible combinations of rows (the "cross-product"), and then filtering out everything except the answer. In practice, relational database management systems rewrite ("optimize") queries to perform faster, using a variety of techniques.
The flexibility of relational databases allows programmers to write queries that were not anticipated by the database designers. As a result, relational databases can be used by multiple applications in ways the original designers did not foresee, which is especially important for databases that might be used for decades. This has made the idea and implementation of relational databases very popular with businesses.
Implementations and indexing
All of these kinds of database can take advantage of indexing to increase their speed. The most common kind of index is a sorted list of the contents of some particular table column, with pointers to the row associated with the value. An index allows a set of table rows matching some criterion to be located quickly. Various methods of indexing are commonly used; b-trees, hashes, and linked lists are all common indexing techniques.
Relational DBMSs have the advantage that indices can be created or dropped without changing existing applications, because applications don't use the indices directly. Instead, the database software decides on behalf of the application which indices to use. The database chooses between many different strategies based on which one it estimates will run the fastest.
Relational DBMSs utilise many different algorithms to compute the result of an SQL statement. The RDBMs will produce a plan of how to execute the query, which is generated by analysing the run times of the different algorithms and selecting the quickest. Some of the key algorithms that deal with joins are Nested Loops Join, Sort-Merge Join and Hash Join.
Mapping objects into databases
In recent years, the object-oriented paradigm has been applied to databases as well, creating a new programming model known as object databases. These databases attempt to overcome some of the difficulties of using objects with the SQL DBMSs. An object-oriented program allows objects of the same type to have different implementations and behave differently, so long as they have the same interface (polymorphism). This doesn't fit well with a SQL database where user-defined types are difficult to define and use, and where the Two Great Blunders prevail: the identification of classes with tables (the correct identification is of classes with types, and of objects with values), and the usage of pointers.
A variety of ways have been tried for storing objects in a database, but there is little consensus on how this should be done. Implementing object databases undo the benefits of relational model by introducing pointers and making ad-hoc queries more difficult. This is because they are essentially adaptations of obsolete network and hierarchical databases to object-oriented programming. As a result, object databases tend to be used for specialized applications and general-purpose object databases have not been very popular. Instead, objects are often stored in SQL databases using complicated mapping software. At the same time, SQL DBMS vendors have added features to allow objects to be stored more conveniently, drifting even further away from the relational model.
Applications of databases
Databases are used in many applications, spanning virtually the entire range of computer software. Databases are the preferred method of storage for large multiuser applications, where coordination between many users is needed. Even individual users find them convenient, though, and many electronic mail programs and personal organizers are based on standard database technology.
Transactions and concurrency
In addition to their data model, most practical databases ("transactional databases") attempt to enforce a database transaction model that has desirable data integrity properties. Ideally, the database software should enforce the ACID rules, summarised here:
- Atomicity - Either all the tasks in a transaction must be done, or none of them. The transaction must be completed, or else it must be undone (rolled back).
- Consistency - Every transaction must preserve the integrity constraints -- the declared consistency rules -- of the database. It cannot place the data in a contradictory state.
- Isolation - Two simultaneous transactions cannot interfere with one another. Intermediate results within a transaction are not visible to other transactions.
- Durability - Completed transactions cannot be aborted later or their results discarded. They must persist through (for instance) restarts of the DBMS after crashes.
In practice, many DBMS's allow most of these rules to be selectively relaxed for better performance.
Concurrency control is a method used to ensure transactions are executed in a safe manner and follows the ACID rules. The DBMS must be able to ensure only serializable, recoverable schedules are allowed, and that no actions of committed transactions are lost while undoing aborted transactions.
The Database State
While databases are a vital tool of modern life, concerns are growing over the privacy and civil liberties issues that result, particularly with governments using increasingly larger interlinked databases with their potential for mass surveillance in what has been termed by some the 'Database State'.
See also
- CDDB
- Client-Server
- Database dump
- Database management system
- Data Manipulation Language
- Database normalization
- Databases in the United Kingdom Government
- Distributed database
- Entity-relationship model
- Flat file database
- Hierarchic Database
- Internet Movie Database
- Java Database Connectivity
- Key field
- Main Memory database
- OLAP
- Recordset : dynaset, snapshot
- Relational model
- SQL (Structured Query Language)
- Object database
- Important publications in databases
- Redundancy (databases)
- Software engineering and List of software engineering topics
- Temporal database
References
- CNET News.com article, Study: Open-source databases going mainstream (http://news.com.com/2100-7344_3-5171543.html?part=rss&tag=feed&subj=news)
- Sandro Nielsen: Lexicographical Basis for an Electronic Bilingual Accounting Dictionary: Theoretical Considerations (http://www.sprog.asb.dk/sn/lexicographicalbasis.htm)
- Database @ sourceforge.net (http://sourceforge.net/softwaremap/trove_list.php?form_cat=66)
- Open Source database comparison (http://www.geocities.com/mailsoftware42/db/index.html)af:Databasis
ca:Base de dades cs:Databáze da:Database de:Datenbank es:Base de datos eo:Datumbazo fr:Base de données gl:Base de datos ia:Base de datos it:Database he:בסיס נתונים lv:Datu bāze nl:Database ja:データベース pl:Baza danych pt:Banco de dados ro:Bază de date ru:База данных sk:Databáza sl:Podatkovna baza fi:Tietokanta sv:Databas tl:Database th:ฐานข้อมูล vi:Cơ sở dữ liệu uk:База даних zh:数据库