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

[Erwin]

I run into these terms rather frequently, without ever getting/finding a good explanation as to what it's really about.

Anyone here can help me ?

[Nicola]

Since it seems that Springer has given free access to its books up to 2004,
if you are interested you may download this:

http://link.springer.com/book/10.1007/978-3-662-04031-7

Nicola


--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---

[Erwin]

>
> Since it seems that Springer has given free access to its books up to 2004,
> if you are interested you may download this:
>
> http://link.springer.com/book/10.1007/978-3-662-04031-7
>
> Nicola
>
>

Thanks, but, well :

(a) that link doesn't seem to immediately give me "free download" (of the table of contents, yeah) and the "look inside" gives me access to only two initial pages of each chapter.
(b) I was looking for a bit of introductory stuff that starts off with a good answer, in layman's lingo, to the questions such as "why should I even care" (*) (not with "we define a vocabulary as three sets F,P and M").

(*) question also known as, a.o. :
- what does it do that other databases cannot do ?
- what problem of mine do they intend to solve (or facilitate solving) ?
- why are they being researched ?

I can still decide to dig deeper later on.

[Nicola]

On 2015-12-31 10:09:10 +0000, Erwin said:

>>
>>
>> Since it seems that Springer has given free access to its books up to 2004,
>> if you are interested you may download this:
>>
>> http://link.springer.com/book/10.1007/978-3-662-04031-7
>>
>> Nicola
>>
>>
>
> Thanks, but, well :
>
> (a) that link doesn't seem to immediately give me "free download" (of
> the table of contents, yeah) and the "look inside" gives me access to
> only two initial pages of each chapter.

Ouch. It was available yesterday. A mistake on Springer's part then, or
a temporary Christmas gift.

I'm in a hurry now, I'll get back to this later.

[Nicola]

On 2015-12-29 14:16:11 +0000, Erwin said:

> I run into these terms rather frequently, without ever getting/finding
> a good explanation as to what it's really about.

The idea of constraint databases is simple: a tuple may be viewed as a
very restrict form of constraint, and a relation instance as a set of
(simple) constraints. For example:

R
x y
---
1 2
3 4

may be viewed as a representation of the constraint (x=1 and y=2) or
(x=3 and y=4). Think of that relation as a set of points in the plane:
the relation then defines two points.

Now, what if we allow more general constraints, say inequalities (x=1
and y<2)? It turns out that it is possible to give reasonable
definitions of generalized tuples and generalized relations
corresponding to such constraints. The generalized relations are
possibly infinite (x=1 and y<2 would represent an infinite set of
points). So, constraint databases are a way to extend the relational
model to deal with (finitely represented) infinite relations.

The approach is particularly attractive for spatial databases. Consider
again the Euclidean (2D) plane: an inequality of the form ax + by + c
<= 0 defines a half-plane. Any convex polygon may be defined as an
intersection of half-planes, and non-convex polygons as unions of
convex polygons. Lines and points are degenerate forms of polygons, so
they also may be represented in the same way. Therefore, points, lines
and polygons may be all represented as sets of constraints of the form
ax + by + c <= 0—that is, generalized relations.

Constraint programming is another thing entirely: it deals with solving
problems that may be modeled via constraints (e.g, find all the ways to
put eight queens on a chessboard without them being able to capture
each other). Of course, in constraint databases queries become
constraint problems, so one may naturally apply constraint programming
techniques to solve them.

This is maybe not the good explanation you expected, but I hope it is a
start. Let's try to provoke more posts:

constraint programming : constraint database = relational algebra :
relational database

[Tegiri Nenashi]

> ax + by + c <= 0--that is, generalized relations.

>
> Constraint programming is another thing entirely: it deals with solving
> problems that may be modeled via constraints (e.g, find all the ways to
> put eight queens on a chessboard without them being able to capture
> each other). Of course, in constraint databases queries become
> constraint problems, so one may naturally apply constraint programming
> techniques to solve them.
>
> This is maybe not the good explanation you expected, but I hope it is a
> start. Let's try to provoke more posts:
>
> constraint programming : constraint database = relational algebra :
> relational database
>
> Nicola

So suppose you have the following system of constraints:

y^2 -3*y +2 = 0
x*y -x -3*y +3 = 0
x^2 -3*x -2*y +4 = 0
x > 0

Can you exhibit an algorithm that:
1. Decides if it is a finite set of points
2. Lists the points
(If I remove inequality then the algorithm that does that is doubly exponential. Is there such an algorithm in semi-algebraic case and what its complexity?)

[vadi...@gmail.com]

On Wednesday, January 6, 2016 at 7:52:39 AM UTC-8, Nicola wrote:

> constraint programming : constraint database = relational algebra :
> relational database

This correspondence is certainly intriguing in semi-algebraic case. In algebraic case you can employ off-the-shelf CAS to work as rudimentary RDBMS
https://vadimtropashko.wordpress.com/2016/01/04/relational-algebra-with-cas/

[Nicola]

On 2016-01-06 17:30:47 +0000, Tegiri Nenashi said:
>
> So suppose you have the following system of constraints:
>
> y^2 -3*y +2 = 0
> x*y -x -3*y +3 = 0
> x^2 -3*x -2*y +4 = 0
> x > 0
>
> Can you exhibit an algorithm that:
> 1. Decides if it is a finite set of points
> 2. Lists the points
> (If I remove inequality then the algorithm that does that is doubly
> exponential. Is there such an algorithm in semi-algebraic case and what
> its complexity?)

I assume that the problem you have in mind is equivalent to the problem
of evaluating queries in the first-order language FO(<,=,+,*,0,1) over
the rationals or the reals. If my memory does not fail me, I *think*
that the complexity should stay the same, but I don't know more
details. Btw, you are talking about query complexity, that is, the
complexity wrt to the size of the constraints. In databases, data
complexity (the complexity wrt to the size of the database) is often
more relevant, and typically much lower. The language above has
tractable data complexity (PTIME if I remember well). Also, linear
constraints are already sufficient for many applications (e.g., GIS).

[Nicola]

Note that the correspondence is (intentionally) inaccurate. In
constraint databases you continue to use relational algebra, for
example; it's just the evaluation mechanism that changes. The role of
constraint programming in that context is closer to query evaluation
than to query formulation.

[vadi...@gmail.com]

On Tuesday, December 29, 2015 at 6:16:14 AM UTC-8, Erwin wrote:
> I run into these terms rather frequently, without ever getting/finding a good explanation as to what it's really about.

Pages 93-96 in the Alice book

http://wiki.epfl.ch/provenance2011/documents/foundations%20of%20databases-abiteboul-1995.pdf

[Tegiri Nenashi]

On Thursday, January 7, 2016 at 2:22:51 AM UTC-8, Nicola wrote:
> I assume that the problem you have in mind is equivalent to the problem
> of evaluating queries in the first-order language FO(<,=,+,*,0,1) over
> the rationals or the reals. If my memory does not fail me, I *think*
> that the complexity should stay the same, but I don't know more
> details. Btw, you are talking about query complexity, that is, the
> complexity wrt to the size of the constraints. In databases, data
> complexity (the complexity wrt to the size of the database) is often
> more relevant, and typically much lower. The language above has
> tractable data complexity (PTIME if I remember well). Also, linear
> constraints are already sufficient for many applications (e.g., GIS).

Doubly-exponential
https://en.wikipedia.org/wiki/Real_closed_field#Model_theory:_decidability_and_quantifier_elimination

[Nicola]

Yes, in the size of the formulas.

[Nicola]

On 2015-12-31 10:09:10 +0000, Erwin said:

>>
>>

Have you tried browsing the book on Google Books? §1.4-§1.7 (which you
should be able to access almost entirely) do a good job, I think,
explaining what it is all about.

[Tegiri Nenashi]

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? Next question, how do people represent map data, I bet it is not a set of constraints... Can you exhibit an example where map data represented with constraints gives an advantage?

[Nicola]

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.

[Tegiri Nenashi]

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.

[Erwin]

Op dinsdag 12 januari 2016 20:09:18 UTC+1 schreef Nicola:

> --- news://freenews.netfront.net/ - complaints: ---

Thanks for that. I think I get the point now.