Re: Functions and Relations

On 2006-11-17, Aloha Kakuikanu wrote:

> Function u=f(x,y,z) in general is a predicate Pf(x,y,z,u) with some
> additional constraint. [...]

Similarly normal predicates like less-than can be represented as relations on two copies of any domain with equality. Then all you'll ever need are equijoins.

> Given that a predicate is often an infinite relation we have obvious
> difficulty implementing it.

None of the usual predicates are infinite, because precision limits force finiteness. The interesting, genuinely infinite case comes about only when you deal with bignums, unlimited length strings or some other similarly lenient type. I think it'd mostly be funny if an engine could be forced to select from a blob type equality predicate, for example...

> This index is not a conventional b-tree of course, as all what is
> needed to do when x is known, and y is not is just to calculate y by a
> simple formula x^2. The corollary here is that the function x->x2 is
> essentially an index.

Yes. I've also many times wondered why only those indices are generally available in DBMS's, e.g. for calendar calculations, and not the underlying relations. I mean, using them and a concise equijoin syntax would make a number of practical tasks a whole lot easier.

> The other case is only marginally more complex. Likewise, we quickly
> arrive to the conclusion that the only feasible execution is the
> indexed nested loops with the scan of the `y=9` as the leading
> relation.

OTOH, if there was enough information available on the domain and the relations, it is theoretically possible that the DBMS could autonomously come up with a numerical solution to the equation. In some applications heavily domain based mechanics like these might also make practical sense if the payoff and utilization is great enough: think for example of the spatio-temporal stuff that makes R-trees tick.

> Here is little more complex example. For x^2+y^2=1, there are 3 access
> methods:
> 1. Given x, and y return {(x,y)} if they satisfy the equation, and {}
> otherwise.
> 2. Given x return {(x,sqrt(1-x^2)),(x,-sqrt(1-x^2))} or empty set.
> 3. Given y return {(sqrt(1-y^2),y),(-sqrt(1-x^2),y)} or empty set.

4. Given a selection from any such relation, return a succinct approximation to the set of selected points, e.g. by tiling it?

I think this sort of thing is not totally out of the question, because a) approximate answers are already within the DSS/OLAP/statistical canon, b) Codd and others have already suggested DBMS support for specialized representations like tuple bags collapsed to a set plus a count attribute, c) operationalizing and axiomatizing infinite sets and their approximate representations as disjoint unions shouldn't be too difficult, and d) solid modeling folks already have the necessary algorithms.

-- 
Sampo Syreeni, aka decoy - mailto:decoy_at_iki.fi, tel:+358-50-5756111
student/math+cs/helsinki university, http://www.iki.fi/~decoy/front
openpgp: 050985C2/025E D175 ABE5 027C 9494 EEB0 E090 8BA9 0509 85C2