Choose a circular fillet that removes the sharp convex tip at $B$. The unit directions from $B$ toward $A$ and $C$ are $(-\sqrt{3}/2,-1/2)$ and $(-1,0)$. Therefore the prescribed tangent points areThe circle centre $K$ lies on the normal line to $BC$ through $N$, so $K=(3/2,k)$. Its radius to $M$ must be perpendicular to $AB$, whose direction vector is $(\sqrt{3},1)$. ThusConsequentlyIndeed $|M-K|=|N-K|=r$. The interior angle $ABC$ is $30^{\circ }$, and the same radius follows from $r=\frac{1}{2}\tan 15^{\circ }$. The selected circular arc runs from $M$ to $N$ through angles $-60^{\circ }\le \theta \le 90^{\circ }$ around $K$:The $150^{\circ }$ circular arc facing $B$ is the rounding; the complementary arc is not part of the boundary.

Define the disk and a half-plane through the chord $MN$ byBoth $M,N$ satisfy $g=0$, and $g(B)=1/2>0$. The clipping half-space $H_g$ retains the part away from $B$, while the disk restores the rounded cap. The required local constructive solid geometry tree isOnly the portion of $P$ on the $B$ side of $MN$ can be removed. To see the locality, $g$ is negative at every original vertex of a polygon except $B$, and vanishes on the two adjacent sides exactly at $M,N$. In the resulting triangle $BMN$, the disk keeps the curved cap next to $MN$ and discards the tip at $B$. A global set intersection with $D_r$ alone would destroy most of the seat. The outward normal vector on the new boundary is $\nabla f_c=2((x,y)-K)$; at $M,N$ it has the same direction as the outward normal vectors of $AB,BC$.

The tangent constraints alone do not insist on a circle; other conic sections can give different bulges. For example, a positive-weight rational quadratic Bézier curve with handles $M,B,N$ has the required tangent directions:Varying $w$ changes the bulge while fixing the tangent points; the circular choice has $w=\cos 75^{\circ }$. Once a circular fillet and these two tangent points are chosen, its centre and radius have no remaining freedom. The half-plane sign and arc selection are also essential: reversing them chooses a different retained region. This construction gives matching tangent directions, or first-order geometric continuity, at $M,N$; the curvature jumps from zero on each straight side to $1/r$ on the circle.

The tight axis-aligned bounding box is $Q=[0,2]\times [0,2]$. Bisect vertically at $x=1$, giving a right child $R=[1,2]\times [0,2]$. For a scalar implicit function representing the same constructive solid geometry solid, useWith the convention $f_i\le 0$ inside, set intersection corresponds to the maximum, and set union to the minimum. These operations encode membership; $\Phi$ is not a signed distance function.

Since every $f_i$ is an affine function, its extreme values on $R$ occur at corners. Exact real-arithmetic interval arithmetic gives:

Each leaf range is exact, but combining independent intervals forgets that the expressions share $x,y$. The final enclosure need not be the exact range of $\Phi$. For example, equality $\Phi =-1$ would require both $f_6\le -1$, hence $y\ge 1$, and $\min (f_2,f_3)\le -1$, hence $y\le 0$ on $R$, which is impossible. The enclosure is still sufficient for a reliable three-way decision:Here the result is unresolved. This is a real mixed box, rather than only a pessimistic test: $(5/4,3/4)$ is strictly inside, whereas $(3/2,3/2)$ is outside. A zero endpoint alone can also mean contact with the boundary, so equality must not be treated as proof of strict interior or strict exterior. In floating-point arithmetic, certified bounds require outward rounding.

Continue splitting unresolved boxes, normally alternating axes or splitting the longest side. Propagate the interval arithmetic results through the constructive solid geometry tree, discard exterior boxes and stop refining strict interior boxes. In sufficiently small boundary boxes, locate crossings of the active implicit equations with box edges and connect them into boundary line segments. Retain corners and resolve ambiguous multiple crossings by further refinement; here every genuine boundary piece is straight, so its supporting implicit equation allows exact intersection rather than a curved approximation. A maximum boundary-box diagonal $\epsilon$ gives spatial localization at that scale, provided no boundary components are discarded; corner-sign sampling alone provides no such guarantee.

The tight box saves empty-space work, but it is awkward for extracting facets. Entire boundary line segments, notably $EO$, $OA$ and $DE$, lie on the initial box boundary, and $CD$ lies on the first splitting straight line. A sign-change-only method may have no exterior sample on the other side and lose such pieces; exact zeros also persist through refinement. A slightly padded initial axis-aligned bounding box, together with an explicit rule for boundary-coincident pieces, makes the faceting more robust. The tight box is therefore economical for enclosure but not the best unqualified choice for a simple faceting implementation.

Put $a_0=2-\sqrt{3}$ and define six closed half-spaces $H_i=\{(x,y):f_i(x,y)\le 0\}$. Their implicit equations and outward normal vectors are:

The six vertices of a polygon traverse the boundary counterclockwise. Each displayed normal vector therefore points to the right of the corresponding directed boundary line segment; it need not be a unit vector. The zero level sets are full straight lines, while the actual boundary retains only the appropriate line segments.

The inward corner at $C$ prevents using the set intersection of all six half-spaces: that would incorrectly discard the upper-left part of the seat. Instead takeThe last factor permits either $y\le 1$ or $x\le 1$, removing only the upper-right region. Another way to understand the same constructive solid geometry model is as the set union of two convex polygons, obtained by distributing the last set intersection over this set union. Its constructive solid geometry tree has an intersection at the root and a union child for $H_2,H_3$.

For $ax+by+c=0$, substitute $y=0$ or $x=0$, respectively:In terms of the original coordinates, these arewith each expression used only when its denominator is nonzero. If $a=0$, the straight line is horizontal: it misses the horizontal axis unless $c=0$, in which case it is that entire axis. If $b=0$, it is vertical: it misses the vertical axis unless $c=0$, in which case it is that entire axis. A straight line through the origin has both finite intercepts equal to the origin whenever neither axis is coincident with it.

Solving the implicit equation for $y$ when $\Delta x\ne 0$ givesHere “gradient” means the slope $dy/dx$, rather than the gradient $(a,b)$ of an implicit defining function. If $\Delta x=0$ and $A\ne B$, the straight line is vertical and has no finite slope. If $\Delta y=0$ and $\Delta x\ne 0$, its slope is zero.

Set $\Delta x=x_B-x_A$ and $\Delta y=y_B-y_A$. A displacement from $A$ lies along the straight line precisely when its two-dimensional determinant with $(\Delta x,\Delta y)$ vanishes. Thus an implicit equation isEquivalently, write $ax+by+c=0$, with $a=\Delta y$, $b=-\Delta x$ and $c=\Delta x{y}_A-\Delta y{x}_A$. The vector $(a,b)$ is a normal vector. The formula handles vertical and horizontal straight lines without division. It presupposes $A\ne B$: coincident points do not determine a unique straight line.

Let $\mathcal{A}$ contain the $n$ database attributes of $R$, and let $F$ contain the given functional dependencies for $R$. To compute the attribute closure $X^{+}$, start with $X$ and repeatedly add $V$ for every functional dependency $U\to V$ with $U\subseteq X^{+}$, stopping when a full scan adds nothing.

Enumerate every $X\subseteq \mathcal{A}\setminus \{a\}$. For each, test whether $X$ is not a superkey but becomes one on adding $a$:If no enumerated $X$ passes both tests, return no. A direct implementation isIf a candidate key $K$ contains $a$, choose $X=K\setminus \{a\}$. Minimality makes $X$ fail the superkey test while $X\cup \{a\}=K$ passes it, so the algorithm finds a witness.

Conversely, suppose an enumerated $X$ passes. Starting from $X\cup \{a\}$, repeatedly discard any database attribute other than $a$ whose removal preserves the superkey property. The process terminates at a superkey $K$ minimal with respect to these deletions. Removing $a$ cannot leave a superkey: $K\setminus \{a\}\subseteq X$, and a subset of $X$, which is not a superkey, cannot determine more database attributes than $X$. Hence $K$ is a candidate key containing $a$. The algorithm need not carry out this minimization to return the correct yes/no answer; it establishes why the witness test suffices.

For an explicit analysis of algorithms, let $L$ be the total encoded length of the functional dependencies, counting their left and right database attribute occurrences and delimiters. With Boolean membership arrays, one complete dependency scan costs $O(L)$. There are at most $n$ productive scans, followed by one unproductive scan, so a naive attribute closure costs $O(nL+n)$. There are $2^{n-1}$ subsets and at most two attribute closure computations per subset. ThusThis is an exponential-time algorithm in the number of database attributes, not a polynomial-time claim. Subsets can be generated successively rather than stored all at once. The argument applies to functional dependencies within the database relation $R$; dependencies belonging to unrelated database relations do not constrain its candidate keys.

Take the relational schema and functional dependencyThe attribute closure of $\{b\}$ is $\{b,a\}$, so $\{b\}$ is a candidate key. The attribute closure of $\{a\}$ is just $\{a\}$, so it is not a superkey. The set $\{a,b\}$ is a superkey but is not a candidate key, because removing $a$ leaves the superkey $\{b\}$. Thus the only candidate key is $\{b\}$, and $a$ occurs in none.

For example, records $(b,a)=(1,7),(2,7)$ illustrate that the same $a$ value may occur at different $b$ values. The conclusion about candidate keys follows from the declared functional dependencies, rather than from accidental uniqueness in any one sample.

Abbreviate the database attributes by $E,C,B,S,T,O$ for EventId, ConfId, BuildingId, StartTime, EndTime and ConfOrganizer. Write $\mathcal{A}=\{E,C,B,S,T,O\}$ for the full relational schema.

The explicit event assumptions give the functional dependencyI additionally interpret the conference's organizer as a single organizer for the whole conference, giving $C\to O$. This is the natural reading of ConfOrganizer, but it is stronger than saying only that each event has one organizer. Under this interpretation a compact generating basis of functional dependencies isThere is no premise that an EventId is globally unique, that a conference has one building, or that a start time determines an end time. In particular, the single-room requirement for one subtype in part (a) must not be imposed on this entire database relation.

To specify all non-trivial functional dependencies without listing every augmented version, the attribute closure isExactly the functional dependencies $X\to Y$ with $Y\subseteq X^{+}$ and $Y⊈X$ are non-trivial consequences of the assumptions. In particular, $EC$ is the only candidate key: both $E$ and $C$ must be present because neither is generated from other database attributes.

Every functional dependency implies the corresponding multivalued dependency. Thus $C\twoheadrightarrow O$ and, by complementation, $C\twoheadrightarrow EBST$ hold. Also $EC\twoheadrightarrow Y$ holds for every $Y\subseteq \mathcal{A}$, with the usual trivial cases omitted. A complete compact description, including all augmented and complemented cases, isFor a non-trivial multivalued dependency, additionally require $Y⊈X$ and $X\cup Y\ne \mathcal{A}$. To see the criterion, if either side of the split is determined by $X$, swapping that side requires no new database tuple. Conversely, if both sides contain a database attribute outside $X^{+}$, choose two database tuples agreeing exactly on $X^{+}$. They satisfy every functional dependency in $F$, but a mixed database tuple required by the proposed multivalued dependency is neither of them. The two-row database relation is therefore a counterexample.

There is no independent many-valued fact such as buildings freely combining with event times. For example, two events of one conference might have $(E,B,S,T)=(e_1,b_1,s_1,t_1)$ and $(e_2,b_2,s_2,t_2)$. A multivalued dependency $C\twoheadrightarrow B$ would require the building to be swappable independently of the event and its times, which these assumptions do not require and the event functional dependency may forbid.

Since $C$ is not a superkey, $C\to O$ violates Boyce-Codd normal form. The corresponding non-trivial multivalued dependency $C\twoheadrightarrow O$ violates fourth normal form. Use the decompositionTheir common database attribute is $C$, which determines the whole first component. Consequently the decomposition is a lossless-join decomposition: each event joins to exactly its own conference's organizer, producing no spurious database tuples.

In the first component, the only basic non-trivial functional dependency is $C\to O$, whose determinant is a candidate key. In the second it is $EC\to BST$, again with a candidate key determinant. No independent non-trivial multivalued dependencies with determinants that are not superkeys are implied in either component, so both are in fourth normal form, and therefore in Boyce-Codd normal form. This reaches the strongest normal form tested here. The decomposition is a dependency-preserving decomposition: $C\to O$ is enforced in the first component, $EC\to BST$ in the second, and together they imply $EC\to O$.

If only the explicitly stated event-level organizer uniqueness is assumed, omit $C\to O$. The basis is then just $EC\to BSTO$; $X^{+}=\mathcal{A}$ when $EC\subseteq X$ and $X^{+}=X$ otherwise. Under those weaker assumptions the original database relation is already in fourth normal form and Boyce-Codd normal form, so no decomposition is necessary. In particular, separating $(C,O)$ under that reading could create extra database tuples when different events of one conference have different organizers.

Use an entity-relationship model with Customer, Conference, Event, Venue and Building. The following entity-relationship diagram uses minimum–maximum cardinalities at each end: the label beside an entity counts how many instances of that entity can be associated with one instance at the opposite end. A double link into the specialization circle means total specialization; its d means disjoint.

Every conference belongs to exactly one customer and contains at least one event. A customer may book zero or more conferences. Every event belongs to exactly one conference and occurs at exactly one venue; a venue may host zero or more events. The event identifier is local to its conference, so its full candidate key is (conferenceid, eventNo). Choosing an event number is an explicit additional identifier assumption; a globally unique event identifier would be another valid design.

Every conference is exactly one of the two entity subtypes, SingleDay and MultiDay. Both inherit the conference identifier and the customer and event relationships. For SingleDay, store heldDate, and enforceThese cross-event database integrity constraints accompany the diagram; simple endpoint cardinalities alone cannot express them. Since there is at least one event, their common venue determines the conference's single room.

For this design, a venue is a room with the given identifier, name and capacity, and each room belongs to exactly one building. A building may contain zero or more rooms. Introducing Building and its identifier is an explicit modeling choice that makes the single-building requirement enforceable: one common room implies one common building. If an application also used non-room venues, it could instead introduce a room entity subtype and restrict SingleDay events to it.

The start and end values are full timestamps, not times of day alone, and each event has $\mathsf{startTime}<\mathsf{endTime}$. MultiDay events may use different dates and rooms; the design does not force every pair of events to use different rooms or dates. It imposes no uniqueness of customer names, no venue-exclusivity rule, and no attendance–capacity rule because no attendance data are supplied. Such extra scheduling restrictions could be added as further database integrity constraints without altering the basic entity-relationship model.

A serial database schedule is obtained by running the three database transactions in the order $T_1,T_2,T_3$:A genuinely interleaved conflict-serializable database schedule with the same serial order isThe early $R_3(B)$ conflicts with nothing: all accesses to $B$ are reads. The conflicts on $A$ give edges $T_1\to T_2$, $T_1\to T_3$ and $T_2\to T_3$ in the database precedence graph, while the writes to $C$ give the already present edge $T_1\to T_2$. This database precedence graph has no directed cycle and admits the order $T_1,T_2,T_3$. Moving the early $R_3(B)$ after $R_2(B)$ swaps it only past non-conflicting operations, recovering the displayed serial database schedule.

For a database schedule that is not a conflict-serializable database schedule, takeOn $A$, $W_1(A)$ before $W_2(A)$ forces $T_1\to T_2$. On $C$, $W_2(C)$ before $W_1(C)$ forces $T_2\to T_1$. The resulting directed cycle prevents any serial ordering from preserving all conflicts. Each of the three displayed database schedules preserves the operation order inside every database transaction.

Use fan-out four to mean at most four child pointers per internal node. A height increase requires a B+ tree node split at the root. Immediately after that B+ tree node split, the new root has exactly two children.

One further insertion follows one search path. Any chain of B+ tree node splits along that path can pass at most one additional separator and child pointer to the root. Its number of children therefore rises from two to at most three, below the maximum four. ThusThe argument includes an initially leaf-only B+ tree: its first root split likewise creates a root with two children. Even if the next insertion causes a child split immediately, the new root still has room. The conclusion assumes the standard insertion operation with one overflowing node split into two; it does not depend on whether height counts edges or levels.

A simple valid database query plan uses a block nested-loop join with the salesperson records on the outside, checking both sale conditions during the same inner scan. It avoids materializing the potentially much larger set of matching sale pairs.

Let $p\le SPT$ be the actual number of salesperson data pages and $k$ the number of outer data pages that fit along with the flags and working buffers. With the usual convention of $B-2$ outer pages, one inner input page and one output page, take $k=B-2$ for $B\ge 3$. If flag storage requires an extra reserved page, reduce $k$ accordingly. The number of outer records is at most $pSPR$, and there are $\lceil p/k\rceil$ outer blocks. Every such block requires a complete scan of the $ST$ sales data pages.

Count a database page read or write as one I/O. Conservatively charge $H_{SP}$ to locate the first salesperson leaf and $H_S$ to locate the start of each inner scan; this permits a small double charge if a definition of height includes a data leaf. The estimated read cost isIn the common convention that scan startup and cached internal pages are ignored, the usual upper estimate isFor an empty outer input there are no inner scans. This database query plan requires neither a sorted sale input nor a price index. In particular, the clustered database index on invoiceno cannot locate records by price. The quantities $TN$ and $THO$ describe the amount of qualifying data; they do not justify replacing a complete scan cost $ST$ by $TN+THO$. They can bound the retained work within each scan by roughly $(TN+THO)SR$ sale records, if those page counts describe packed qualifying records. Comparison cost against the outer block is CPU work rather than additional I/O.

Finally let $D_{\delta }$ be the extra I/O for eliminating repeated output names, including any temporary writes and reads, and let $w$ be the final result size in database pages if materialization is required. The total estimate isIf enough additional memory is available to retain all distinct qualifying names while producing the stream, then $D_{\delta }=0$. This extra memory is an additional assumption, separate from the $B$ join buffers. More generally, for $q$ pages of raw qualifying names, external merge sort gives $D_{\delta }=O\left(q\left[1+{\log }_{B-1}\max \{1,\lceil q/B\rceil \}\right]\right)$ for $B\ge 3$, including spooling. Names can be deduplicated during the merges. Counting this work matters because a database primary key on empid does not make names unique. No claim of optimality is needed for this database query plan.

Find the salesperson identifiers satisfying each price condition using relational selection and relational projection:Intersect these identifier sets, relational join the result to the salesperson records, and apply relational projection to names:If intersection is not a primitive of the chosen relational algebra, use $L\cap H=L-(L-H)$ with relational difference. There is no need to access Car: the foreign key already ensures that every sale refers to a car.

Intersecting names instead of identifiers is wrong. Two different salespeople called Alex, one making only $10000$ sales and the other only $30000$ sales, would make Alex appear in both name sets although neither person satisfies the condition. Nor can one sale satisfy both price tests: the two distinct prices require distinct sale records.

The right-hand relational projection lists the models of cars for which at least one recorded sale was made by a salesperson earning strictly more than $30000$. The outer relational difference removes precisely those models from all models present in Car. Thus the answer isThis includes models with no sales at all, as well as models sold exclusively by salespeople whose salaries are at most $30000$. A model sold by both a low-paid salesperson and a high-paid salesperson is excluded. A salary exactly equal to $30000$ does not trigger exclusion. These are model-level statements: one unsold car of a model does not rescue that model if a different car of the same model had a qualifying sale.