<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 TRANSITIONAL//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; CHARSET=UTF-8">
<META NAME="GENERATOR" CONTENT="GtkHTML/3.3.2">
</HEAD>
<BODY>
I'm assuming x and y are properites of a data object, which has some other component z which <BR>
you with to retrieve, and you query is that you want to find all the records (x,y,z) such that <BR>
(10 < x < 20) and ( -5 < y < 15).<BR>
<BR>
There is a spectrum of solutions to this problem. However, in the general case Elephant will <BR>
not compute this with the best possible asymptotic complexity, although it may be better than <BR>
a relational database at doing so.<BR>
<BR>
Here is the most naive solution:<BR>
<BR>
Examine every object in the database, and report those that meet that above condition.<BR>
<BR>
Although this may seem silly, don't knock it till you try it....it may be perfectly reasonable.<BR>
<BR>
A second solution is to make sure that you have specified :index on the x component <BR>
(or, without loss of generality, the y component), and then using the "get-instance-by-range"<BR>
feature to get all of the instances within the x range, and use a simple lisp function to discard<BR>
those for which the y component does not match.<BR>
<BR>
This will be relatively fast if the x range excludes a lot of objects and the y range doesn't.<BR>
<BR>
It's not obvious to me that one can do better than that without some significant coding <BR>
(For example, a "grid file" is a datastructure designed to answer such queries efficiently.<BR>
An R-Tree is another geometric structure.)<BR>
<BR>
A relational database will not do better, in the worst case. A relational database will do <BR>
a better job at statistical sampling---that is, a query optimizer should, in a huge database,<BR>
be able to decide whether it should use the "x" index or the "y" index first based on the <BR>
selectivity of those clauses in the boolean expression. However, fundamentally it can't <BR>
do any better than to pick the best index, use that only examine some of the objects, and then<BR>
look at the values of the other ones.<BR>
<BR>
On Fri, 2007-06-01 at 03:48 +0300, Ignas Mikalajunas wrote:
<BLOCKQUOTE TYPE=CITE>
<PRE>
<FONT COLOR="#000000"> Hi, i have an interesting usecase and i would like to ask whether i</FONT>
<FONT COLOR="#000000">can solve it by using Elephant. I would like to index objects placed</FONT>
<FONT COLOR="#000000">on a discreet 2d grid of an arbitarry size, which would require</FONT>
<FONT COLOR="#000000">queries like (10 < x < 20) AND (-5 < y < 15).</FONT>
<FONT COLOR="#000000">Is it possible to perform such a query with elephant? I am not sure i</FONT>
<FONT COLOR="#000000">have looked in the right place, but i could not find such example in</FONT>
<FONT COLOR="#000000">the manual.</FONT>
<FONT COLOR="#000000">Ignas Mikalajūnas</FONT>
<FONT COLOR="#000000">_______________________________________________</FONT>
<FONT COLOR="#000000">elephant-devel site list</FONT>
<FONT COLOR="#000000"><A HREF="mailto:elephant-devel@common-lisp.net">elephant-devel@common-lisp.net</A></FONT>
<FONT COLOR="#000000"><A HREF="http://common-lisp.net/mailman/listinfo/elephant-devel">http://common-lisp.net/mailman/listinfo/elephant-devel</A></FONT>
</PRE>
</BLOCKQUOTE>
</BODY>
</HTML>