Re: What exactly are "Constraint programming" & "constraint databases" about ?

On Wednesday, January 13, 2016 at 1:00:57 AM UTC-8, Nicola wrote:
> ...Second, the operation
> is expressed quite naturally in SQL or Relational Algebra, without the
> need for extensions such as spatial functions. As such, it is amenable
> to the same treatment and optimization as any other RA expression.

I'm not challenging this part, because it is pretty straightforward. For classic databases those ad-hock relational algebra rewrite rules

https://en.wikipedia.org/wiki/Relational_algebra#Use_of_algebraic_properties_for_query_optimization

can be proved either "point-wise" (that is translating each RA identity into an equivalent calculus statement) or by leveraging relational algebra axiomatization. Then, generalization to constraint databases is trivial dropping of "finite" adjective.

> In practice, currently map data is most often represented using a
> linear approximation in which the only primitives are points, segments,
> and polygons (just zoom into a Google map). The underlying model is
> said to be a "spaghetti" model, because each object is independent of
> the others. So, for example, two adjacent buildings sharing a wall may
> in fact be two distinct polygons with a (hopefully) overlapping edge.
> There are several other spatial models, of course, but this is the most
> used.

Please note, that constraint databases model is "spaghetti" (or I'd better call it "heterogeneous") as well. Primary constraint are inequalities, while equalities are treated are second class citizens. For example,

x^2+y^2=1

is a conjunction of two inequalities. But then, when considering "normal" (not spatial/temporal) atrributes, constraint databases people suggest that their model is not good enough for those , so that they have different set of rules for different attributes. They end up with some awkward constructions such as "generalized tuples", e.g

DepartureCity=LA, ArrivalCity=San Francisco, 700 <= Distance

Clearly, the idea of equalities as second class citizens ends there, and feasibility/practicality of inequality constraints like DepartureCity<=LA is never mentioned.

Once, again I'm for homogeneous model with the scope limited to equalities only. Here is yet one more argument for it.

Consider an [equality] constraint

y = z

This is just a generalized relation with two attributes. Consider the following relational algebra expression:

project(xz, join(R(x,y),y=z) )

This is an old familiar friend -- the rename operator. Received on Thu Jan 14 2016 - 23:32:57 CET