git clone
Log | Files | Refs

Basic database (2298B)

      1 # Signatures
      3 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**.
      5 # Facts and atoms
      7 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. An **atom** is an expression of the form $R(x_1, \ldots, x_n)$ where the $x_1, \ldots, x_n$ are variables (though they are sometimes permitted to be constants). These two notions are essentially the same: the difference is that variables are expected to be quantified, whereas constants are used literally and refer to objects with that specific name.
      9 # Instances
     11 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$. Note that a database is not necessarily finite -- it can contain infinitely many facts, though finite databases are a frequent object of study (see for instance [Query answering under constraints]()).
     13 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.