git clone
Log | Files | Refs

commit 88612f9848db0b2dcf097e77874306c61dff6233
parent ed0be4f6393aab14cb862549f9419291bcef435b
Author: a3nm <>
Date:   Sun, 17 Jun 2018 01:17:18 +0200

basic database terminology

Basic database | 10++++++++++
1 file changed, 10 insertions(+), 0 deletions(-)

diff --git a/Basic database b/Basic database @@ -0,0 +1,9 @@ +# Signatures + +A **signature** $\sigma$ is a set of **relation names**, usually written with uppercase Latin letters ($R$, $S$, $T$, etc.), and a function that associates an **arity** to each relation. A relation of arity $1$ is called **unary**, a relation of arity $2$ is called **binary**, a relation of arity $3$ is called **ternary**, otherwise a relation of arity $i$ is called **$i$-ary**. + +# Instances + +Given a signature $\sigma$, a **fact** over $\sigma$ is an expression of the form $R(a_1, \ldots, a_n)$ where $R$ is a relation of $\sigma$, where $n$ is its arity, and where $a_1, \ldots, a_n$ are values. A **relational instance** $I$ (or **database**) over $\sigma$ is a set of **facts** over $\sigma$. We say that a fact **holds** in $I$ simply if it belongs to $I$. Another way to present relational instances is to see them as giving, for each relation name $R$ of $\sigma$ with arity $i$, a set of $i$-tuples called the **interpretation** of $R$ and often written $I^R$, which is the set of tuples $\mathbf{a}$ such that $R(\mathbf{a})$ holds in $I$. + +The **active domain** $\mathrm{dom}(I)$ of $I$ is the set of values that occur in facts of $I$. It is called *active* domain to distinguish it from the standard notion of domain in logic where a structure can contain elements that are not part of any interpretation, i.e., do not occur in any fact. The standard logical definition can be recovered in the database context up to adding to the signature a fresh unary relation $\mathrm{Dom}$ and rewritting instances to add a fact $\mathrm{Dom}(a)$ for all elements of the active domain and for all other elements that we wish to add to the domain without making them part of a fact of the original signature.+ \ No newline at end of file