[DAS2] feature search algorithm (was Re: feature locations)

[Andrew Dalke]

Given a database:

Foo: (10, 60)
   Bar: (10, 20)
   Baz: (50, 60)

I understand that everyone wants "overlaps(30,40)" to
return {Foo, Bar, Baz}.  That includes me.  I question
the need for the requirement that parent locations include
all of the children locations.  Putting that aside for now
I have a question about the above structure, which we all
agree is valid.

What does the search

    overlaps(30,40) and title == "Foo"

return?

I think it should return nothing.  There are no features
named "Foo" in that range.

If I understand you all correctly it should return {Foo,
Bar, Baz} because the overlaps search is only done on
the root feature, returning all features in the feature
group, while the title search is done on on a per-feature
basis.


How is the server search algorithm supposed to work?


Given a range search "in_range(feature)" and non-range
search "is_match(feature)" (for things like title, type, etc.)
then the current search algorithm can be expressed:

   find all features X where:
     feature X is in the same feature group as feature Y where:
         in_range(Y) and is_match(Y)


As I understand from you all, the search algorithm should be

   find all features X where both:
    - feature X is in the same feature group as Y where:
         Y is a root element and in_range(Y)
    - feature X is in the same feature group as Z where:
         is_match(Z)

					Andrew
					dalke at dalkescientific.com