[elephant-devel] Newbie question: Index on collections
Marc
klists at saphor.de
Mon Mar 24 10:41:20 UTC 2008
Ian Eslick wrote:
> Great! Actually in writing the following e-mail, I realized that this
> had forced me to think through a bunch of things and so I wrote a
> version of the functionality in associations.lisp and just checked it in.
>
> Start playing with, reading and commenting on what's wrong with it.
> For example, I'd like a better API for adding/removing items from
> slots than overloading (setf (accessor instance) related-instance). I
> left a commented API proposal in the source code for you to look at.
>
> There are still bugs that I haven't thought through that will crop up
> when you change classes, redefine classes, etc. Let me know what you
> think.
Thanks for the file and the documentation in this mail. Starting from
this I'll now begin to dig into it and try to grope my way around.
As to timing: this week is somewhat busy due to a conference, but I
still hope for some time in between sessions.
Best regards
Marc
>
> ========================
>
> Download the elephant-unstable branch:
>
> darcs get
> http://www.common-lisp.net/project/elephant/darcs/elephant-unstable
>
> It's probably best to spend a little time reading and experimenting,
> then write up a proposal so we can discuss it a bit. The support for
> defining association slots (but not implementing them) is already
> implemented in metaclasses.lisp.
>
> The idea of an association is that instances of class A can find
> instances of class B that are 'associated' with it. Association
> relations can be undirected or directed, typically called many-to-many
> or 1-to-many. 1-to-many is a kind of inverse indexing and many-to-many
> requires a separate btree/class/table to maintain the undirected
> relation. Hopefully the following description will help clarify what
> I mean.
>
>
> One-to-Many associations:
>
> If class B has a slot that stores a single instance of A, then class A
> would like to have a method that returns the set of instances of B
> that refer to the instance of A.
>
> If A is person and B is job, then job->owner is a reference to A and
> A->jobs is a method (no slot storage) that refers to an index on
> job->owner. The index keys are A oids.
>
> If you look in indexed-slots.lisp, you'll get a sense of how indices
> work. set-valued-slots.lisp is also useful as it puts a btree in each
> instance's slot to store sets of objects using the pset abstraction in
> pset.lisp. Reading these three files should help alot to see how we
> use btrees and dup-btrees to maintain sets of objects and relations.
>
>
> One challenge is how to specify an association implicitly in slot
> definitions. Ideally you want it to be on the object that you are
> most often going to use to add and remove relations:
>
> (defpclass person ()
> ((jobs :accessor jobs :association (job owner))))
>
> (defpclass job ()
> ((title :accessor title ...)
> (company :accessor company ...)))
>
> But this means that person has to change the definition of job and
> that can be problematic. So you could require agreement...
>
> (defpclass person ()
> ((jobs :accessor jobs :association (job owner)))
>
> (defpclass job ()
> ((title ...)
> (company ...)
> (owner :accessor owner :association person)))
>
> This means that job has a slot owner who's values are instances of the
> class person. This slot is also effectively indexed. A person has a
> method jobs which looks up the index in (job owner) and returns the
> list of instances of job that have the instance of A in the owner slot.
>
>
> Many-to-Many:
>
> To add many-to-many relations, any A->B relation also requires that we
> can find the relation from the other direction B->A. Typically this
> requires a special table to keep track of pairs of related objects.
> You can then query on either column to get the set of related objects.
>
> many-to-many association: A<->B
> (A1 B1)
> (A1 B2)
> (A2 B1)
> (A2 B3)
>
> (get-related assoc A1)->B1,B2
> (get-related assoc B1)->A1,A2
>
> We can simply stick with the index model and just ensure that there
> are indexes on both classes instead of one. When we add an element to
> one side, we also add it to the other. (This is what is implemented now)
>
>
> Optimizations/Alternatives:
>
> One optimization for one-to-many is to return a standard object
> implementing the pset protocol that just keeps a reference to the
> index and supports map operations over the appropriate subset of the
> objects in the index.
>
> Regards,
> Ian
>
> On Mar 19, 2008, at 2:42 AM, Marc wrote:
>> Hi Ian,
>>>
>>> My best guess is weeks, not months. We're hoping for April
>>> sometime, but it depends on a number of factors. Elephant is
>>> getting quite complex to test so the last few bugs can take some time.
>>>
>>> You can speed this process up if you want to help develop and test
>>> the association facility (most of the hooks are there so it
>>> shouldn't be too hard, even if you don't fully understand the
>>> elephant internals). If not, we have plenty of new features that
>>> need tests written against them!
>> Since we need this feature anyway for our application, I'm quite
>> prepared to join in the work on the association facility. Any pointer
>> on what would be the best entry point into that task?
>>
>> Best regards,
>>
>> Marc
>>>
>>> On Mar 18, 2008, at 12:50 AM, Marc wrote:
>>>
>>>> Ian Eslick wrote:
>>>>> The pset is probably your best bet. Other collection objects have
>>>>> more performance impact. With a pset you can ask:
>>>>>
>>>>> is X a friend of Y? (find-item X (friends Y)) => X | nil
>>>>>
>>>>> all people that X is friends of:
>>>>>
>>>>> (remove-nulls
>>>>> (map-class 'people (lambda (y)
>>>>> (when (find-item X (friends Y))
>>>>> Y))
>>>>> :collect t))
>>>>>
>>>>> This requires walking all person objects. For larger DB's, you
>>>>> can build your own 'many-to-many' relation table or waiting for
>>>>> the next release which should do this for you.
>>>> Is there a time line (however preliminary) when this release might be
>>>> available?
>>>>>
>>>>> (defpclass friend-relation ()
>>>>> ((first :accessor first :initarg :first :index t)
>>>>> (second :accessor second :initarg :second :index t)))
>>>>>
>>>>> (defmethod add-friend-relation (x y)
>>>>> (make-instance 'friend-relation :first x :second y))
>>>>>
>>>>> (defmethod friends-of (x)
>>>>> (union (mapcar #'second (get-instances-by-slot 'friend-relation
>>>>> 'first x))
>>>>> (mapcar #'first (get-instances-by-slot 'friend-relation
>>>>> 'second x))))
>>>>>
>>>>> Of course there are ways to do this more efficiently, but I think
>>>>> this is the idea.
>>>>>
>>>> Many thanks for this guidance. That does, indeed, give me an idea
>>>> of the
>>>> best way forward in our application.
>>>>
>>>>
>>>> Best regards,
>>>>
>>>> Marc
>>>>
>>>>>
>>>>>
>>>>> On Mar 16, 2008, at 11:06 PM, Marc wrote:
>>>>>
>>>>>> Hello!
>>>>>>
>>>>>> I fear that this may be a rather stupid newbie question, but
>>>>>> neither from the documentation nor from the mailing list posts I
>>>>>> got an idea as to the best practice for the following type of
>>>>>> searches. Let's use an example akin to the one in the tutorial:
>>>>>>
>>>>>> (defpclass person ()
>>>>>> ((name :accessor name :index t)
>>>>>> (friends :accessor friends)) ;collection with names (say as
>>>>>> strings) of the friends of this person
>>>>>> )
>>>>>>
>>>>>> Given a similar structure, what is the recommended way to handle
>>>>>> queries of the type "find all persons that X is a friend of?"
>>>>>> (i.e. queries on individual entries in slots that contain
>>>>>> collections)? What would be the best data structure for the
>>>>>> friends slot, assuming that the collection remains fairly stable
>>>>>> over time (psets, lists or other collections)?
>>>>>>
>>>>>> Thanks in advance for any hint!
>>>>>>
>>>>>> Best regards,
>>>>>>
>>>>>> Marc
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> _______________________________________________
>>>>>> 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
>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>>
>>>> _______________________________________________
>>>> 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
>>>
>>>
>>>
>>
>>
>> _______________________________________________
>> 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
>
>
>
More information about the elephant-devel
mailing list