

![0_image_0.png](0_image_0.png)

G For each relationship R E R S such that rels(R) = [U 1 : E 1 , . . , U k : E k ], for each i E {1, . . , k}, for each entity E E E s such that E - s E i and for each instance e of E

$cmin_{\mathcal{S}}(E,R,U_{i})\leq\sharp\{r\in R^{\mathcal{B}}\mid r[U_{i}]=e\}\leq\mathit{cma}\,x_{\mathcal{S}}(E,R,U_{i})$.  
Notice that the definition of database state reflects the usual assumption in databases that database states are finite structures (see also Cosmadakis, Kanellakis, & Vardi, 1990). In fact, the basic domains are not required to be finite, but for each legal database state for a schema, only a finite set of values from the basic domains are actually of interest. We define the active domain Aget of a database state B as the set of all elements of the basic domains D BPP, D E Ds, that effectively appear as values of attributes in B. More formally:

$$\Delta_{a c t}^{B}=\{d\in D^{B\,p}\ |\ D\in{\mathcal{D}}_{S}\wedge\exists A\in{\mathcal{A}}_{S}\,,e\in\Delta^{B}\,.\,(e,d)\in A^{B}\}\,.$$

Since ∆ B is finite and A S contains only a finite number of attributes, which are functional by definition, also ∆ act is finite.

Reasoning in the ER model includes verifying entity satisfiability and deducing inheritance. Entity satisfiability amounts to checking whether a given entity can be populated in some legal database state (Atzeni & Parker Jr., 1986; Lenzerini & Nobili, 1990; Di Battista & Lenzerini, 1993), and corresponds to the notion of concept consistency in DLs. Deducing inheritance amounts to verifying whether in all databases that are legal for the schema, ery instance of an entity is also an instance of another entity. Such implied ISA relationships can arise for different reasons. Either trivially, through the transitive closure of the explicit ISA relationships present in the schema, or in more subtle ways, through specific patterns of cardinality restrictions along cycles in the schema and the requirement of the database state to be finite (Lenzerini & Nobili, 1990; Cosmadakis et al., 1990). Example 4.4 Figure 5 shows an ER schema modeling the same situation as the knowledge base of Example 2.2. Arguing exactly as in that example we can conclude that the two entities Number and Even denote the same set of elements in every finite database legal for the schema, although the ISA relation from Number to Even is not stated explicitly. It is implied, however, due to the cycle involving the relationship and the two entities and due to the particular form of cardinality constraints.

n