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

On 2016-01-12 22:48:45 +0000, Tegiri Nenashi said:
>
> There is also "Introduction to Constraint Databases" by P Revesz which
> seems quite accessible. Here is a query from that textbook:
>
> (SELECT X, Y
> FROM Town
> WHERE Name = "Lincoln")
> INTERSECT (SELECT X, Y
> FROM Broadcast)
>
> I have few problems with this query. It doesn't seem to be realistic:
> why would one enter constraints for broadcasting areas where elevation
> map and broadcasting signal function would suffice?

I don't have much context (I don't have the book), but the query above is just an example of spatial intersection. Usually, the point made along with such examples is that in constraint databases you may express some geometrical constructions without resorting to algorithms from computational geometry. This has potentially two advantages: first, the operation above is "easy" because, if Town and Broadcast are represented through constraints, their intersection is just(*) the union of the constraints (evaluating it, e.g., for the purpose of visualizing it in a GIS, is a different matter). 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.

(*) typically, it is required that the resulting set of constraints be in a specific form, so some transformation must be applied, e.g., quantifier elimination.

> Next question, how do people represent map data, I bet it is not a set
> of constraints...

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.

> Can you exhibit an example where map data represented with constraints
> gives an advantage?

See above, but note that I said "potentially" :) I don't really know to what extent the constraint model has been proven "better" in practice, compared to the status quo.

Nicola

• news://freenews.netfront.net/ - complaints: news_at_netfront.net ---