[elephant-devel] Newbie question: Index on collections
Ian Eslick
eslick at media.mit.edu
Sat May 3 12:59:20 UTC 2008
Definitely work elephant-unstable if you want to test the new
functionality. Most of the activity in the main branch has been in
and around the postmodern interface. The limiting factor in merging
the branches is getting support for the new data store API (i.e. for
btrees w/ duplicate keys) in CL-SQL and Postmodern. Robert has made
some good progress on CL-SQL but we haven't had any work done on this
in Postmodern yet.
I just merged out everything from the main elephant branch into
unstable, so you won't be missing anything; except of course it only
works for the BDB data store now.
Ian
On May 3, 2008, at 3:56 AM, Marc wrote:
> Marc wrote:
>> 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.
> I fear that the delay has been much longer than anticipated --- it
> has been very busy ever after the conference ---, but no w I hope
> finally to find some time --- provided that the issue is not long
> obsolete.
>
> Best regards,
>
> Marc
>
> P. S.: I've noticed that there have been few changes in the unstable
> branch lately, but many more in the stable one. Which one is the one
> to work on for this right now?
>>
>>>
>>> ========================
>>>
>>> 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
>>>
>>>
>>>
>>
>>
>> _______________________________________________
>> 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