commit 3a464eda3c3d97c00656f7811e469a9de8cd554a
parent dc9d61381d4f221cd6ebe52f8215241d22938976
Author: a3nm <>
Date: Sun, 17 Jun 2018 01:22:12 +0200
facts and atoms
Diffstat:
1 file changed, 5 insertions(+), 1 deletion(-)
diff --git a/Basic database terminology.page b/Basic database terminology.page
@@ -2,8 +2,12 @@
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**.
+# Facts and atoms
+
+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.
+
# 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$. 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]()).
+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]()).
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
