Past exam of the computer science course of the University of Oxford 2015 Databases 3 d Solution 2026-10-31
Let contain the database attributes of , and let contain the given functional dependencies for . To compute the attribute closure , start with and repeatedly add for every functional dependency with , stopping when a full scan adds nothing.
Enumerate every . For each, test whether is not a superkey but becomes one on adding :If no enumerated passes both tests, return no. A direct implementation isIf a candidate key contains , choose . Minimality makes fail the superkey test while passes it, so the algorithm finds a witness.
for each subset X of attributes(R) minus {a}:
if closure(X, F) != attributes(R):
if closure(X union {a}, F) == attributes(R):
return yes
return noConversely, suppose an enumerated passes. Starting from , repeatedly discard any database attribute other than whose removal preserves the superkey property. The process terminates at a superkey minimal with respect to these deletions. Removing cannot leave a superkey: , and a subset of , which is not a superkey, cannot determine more database attributes than . Hence is a candidate key containing . The algorithm need not carry out this minimization to return the correct yes/no answer; it establishes why the witness test suffices.
For an explicit analysis of algorithms, let be the total encoded length of the functional dependencies, counting their left and right database attribute occurrences and delimiters. With Boolean membership arrays, one complete dependency scan costs . There are at most productive scans, followed by one unproductive scan, so a naive attribute closure costs . There are subsets and at most two attribute closure computations per subset. ThusThis is an exponential-time algorithm in the number of database attributes, not a polynomial-time claim. Subsets can be generated successively rather than stored all at once. The argument applies to functional dependencies within the database relation ; dependencies belonging to unrelated database relations do not constrain its candidate keys.
PostgreSQL 2026-11-05
PostgreSQL is an open-source object-relational database management system supporting SQL, database transactions, constraints and extensible data types. It manages stored relations and concurrent access through a server, rather than merely defining a database query language. The project descends from the Berkeley POSTGRES system.[ref]
What Is PostgreSQL? in the PostgreSQL documentation. Preface §1, origins and supported features
For example,
SELECT name FROM samples WHERE reading > 5 requests selected rows without prescribing their physical access path. A database index can accelerate retrieval, while database transactions govern the visibility and consistency of related updates. A database relation has no implicit presentation order: a caller needing sorted rows must request an ordering.[ref]Concepts in the PostgreSQL documentation. §2.2, relations, columns and unspecified row order
These distinctions separate logical results from storage organization and display. Relational algebra 2026-10-31
An algebra of operations on database relations. Classical relational algebra has relational selection, relational projection, relational join, Cartesian product, union and relational difference; database aggregation requires an extension.
Relational difference 2026-10-31
For two database relations with compatible database attributes, retains the database tuples in the first and absent from the second.
Relational division Created 2026-10-31 Updated 2026-11-05
Relational division expresses an all-required-matches query. Let be a database relation, the required values and an explicit candidate database relation. The desired result isIt can be constructed using Cartesian product, relational projection and relational difference:The inner relational difference contains missing required pairs. Its relational projection identifies failing candidates; removing them from proves the formula.
For example, can record scientific instrument/test pairs and the required tests. An scientific instrument with both pairs passes; one with only the heat pair does not. This is a universal quantifier requirement, unlike an ordinary relational join asking for some match.
When is empty, vacuous truth gives . Choosing is conventional but cannot recover candidates absent from ; use an independently stored scientific instrument database relation if those candidates must be included. Stating the candidate universe makes this edge case unambiguous.
Relational model Created 2026-10-31 Updated 2026-11-05
The relational model represents data as database relations, which are sets of database tuples over specified value domains. A relational schema names the database attributes and states database integrity constraints; an instance supplies their current values. Relational algebra describes operations on this logical data, while storage order, indexes and access paths belong to its implementation.
For example, the database relation
Reading(sample, value) can contain . A relational selection for values above five followed by relational projection onto sample identifiers returns . Changing the underlying file layout or adding an index need not change that query's meaning. Mathematical database relations have set semantics; SQL often uses bag semantics and has additional SQL NULL behavior.In his 1970 paper, E. F. Codd argued for data independence: application logic should not rely on particular stored orderings, indexes or navigational paths. His relational formulation made that separation central to database design.[ref]
Relational schema 2026-10-31
Names of database relations, their database attributes and value domains, together with applicable database integrity constraints.
Superkey 2026-10-31
A set of database attributes that determines every database attribute of a database relation under its database integrity constraints.
Tuple relational calculus 2026-11-05
Tuple relational calculus describes query answers by predicates over database tuples rather than a sequence of storage operations. A set-builder expression returns tuples satisfying a formula built from relation membership, attribute comparisons, logical connectives and quantifiers. For example,selects employee tuples whose salary exceeds100. A join can be expressed using existentially quantified tuples from two relations and equality of their shared identifying attribute.
The formula needs a safety restriction. Over an unrestricted infinite value universe, a query such as can demand infinitely many absent tuples. Safe tuple relational calculus restricts results to information grounded in the input and explicit constants. Under the usual finite-relation assumptions, its expressive power agrees with relational algebra. This gives a declarative query language while leaving the database system free to choose an efficient query plan.