Re: Comments on Norbert's topological extension of relational algebra
Date: Mon, 21 Dec 2015 08:30:18 -0800 (PST)
Message-ID: <cea5784d-2aad-48da-ba16-765144ace727_at_googlegroups.com>
On Monday, December 21, 2015 at 4:24:36 AM UTC-8, Jan Hidders wrote:
> Op zondag 20 december 2015 10:27:17 UTC+1 schreef vadi..._at_gmail.com:
> > On Tuesday, December 15, 2015 at 8:14:17 AM UTC-8, Jan Hidders wrote:
> > > What *I* am interested in is the connection with this work:
> > >
> > > http://alpha.uhasselt.be/~lucp1080/queries_reals.pdf
> >
> > Do you prefer to work with algebraic or semi-algebraic constraints?
> >
> > Here is how Heath's theorem from database dependency theory is made obvious in algebraic settings. Basically we have:
> > 1. A system of constraints in 3 variables x,y,z
> > 2. A function x->y
> > We need to reorganize the system's constraints into two parts: the ones expressed in variables x and y only, on one hand, and the other in x and z. For the first system we take the equation that defines the active domain x together with the equation that explicitly defines FD x->y. For the second system, we take the whole original system, and eliminate y by substitution its formula in terms of x.
> > https://vadimtropashko.wordpress.com/2014/01/03/analytic-view-of-functional-dependency/
> >
> > I struggle to prove Heath's theorem for semialgebraic sets. For example, is it possible to have functional dependency which is a function but not expressible polynomially?
>
>
> In principle yes, but that was already the case in the algebraic setting where it is also not a priori the case that all functional dependencies are expressible by a polynomial, unless that is how you define them, as you apparently do. You are anyway looking here at restricted classes of relations and dependencies, so it's up to you to say how you want to restrict them.
There is no requrement for functional dependency to be polynomial -- this has been inferred. Let me explain why it is not a vacuous statement. I can easily see how a reader can be confused, because first I say that a relation is a system of polynomial conatraints, and then go on to discuss constraints of another kind: database dependencies. The fact that one can express functional dependency as a explicit polynomial expression is not a trivial consequence of the fact that we have polynomial system. One has to refer to polynomial interpolation as a method to recover this expression, at least, because this function was originally not in the constraint system. It suddenly appeared when I calculated Grobner basis in this particular example. In general case, it existence follows from inerpolation.
There is more to the idea of constraint databases in algebraic perspective. One really has to study ideals, not varieties. Please note that geometrically ideals formally describe roots of polynomial system together with their multiplicities. Essentially, we have coherent theory of multisets (relations with duplicate tuples).