Database theory encapsulates a broad range of topics related to the study and research of the theoretical realm of

database In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases spa ...

s and

database management system In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases span ...

s. Theoretical aspects of data management include, among other areas, the foundations of query languages,

computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...

and expressive power of queries,

finite model theory Finite model theory is a subarea of model theory. Model theory is the branch of logic which deals with the relation between a formal language (syntax) and its interpretations (semantics). Finite model theory is a restriction of model theory to inte ...

, database design theory,

dependency theory Dependency theory is the notion that resources flow from a " periphery" of poor and underdeveloped states to a " core" of wealthy states, enriching the latter at the expense of the former. A central contention of dependency theory is that poor ...

, foundations of

concurrency control In information technology and computer science, especially in the fields of computer programming, operating systems, multiprocessors, and databases, concurrency control ensures that correct results for concurrent operations are generated, while ...

and database recovery, deductive databases, temporal and spatial databases, real-time databases, managing

uncertain data In computer science, uncertain data is data that contains noise that makes it deviate from the correct, intended or original values. In the age of big data, uncertainty or data veracity is one of the defining characteristics of data. Data is consta ...

and

probabilistic database Most real databases contain data whose correctness is uncertain. In order to work with such data, there is a need to quantify the integrity of the data. This is achieved by using probabilistic databases. A probabilistic database is an uncertain da ...

s, and Web data. Most research work has traditionally been based on the

relational model The relational model (RM) is an approach to managing data using a structure and language consistent with first-order predicate logic, first described in 1969 by English computer scientist Edgar F. Codd, where all data is represented in terms of tup ...

, since this model is usually considered the simplest and most foundational model of interest. Corresponding results for other data models, such as object-oriented or semi-structured models, or, more recently, graph data models and

XML Extensible Markup Language (XML) is a markup language and file format for storing, transmitting, and reconstructing arbitrary data. It defines a set of rules for encoding documents in a format that is both human-readable and machine-readable. ...

, are often derivable from those for the relational model. A central focus of database theory is on understanding the complexity and power of query languages and their connection to

logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premis ...

. Starting from relational algebra and

first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quanti ...

(which are equivalent by Codd's theorem) and the insight that important queries such as

graph reachability In graph theory, reachability refers to the ability to get from one vertex to another within a graph. A vertex s can reach a vertex t (and t is reachable from s) if there exists a sequence of adjacent vertices (i.e. a walk) which starts with s and ...

are not expressible in this language, more powerful language based on

logic programming Logic programming is a programming paradigm which is largely based on formal logic Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of log ...

and fixpoint logic such as

datalog Datalog is a declarative logic programming language. While it is syntactically a subset of Prolog, Datalog generally uses a bottom-up rather than top-down evaluation model. This difference yields significantly different behavior and properties ...

were studied. Another focus was on the foundations of query optimization and

data integration Data integration involves combining data residing in different sources and providing users with a unified view of them. This process becomes significant in a variety of situations, which include both commercial (such as when two similar companies ...

. Here most work studied conjunctive queries, which admit query optimization even under constraints using the chase algorithm. The main research conferences in the area are the ACM Symposium on Principles of Database Systems (PODS) and the International Conference on Database Theory (ICDT).

References

General references

External links

* {{Database

Theory A theory is a rational type of abstract thinking about a phenomenon, or the results of such thinking. The process of contemplative and rational thinking is often associated with such processes as observational study or research. Theories may ...

See also

References

General references

External links