|
Abstract : |
We rework parts of the classical relational theory when the underlying domain is a structure with some interpreted operations that can be used in queries. We identify parts of the classical theory that go through `as before ' when interpreted structure is present, parts that go through only for classes of nicely-behaved structures, and parts that only arise in the interpreted case. The first category includes a number of results on equivalence of query languages, as well as expressive power characterizations for the active-domain semantics for a variety of logics. The second category includes most of our results on the natural semantics, including results on cases where the natural semantics collapses to the active semantics. While these collapse results have been proved by nonconstructive means for first-order logic in previous work, we here give a set of algorithms for eliminating unbounded quantifications in favor of bounded ones. Furthermore, we show these results for a new class of higher-order logics that mix unbounded and bounded quantification. We give a set of normal forms for these logics, under special conditions on the interpreted structures. As a by-product, we obtain an elementary proof of the fact that parity test is not definable in the relational calculus with polynomial inequality constraints. 1, |
