HOME

TheInfoList



OR:

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 s ...
s and database management systems. Theoretical aspects of data management include, among other areas, the foundations of query languages, computational complexity and expressive power of queries, finite model theory, 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 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 ...
,
deductive database A deductive database is a database system that can make deductions (i.e. conclude additional facts) based on rules and facts stored in the (deductive) database. Datalog is the language typically used to specify facts, rules and queries in deductiv ...
s, temporal and
spatial database A spatial database is a general-purpose database (usually a relational database) that has been enhanced to include spatial data that represents objects defined in a geometric space, along with tools for querying and analyzing such data. Most s ...
s,
real-time database A real-time database is a database system which uses real-time processing to handle workloads whose state is constantly changing. This differs from traditional databases containing persistent data, mostly unaffected by time. For example, a stock ma ...
s, managing uncertain data and probabilistic databases, and Web data. Most research work has traditionally been based on the relational model, 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 model The semi-structured model is a database model where there is no separation between the data and the schema, and the amount of structure used depends on the purpose. The advantages of this model are the following: * It can represent the informati ...
s, 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 premise ...
. 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 quantifie ...
(which are equivalent by
Codd's theorem Codd's theorem states that relational algebra and the domain-independent relational calculus queries, two well-known foundational query languages for the relational model, are precisely equivalent in expressive power. That is, a database query can ...
) and the insight that important queries such as graph reachability 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. Any program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic pro ...
and
fixpoint logic In mathematical logic, fixed-point logics are extensions of classical predicate logic that have been introduced to express recursion. Their development has been motivated by descriptive complexity theory and their relationship to database query la ...
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 Query optimization is a feature of many relational database management systems and other databases such as NoSQL and graph databases. The query optimizer attempts to determine the most efficient way to execute a given query by considering the p ...
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 Chase or CHASE may refer to: Businesses * Chase Bank, a national bank based in New York City, New York * Chase Aircraft (1943–1954), a defunct American aircraft manufacturing company * Chase Coaches, a defunct bus operator in England * Chase Co ...
algorithm. The main research conferences in the area are the
ACM Symposium on Principles of Database Systems The ACM Symposium on Principles of Database Systems (PODS) is an international research conference on database theory, and has been held yearly since 1982. It is sponsored by three Association for Computing Machinery SIGs, SIGART, SIGACT, and S ...
(PODS) and the
International Conference on Database Theory The International Conference on Database Theory (ICDT) is an international research conference on foundations of database theory, and has been held since 1986. It is frequently also called the PODS of Europe. Since 2009, ICDT has been held joint ...
(ICDT).


See also

*
Conjunctive query In database theory, a conjunctive query is a restricted form of first-order queries using the logical conjunction operator. Many first-order queries can be written as conjunctive queries. In particular, a large part of queries issued on relational ...
* Expressive power


References


General references

* *
David Maier David Maier (born 2 June 1953) is the Maseeh Professor of Emerging Technologies in the Department of Computer Science at Portland State University. Born in Eugene, OR, he has also been a computer science faculty member at the State University of ...
, The Theory of Relational Databases. Copyright 1983 David Maier. Available at http://web.cecs.pdx.edu/~maier/TheoryBook/TRD.html


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 be ...