Bag semantics 2026-10-31
Database query results may contain repeated records, with their multiplicities retained.
B+ tree Created 2026-10-31 Updated 2026-11-05
A B+ tree is a balanced search tree designed to keep each vertex in a storage database page. Internal vertices contain separator keys and child references; leaf vertices contain the indexed records or references to them. All leaves occur at the same depth, and linked leaves support ordered scans. PostgreSQL's index implementation illustrates this separation between leaf record references and internal downward references.[ref]
A large fan-out reduces storage accesses: with a fixed positive lower bound on nonroot internal fan-out, the height is . A database query first descends to the leaf containing a boundary key, then follows leaf links for a range. Separator keys guide navigation; their copies do not replace the leaf records.
For example, a root separator can direct keys below twelve to leaf and keys at least twelve to leaf . Searching for seventeen descends right. A range query from eight through seventeen starts in the left leaf and continues right. B+ tree node splits preserve the equal-depth structure as records are inserted.
Database Created 2026-10-31 Updated 2026-11-05
A database is an organized collection of data maintained for queries and updates. A database management system manages that collection, enforcing access rules and database integrity constraints. A relational database represents it through database relations, rather than exposing only an arbitrary collection of bytes in files.
For example, a laboratory can store biological sample identifiers, measurement values and scientific instrument identifiers as database tuples. A database query can select measurements above a threshold and join them to scientific instrument records. A foreign key can require every recorded scientific instrument identifier to name an existing scientific instrument. This makes the connection a maintained rule rather than a convention that every application must remember.
The logical relational schema and actual storage are distinct. A database query plan may use an index or scan database pages while returning the same specified result. Database transactions coordinate related updates, and database integrity constraints restrict the permitted states. PostgreSQL's documentation gives a concrete implementation in which named tables contain rows with named, typed columns and databases group tables.[ref]
Database index 2026-11-05
A database index is an auxiliary data structure that helps a database management system locate records satisfying selected conditions. It stores information organized for an access pattern, such as searching a column value, without requiring every database tuple to be inspected. The database query still specifies the result; the index supplies a possible route to it.[ref]
For example, a database relation with a million samples can have an index on sample_id. Looking for one identifier can follow a search structure instead of scanning all rows. A condition matching most rows may still favor a scan, since many separate lookups and row fetches can cost more. The index occupies storage and must be maintained on relevant updates. These costs explain why indexing every column is not automatically the best design.
A database management system is software that defines, stores, queries and updates databases while managing access, integrity and concurrent use. Its components can include a query parser, optimizer, storage manager, transaction manager and recovery mechanism. A database is the managed collection; the database management system supplies the mechanisms and interfaces used to operate on it.
For example, evaluating SELECT name FROM Person WHERE id = 7 requires interpreting the query, choosing an access path, retrieving visible records and returning the selected field. An index can speed the lookup without changing its logical result. Concurrent updates may require locks or versions, and a crash may require log replay. Merely writing records to a file does not supply those guarantees. PostgreSQL's tutorial illustrates the distinction between client applications, the server process managing database files and connections, and the databases accessed through that server.[ref]
Database query Created 2026-10-31 Updated 2026-11-05
A database query requests information computed from stored data. It can filter database tuples, project selected database attributes, combine database relations or aggregate groups. For example, a query can return the count of orders per customer rather than retrieving every order separately. The query specifies a result; a database query plan chooses operations for computing it. Equivalent result specifications can have very different costs under different indexes and data sizes. In SQL, duplicate rows and null values require conventions beyond the simplest mathematical relational algebra.
Database query optimization chooses a database query plan for a database query by comparing ways to obtain the required result. The choice includes the order of relational joins, use of a database index, and the algorithms implementing those relational joins. A cost model estimates work from quantities such as input sizes and storage accesses. The selected plan minimizes estimated cost among considered alternatives; this need not be the fastest possible plan in reality.[ref]
Consider a relational join of one million orders with customers, followed by a condition selecting ten customers. Applying the customer condition first can greatly shrink a join input. If a suitable database index locates those customers' orders, the engine may avoid scanning all orders. If almost all customers qualify, a sequential scan can instead be cheaper than many scattered index accesses. These are alternative ways of computing the same answer, not different meanings of the query.
Join order also matters with three or more inputs: an early join that creates a huge intermediate result can dominate the total work. Exhaustive search itself becomes expensive as the number of inputs grows. PostgreSQL therefore switches to a heuristic search above a configurable threshold. Inaccurate size estimates can favor a poor plan even when the search algorithm correctly minimizes its cost model.[ref]
Database query plan Created 2026-10-31 Updated 2026-11-05
A physical recipe for evaluating a database query, specifying scans, index accesses and implementations of relational joins and duplicate elimination.
Database query processing 2026-11-05
Database query processing is the sequence that turns a database query into returned results. In a typical SQL system, it includes parsing the text, checking names and types, rewriting the query when appropriate, database query optimization, and executing the chosen database query plan. Planning chooses operations; execution actually performs storage accesses, relational joins, filtering and aggregation.[ref]
For a request for each customer's total order value, the engine might scan orders, group their database tuples by customer identifier, sum the values and return one result per customer. An alternative plan can first restrict the orders using a database index. The result specification alone does not prescribe which access method performs the work.
A query against a stored database view illustrates why processing has more than a text-to-loop step. PostgreSQL can rewrite the reference into a query on the underlying tables before planning. The executor then walks the resulting plan and obtains rows from its operations. The distinction is useful when diagnosing a slow query: excessive planning work, a poor plan, and unexpectedly expensive execution are different causes even if the same statement triggered them.[ref]
Database query safety 2026-10-31
The requirement that a database query have a finite, appropriately range-restricted answer on finite input. In the usual domain-independent interpretation, extending the ambient value domain with unused values must not change the answer. The absence of a negation symbol alone does not ensure safety.
Database view 2026-11-05
A database view is a named database query that can be used much like a database relation. An ordinary view stores the query definition rather than a separate persistent copy of its result. Referring to the view evaluates that definition as part of the surrounding database query; changes in the underlying data can therefore change the view's result.[ref]
For example, an orders table might contain identifiers, totals and payment flags. The definition CREATE VIEW unpaid_orders AS SELECT id, total FROM orders WHERE paid = false; exposes the unpaid orders without requiring every application query to repeat the condition. If order 17 is marked paid, the next query of the ordinary view no longer includes that order, subject to the query's database transaction snapshot. Creating the view did not create another independent copy of order 17.
A view can hide storage and schema details behind a stable interface, supporting data independence. A materialized view instead stores results that require a refresh policy. Some ordinary views permit updates, but a view containing aggregation or certain joins may not identify a unique underlying row to change. Update behavior and access control are separate specifications; the word view alone does not guarantee that an arbitrary definition is writable or supplies a security boundary.[ref]
Data independence 2026-11-05
Data independence separates the logical meaning of stored data from details that an application need not know. Physical independence permits changing indexes, page layout or access paths without changing a query's meaning. Logical independence permits some changes in the database's logical organization while preserving the interface exposed to existing applications, often through views.
For example, a query asking for an employee's department should return the same answer after the database replaces a table scan with a B-tree index. An application that follows stored record addresses directly would instead depend on that representation. E. F. Codd's1970 relational model explicitly argued against dependencies on ordering, indexes and access paths.[ref] Independence does not mean every schema change is invisible: removing a field an application needs changes its contract unless another representation supplies equivalent information.
A database query has the same result when its ambient domain is extended while all input database relations are unchanged.
Domain relational calculus Created 2026-10-31 Updated 2026-11-05
Domain relational calculus describes a database query using first-order logic variables ranging over individual attribute values. A formula specifies which output tuples qualify, instead of prescribing a sequence of physical scans or joins. This differs from tuple relational calculus, whose variables range over whole database tuples.
For example, if records an scientific instrument identifier and a measurement value, then
returns identifiers with some recorded value above five. The existential quantifier binds , while is the output variable. Each returned identifier occurs in a stored database tuple, so extending the ambient domain by unused values cannot change the result.
The apparently simple query behaves differently: with unrestricted quantification, it can return every unused domain value as well as absent recorded values. Database query safety and domain independence of a database query formalize why a finite input must not silently turn such a query into an unbounded enumeration. A finite candidate relation gives the safer intended query .
E. F. Codd 2026-11-05
E. F. Codd introduced the relational model in his 1970 paper on large shared data banks. Data is represented by relations rather than application-visible pointers and access paths, supporting data independence: changing physical organization need not change the meaning of a query.[ref]
The distinction is operationally important. A query can request tuples satisfying a predicate while the system chooses an index or scan. Applications specify the information they need instead of navigating one fixed storage layout. Mathematical relations also expose dependencies among attributes, providing a foundation for database normalization.
Jeffrey Scott Vitter 2026-11-05
Jeffrey Scott Vitter coauthored the 2003 work on entropy-compressed text indexes with Roberto Grossi and Ankur Gupta. It develops compressed suffix-array representations and introduces a wavelet tree representation for symbol sequences. Bitvectors route a position through alphabet partitions, with rank queries translating that position into the selected subsequence. This connects compressed storage to efficient indexing rather than requiring full decompression for every query.[ref]
Materialized view 2026-11-05
A materialized view stores the result of a defining database query, allowing later queries to read the stored result. An ordinary database view retains the definition and evaluates it against the relevant underlying data when queried. A materialized view trades storage and maintenance work for potentially cheaper repeated reads; its freshness depends on when and how the result is maintained.[ref]
Suppose an orders table contains totals 10 and 20 for one customer. A materialized view defined by SELECT customer_id, SUM(total) AS total FROM orders GROUP BY customer_id stores 30 for that customer. Inserting a third order worth 7 changes the underlying sum to 37. In PostgreSQL, the previously stored 30 remains until a refresh replaces the result, for example with REFRESH MATERIALIZED VIEW customer_totals;. The stored answer can therefore be internally consistent yet out of date.
A dashboard that tolerates nightly updates can benefit from this arrangement, especially when the defining database query combines many rows. An application requiring the latest committed totals needs a suitable maintenance policy and database transaction semantics. The term materialized view alone does not promise automatic updates or an always faster query.[ref]
Multi-tenancy 2026-11-05
Multi-tenancy lets distinct consumers share a software service or computing infrastructure while retaining separate data and permitted operations. A tenant is the consumer or administrative grouping treated as one isolated customer. Resource pooling commonly assigns shared physical resources dynamically among tenants.[ref]
For example, two laboratories can use one hosted database application. Each laboratory's users must access only their permitted records, even when both laboratories' records occupy the same database relation. Checks on each database query and limits on resource use serve different purposes: data isolation does not prevent one tenant's expensive work from delaying another. Separate virtual machines are one possible implementation boundary, rather than a requirement of multi-tenancy.
Assume the two database queries have compatible output database attributes. Then
For a finite input database, the result of the relational difference is a subset of the finite result of , so it is finite and introduces no new values. For the usual domain independence of a database query, let be the input database and let be two ambient value domains containing its data and the query constants. Database query safety gives
and therefore
Although a domain relational calculus expression for the relational difference uses negation, its positive membership requirement in supplies the necessary range restriction. Negation is not by itself a reason for failure of database query safety.
The PostgreSQL Global Development Group is the collective project attribution used for the development and documentation of PostgreSQL, an open-source database management system. Its documentation specifies concrete behavior for database transactions, database integrity constraints, database query operations and storage mechanisms; these specifications are more precise than inferring behavior from SQL syntax alone.[ref]
For example, PostgreSQL documents transaction isolation levels in terms of visible snapshots and permitted anomalies. The project name here identifies the responsible development community, rather than one individual author or a separate database product.