User:Paolo Liberatore~enwiki/Relational structure

Kind of duplicate of Structure (mathematical logic); something may be merged there.

In database theory, a relational structure is a mathematical representation of a database, comprising a set of relations, each associated to a relation symbol from a given set of relational symbols. Relational structures are

A language is a set whose elements are called relation symbols; each relation symbol is associated an arity. Other names used for a language are similarity type, signature, and vocabulary. Given a language comprising $n$ relation symbols, a relational structure over $L$ is a tuple $A=(U,R_{1},\ldots ,R_{n})$ where $U$ is a set, called the universe, and $R_{1},\ldots ,R_{n}$ are $n$ relations over $U$; each $R_{i}$ is associated with a relation symbol of the language, and has the arity of that relation symbol.

Graphs are relational structures over a language comprising a single binary relation symbol, which represents the presence of an edge between two vertices. In other words, the language only contains a relation symbol $E$ of arity 2; a relational structure over this language is composed of a universe and a binary relation over the vertices; the universe is the set of nodes, and the relation contains the edges of the graph, that is, $(a,b)\in E$ means that nodes $a$ and $b$ are joined by an edge.

A Boolean formula in conjunctive normal form can also be seen as a relational structure over a language comprosing a unary relation symbol $V$ and two binary relation symbols $P$ and $N$. The universe contains the variables and the clauses; the relation associated with $V$ tells the variables and the clauses apart; the relations associated with $P$ and $N$ are used to represent the presence of a variable in a clause, either directly or negated.