Database theory

Database theory

Database theory encapsulates a broad range of topics related to the study and research of the theoretical realm of databases 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, foundations of concurrency control and database recovery, deductive databases, temporal and spatial databases, real time databases, 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 models, or, more recently, graph data models and XML, 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. Starting from relational algebra and first-order logic (which are equivalent by Codd's theorem) and the insight that important queries such as graph reachability are not expressible in this language, more powerful language based on logic programming and fixpoint logic such as datalog were studied. Another focus was on the foundations of query optimization and data integration. 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

  • Serge Abiteboul, Richard B. Hull, Victor Vianu: Foundations of Databases. Addison-Wesley, 1995.

See also


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Dependency theory (database theory) — Dependency theory is a subfield of database theory which studies implication and optimization problems related to logical constraints, commonly called dependencies, on databases. The best known class of such dependencies are functional… …   Wikipedia

  • Superclass (database theory) — In database design and database theory, class organization is stratified into class hierarchies which use inheritance. Class hierarchies consist of superclasses and subclasses, in which each subclass has a one to many isa relationship with its… …   Wikipedia

  • Database design — is the process of producing a detailed data model of a database. This logical data model contains all the needed logical and physical design choices and physical storage parameters needed to generate a design in a Data Definition Language, which… …   Wikipedia

  • Database storage structures — Database tables/indexes are typically stored on hard disk in one of many forms, ordered/unordered Flat files, ISAM, Heaps, Hash buckets or B+ Trees. These have various advantages and disadvantages discussed in this topic. The most commonly used… …   Wikipedia

  • Database normalization — In the design of a relational database management system (RDBMS), the process of organizing data to minimize redundancy is called normalization. The goal of database normalization is to decompose relations with anomalies in order to produce… …   Wikipedia

  • Database — A database is an organized collection of data for one or more purposes, usually in digital form. The data are typically organized to model relevant aspects of reality (for example, the availability of rooms in hotels), in a way that supports… …   Wikipedia

  • Database schema — A depiction of MediaWiki database schema. A database schema (pronounced skee ma, /ˈski.mə/) of a database system is its structure described in a formal language supported by the database management system (DBMS) and refers to the organization of… …   Wikipedia

  • Database model — A database model is the theoretical foundation of a database and fundamentally determines in which manner data can be stored, organized, and manipulated in a database system. It thereby defines the infrastructure offered by a particular database… …   Wikipedia

  • Database catalog — The database catalog of a database instance consists of metadata in which definitions of database objects such as base tables, views (virtual tables), synonyms, value ranges, indexes, users, and user groups are stored.[1][2] The SQL standard… …   Wikipedia

  • Theory of relations — This article is about the theory of relations with regard to its specifically combinatorial aspects. For a general discussion of the basic definitions, see Binary relation and Finitary relation. The theory of relations treats the subject matter… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”