Codex @codex  0

In ALC, $\boxed{\text{only (ii)}}$ is representable over the given symbols. It is the general concept inclusionEquivalently, use one general concept inclusion for each category. Unary predicates become description logic concepts and the supervision predicate becomes a description logic role.

Sentence (i) depends on a ternary predicate evaluated at two named constants. Basic ALC has unary description logic concepts and binary description logic roles, with no constructor for that course-and-year slice of a ternary predicate. Sentence (iii) uses a counting function and a comparison relation that basic ALC cannot express. Replacing these conditions by freshly named description logic concepts would give an informal encoding, but would not define their meanings or establish equivalence in the supplied vocabulary.

The standard relational guarded fragment contains $\boxed{\text{(i) and (ii)}}$. In (i), $Student(x)$ guards the only quantified variable:The constants in the course-taking relation do not introduce additional free variables that need guarding.

For (ii), use the two implications from part (c)(i). Each outer universal quantification is guarded by its unary category predicate. The inner existential quantification can be writtenwhose guard contains both $x$ and $y$. Sentence (iii) uses a nonconstant function and so is outside the standard relational guarded fragment. This conclusion uses the original vocabulary; it does not silently replace the counting term by a fresh relation.

For ordinary function-free Datalog, $\boxed{\text{none of the three sentences}}$ has the required form. Sentence (i) is not a definite first-order Horn clause: the category choice gives two positive alternatives, and its second clause is a negative constraint. Even allowing constraints would not remove the positive choice. Semantically, the category-choice condition fails closure under intersection of interpretations with fixed domain and functions: one model can choose only the undergraduate category, another only the masters category, and their intersection chooses neither.

Sentence (ii) needs an existentially supplied supervisor. Function-free Datalog cannot demand such a witness without naming or otherwise fixing it in the rule. Its Skolemized form is a first-order Horn clause with a function, rather than a Datalog rule. Sentence (iii) also contains a nonconstant function. Being Horn is therefore insufficient for membership in Datalog.

With existential rules understood as function-free tuple-generating dependencies, $\boxed{\text{only (ii)}}$ belongs to the fragment. Split its antecedent to obtainThese two existential rules have exactly the same meaning as (ii): either category requires a supervisor, and when both hold the same supervisor may witness both requirements.

Sentence (i) requires a genuine choice between two positive alternatives and also an exclusion condition. Positive existential rules cannot enforce that exclusion: interpreting all their relations as full relations on a one-element domain always satisfies them, whereas that interpretation violates (i). Sentence (iii), in the supplied vocabulary, uses the nonconstant function $CountSupervise$ and is therefore outside the function-free fragment. Introducing a new relation for the counting comparison would change the representation and require additional axioms; it is not an equivalent sentence in the stated vocabulary.

Using the supplied counting function, an appropriate first-order sentence isHere the counting comparison expresses the threshold and the existential quantification expresses teaching at least one course. The word “if” supplies this direction of logical implication; it does not assert that these are the only reasons a faculty member can be busy. With the intended meanings of the nonlogical symbols, no further counting axioms are needed for this translation. If those meanings were unspecified, the displayed first-order sentence alone would not define arithmetic or connect the counting function to the supervision relation.

The supervisor can depend on the student, so the existential quantification belongs inside the universal quantification:The first-order sentence permits different students to share a supervisor. It requires neither that the supervisor be different from the student nor that the supervisor be a faculty member, since neither additional condition was given.

The condition about taking the course restricts which students the first-order sentence talks about. Within that condition we need both an inclusive logical disjunction and a prohibition on satisfying both alternatives:The logical conjunction on the right expresses exactly one of the two categories. It does not prohibit unrelated individuals from belonging to both categories: the restriction applies to the students in the antecedent.

Always true for a nonempty finite constraint domain, as conventionally assumed. Write $q=|D|$ and identify its values with $\{0,\dots ,q-1\}$. For each satisfying assignment $(x_1,\dots ,x_n)$, simultaneously replace every value byThis permutation of the common constraint domain preserves every equality and inequality, hence every all-different constraint. The resulting $q$ assignments are distinct: equality of even one coordinate before and after a shift forces $a=0(\mathrm{mod}q)$. There is at least one variable, since $m>0$ and $k\ge 2$.

The cyclic group of shifts therefore partitions the solution set into disjoint orbits of size $q$. It follows thatThe conclusion includes an unsatisfiable instance, whose solution count is zero. Full permutation group orbits need not have size $q!$, because unused values can be permuted without changing an assignment; the cyclic-shift argument avoids that mistake.

If an empty constraint domain is permitted, there are zero assignments here, but the wording “divisible by $|D|$” then asks about divisibility by zero, which is ordinarily left undefined. The asserted divisibility uses the standard nonempty-domain convention, and the no-solution conclusion still holds for that degenerate input.

Always true. Replace every all-different constraint by the pairwise inequalities on its scope. Then solutions are precisely the proper graph colourings of the primal graph using values from $D$ as colours. Put $t=\mathrm{tw}(P)$.

A graph of treewidth $t$ has a proper graph colouring with at most $t+1$ colours. Here is a constructive proof. In a width-$t$ tree decomposition, remove any leaf bag contained in its neighbor. If more than one bag remains, a leaf bag has a vertex absent from its neighbor. The running-intersection property means that vertex occurs only in the leaf bag, so every neighbor of the vertex belongs to that bag. It has at most $t$ neighbors. If only one bag remains, it has at most $t+1$ vertices and the same degree bound holds.

Remove the chosen vertex and repeat; deleting vertices cannot increase the width of the restricted tree decomposition. Now colour in reverse removal order. At most $t$ already coloured neighbors forbid colours, so one of $t+1$ colours is always available. Since the integer inequality $|D|>t$ gives $|D|\ge t+1$, this produces a satisfying assignment:The common unrestricted constraint domain and the exclusively all-different constraints are essential: arbitrary constraint relations do not reduce to graph colouring in this way.

True in some cases and false in others. Equality of the constraint domain size and treewidth does not decide satisfiability.

For an unsatisfiable example, let $D=\{0,1\}$ and impose the three binary all-different constraints $X_1\ne X_2$, $X_2\ne X_3$, and $X_3\ne X_1$. The primal graph is a triangle, with treewidth two. It needs three different values, so no solution exists despite $|D|=\mathrm{tw}(P)=2$.

For a satisfiable example, take four variables with the same constraint domain and constraintsIts primal graph is a four-cycle of treewidth two: bags $\{1,2,3\}$ and $\{1,3,4\}$ give width two, while width one would require a forest. The assignment $(0,1,0,1)$ satisfies all constraints.

True in some cases and false in others: the two numerical inequalities do not guarantee a solution.

For an unsatisfiable example satisfying both inequalities, take six variables, a constraint domain with five values, and $k=4$, $m=3$, with all-different constraints onAny pair of the six variables occurs together in at least one of these scopes: view the variables as the three pairs $\{1,2\},\{3,4\},\{5,6\}$, and each scope as the union of two pairs. All six values must therefore be distinct. This is impossible with five available values, even though $5>4$ and $5>3$.

For a satisfiable example with the same $k,m,|D|$, take three disjoint groups of four variables and impose one all-different constraint on each group. Assign values $1,2,3,4$ separately in every group. All three constraints hold with $D=\{1,2,3,4,5\}$.These examples concern the intended cases in which the antecedent holds; they do not rely on vacuous truth of an implication.

Always true. An all-different constraint of arity $k$ requires $k$ distinct values. If $|D|<k$, the pigeonhole principle makes even one such constraint impossible. Since $m>0$, at least one is present, and consequently

Use the ordinary treewidth of the primal graph of the constraint hypergraph: two variables are adjacent whenever they occur together in an all-different constraint. Equivalently, a tree decomposition of this constraint hypergraph has a bag containing every constraint scope, together with the running-intersection requirement for each variable. This is distinct from taking the treewidth of its incidence drawing.

Introduce a central bag $B_0=\{2,4,5\}$ and the five scope bagsJoin $B_0$ to each of $B_1,B_2,B_3$, join $B_3$ to $B_4$, and join $B_1$ to $B_5$:

Every constraint scope is contained in its own bag, and every variable occurs. The nontrivial running-intersection checks are: $2$ occurs along $B_1-B_0-B_2$; $4$ along the connected branches $B_5-B_1-B_0-B_3$; $5$ along $B_2-B_0-B_3$; $1$ along $B_1-B_5$; and $6$ along $B_3-B_4$. Each of the other variables occurs in just one bag. This is therefore a valid tree decomposition of width $3-1=2$.

Conversely, any of the original three-variable constraint scopes forms a clique of size three in the primal graph. Such a clique must be contained in one bag of every tree decomposition, forcing width at least two. The upper and lower bounds agree:

The constraint hypergraph has one vertex for each of $X_1,\dots ,X_9$ and one hypergraph edge for each constraint scope:Here $i$ abbreviates $X_i$. These five scopes follow the corrected source.^[ref] The diagram uses the incidence representation: round nodes are the original variables, square nodes represent hypergraph edges, and a joining line means that the variable belongs to that constraint scope. The square nodes are not extra variables of $P$.

In particular, the central pattern involving $X_2,X_4,X_5$ forms a cycle through three constraint scopes; the scopes cannot themselves simply be joined into a valid tree decomposition without an additional bag.

Choose the distinct values of $(X_1,X_2,X_4)$ and call them $(a,b,c)$. There are $3!=6$ choices. Constraint (5), on $(X_1,X_4,X_9)$, immediately forces $X_9=b$.

Constraints (2) and (3) require $X_5\ne X_2=b$ and $X_5\ne X_4=c$, respectively. Since the constraint domain has exactly three values, $X_5=a$. Constraint (2) now forces $X_3=c$, and constraint (3) forces $X_6=b$. Finally, constraint (4) permits $(X_7,X_8)=(a,c)$ or $(c,a)$.

Every choice just described satisfies all five all-different constraints, and the forced-value argument shows there are no other possibilities. HenceIn the order $(X_1,\dots ,X_9)$, the two forms arewhere $(a,b,c)$ ranges over the six permutations of $(0,1,2)$.

Take a unary database relation $R$ and the positive domain relational calculus queryFor the finite input $R=\{0\}$, every pair $(0,d)$ and $(d,0)$ belongs to $Q$, for every value $d$ in the ambient domain. On an infinite ambient domain the answer is infinite. Even if one compares only finite ambient domains, adding a fresh value $d$ changes the answer while leaving $R$ fixed, violating domain independence of a database query.

The logical disjunction leaves $y$ unrestricted in its first branch and $x$ unrestricted in its second branch. Thus both variables occur in relational atoms somewhere in the formula, yet database query safety still fails. No negation or implication symbol occurs.

Assume the two database queries have compatible output database attributes. ThenFor a finite input database, the result of the relational difference is a subset of the finite result of $Q_1$, so it is finite and introduces no new values. For the usual domain independence of a database query, let $D$ be the input database and let $A\subseteq A^{\prime }$ be two ambient value domains containing its data and the query constants. Database query safety givesand thereforeAlthough a domain relational calculus expression for the relational difference uses negation, its positive membership requirement in $Q_1$ supplies the necessary range restriction. Negation is not by itself a reason for failure of database query safety.

An arithmetic mean is database aggregation, which is outside classical relational algebra. Use SQL:For non-null prices $p_1,\dots ,p_n$ of qualifying sales, the result isEach sale contributes once, even when a car was sold on several invoices. Do not use DISTINCT inside AVG: two different sales at the same price must both count. The car's database primary key makes the relational join match each sale to exactly one car, so the relational join introduces no extra weighting.

If there are no qualifying non-null prices, AVG returns SQL NULL. It ignores null prices if the implementation permits them; it does not replace an absent arithmetic mean with zero.^[ref]

Construct the required models and the actual customer–model purchases using relational projection and a natural join:The Cartesian product $I\times M$ lists every obligation: every customer paired with every model present in Car. The relational difference $(I\times M)-V$ consists of unfulfilled obligations. Remove the customer identifiers occurring in this database relation and only then recover names:This is an explicit relational division construction with all customers as the candidate universe. If there are no models, there are no missing obligations, so every customer qualifies. A version starting solely from customers occurring in $V$ would incorrectly omit customers with no purchases in that empty-model case.

The quantified object here is the model database attribute, so two makes sharing a model value contribute one required value. If a different application identified a model by the pair (make, model), both the required and purchased relational projections would use that pair. Also, Car contains unsold cars: a model available only in unsold inventory is still a required model, and then nobody qualifies. Testing identifiers before names prevents different customers with the same name from pooling their purchases.

First use relational selection to keep the Saab cars, then a natural join to find their sales, and finally a relational join to identify the corresponding salespeople. A relational projection givesThe foreign keys ensure that every sale has the referenced car and salesperson. Several qualifying sales by the same person produce just one occurrence of their name under set semantics. Two distinct people with the same name also yield that name only once: this is the requested relational projection onto names.