[elephant-devel] virtual subtree?

[Ian Eslick]

I should clarify two points from my last e-mail.

I added to the first btree the elements:

k: 1 v:'test1
k: 2 v:'test
k 10 v:10
k 20 v:20

That generated the test result.

The final index, 'triple-first, only indexes triples and no other  
types.  It accomplishes this by returning an 'index-p' value.  The  
first value returned by the :key-form is whether or not to index the  
value provided to get-value.  The second value is the secondary-key  
to use to create the index entry that is used to find the value in  
the main indexed-btree, in this case the triple with the first value  
equal to the generated secondary key.

Sorry if that is wordy - please ask questions if any of this is unclear.

Cheers,
Ian

On Apr 15, 2007, at 2:34 PM, Ian Eslick wrote:

> Joe,
>
> The easiest thing I can think of is to create a derived index on  
> the classes of
> elements in your btree and then use map-index to map over the  
> instances.
>
> ELE-TESTS> (setf my-things (make-indexed-btree))
>
> ELE-TESTS> (add-index my-things :index-name 'thing-type
> 		      :key-form '(lambda (index k v)
> 				  (values t (type-of v))))
>
> ELE-TESTS> (map-index (lambda (sk v pk) (print v))
> 		      (get-index my-things 'thing-type) :value 'symbol)
>
> TEST1
> TEST2
> NIL
>
> ELE-TESTS> (map-index (lambda (sk v pk) (print v))
> 		      (get-index my-things 'thing-type) :value 'fixnum)
>
> 10
> 20
> NIL
>
> Or better, you can mix this in with an efficient search for your  
> triples, such as:
>
> ELE-TESTS> (add-index my-things :index-name 'triples-first
>                       :key-form '(lambda (index k v)
>                                     (if (subtypep (type-of v)  
> 'triple) t)
>                                         (values t (triple-first v))
>                                         (values nil nil)))
>                       :populate t)
>
> This will create an index 'triples-first which only indexes triples  
> and does so by the value of the first element.  Thus you can easily  
> retrieve all triples with the first element eq to 5.
>
> ELE-TESTS> (map-index (lambda (sk v pk) (print v)) (get-index my- 
> things 'triples-first :value 5)))
>
> The index will be automatically populated if there are already  
> elements.  Otherwise all new elements will automatically be added  
> to the new index.
>
> This does create a parallel 'index' which is its own btree.  There  
> isn't a good way to do this using only a single btree as we don't  
> expose the sort order constraints or allow the user to create  
> partial keys so they can use cursors to iterate over a subset of  
> the btree.  Now if you indexed your things by typename, then you  
> could do this with a single tree, although you'd have to go over  
> indexes
>
> Cheers,
> Ian
>
>
> A brief aside:
>
> One of the major issues on queue for v 0.9.1 is how do we  
> automatically do something similar
> for class heirarchies.  If I want an index to go over all elements  
> of a base class,
> but a restricted index to go over all elements of some subtype, how  
> do we implement and
> specify this.
>
> For example, if we had base class 'people and subclasses 'employee,  
> 'manager, 'consultant, etc.
> What if we wanted to retrieve all 'employees and 'managers named  
> "Bob"?  Today you'd have to map
> over each class index separately.  I'd like to be able to map over  
> 'people if people has a slotname
> for "Name" that is common to the subclasses and get back all  
> objects of any subclass with that name.
>
>
> On Apr 15, 2007, at 12:39 PM, Joe Corneli wrote:
>
>> I am wondering whether it is possible to efficiently treat a  
>> subset of
>> a given btree as its own tree.  Specifically: if I have a collection
>> of miscellaneous data, which I'll call Things, some of which are
>> Triples, can I specifically examine all of the Triples in my
>> collection, and from that sub-set, find those Triples whose first  
>> slot
>> is, say, equal to 5?
>>
>> Or must I do what seems to be the expected thing, and treat Things  
>> and
>> Triples as a separate btrees if I want to efficiently search through
>> the slots of my Triples?
>> _______________________________________________
>> elephant-devel site list
>> elephant-devel at common-lisp.net
>> http://common-lisp.net/mailman/listinfo/elephant-devel
>
> _______________________________________________
> elephant-devel site list
> elephant-devel at common-lisp.net
> http://common-lisp.net/mailman/listinfo/elephant-devel