I had a bit of trouble fully understanding the EAV concept or the pldb
code. There's not a good overview of EAV architecture that doesn't focus
on databases. I'm not much of a DB guy. So, I'm not sure if I got the
essence of the EAV pattern with my new implementation, but here it is
anyway:
I think the legacy of object-orientation was so embedded in my brain that I
failed to see the simple solution: rows and columns. I was thinking of
items in the map as "containers" of items, when I could have been thinking
of them as rows in a table. The table is effectively a sparse matrix.
The implementation's main map is of type { [row col]->Item }. It also uses
two other maps: row-idx:{row->{col item}} and col-idx:{col->{row->item}}.
Whenever an assoc occurs on key [r c] and item i, here is how the values
are updated:
main-map<-(assoc main-map [r c] i)
row-idx<-(assoc-in row-idx [r c] i)
col-idx<-(assoc-in col-idx [c r] i)
This way, we efficiently maintain row-idx and col-idx, two complementary
nested maps that mirror each others' structure.
Did I get close to the EAV pattern here? Also, I wonder if this approach
is scalable to higher-dimensional tables, for instance where each item is
associated with a 3-tuple.
On Monday, 18 April 2016 17:18:45 UTC-7, tbc++ wrote:
>
> Core.logic has one such implementation:
> https://github.com/clojure/core.logic/blob/master/src/main/clojure/clojure/core/logic/pldb.clj
>
> <https://www.google.com/url?q=https%3A%2F%2Fgithub.com%2Fclojure%2Fcore.logic%2Fblob%2Fmaster%2Fsrc%2Fmain%2Fclojure%2Fclojure%2Fcore%2Flogic%2Fpldb.clj&sa=D&sntz=1&usg=AFQjCNGjJWdatQscPmDIx3xpBMuwPmOH7A>
>
> might be a place to start.
>
> On Mon, Apr 18, 2016 at 5:35 PM, JvJ <[email protected] <javascript:>>
> wrote:
>
>> Can you point me to a working example of one of these structures?
>>
>> On Monday, 18 April 2016 16:30:17 UTC-7, tbc++ wrote:
>>>
>>> And by "fairly common these days", I mean that I run into this sort of
>>> structure a lot in clojure with anything that is trying to logic or query
>>> operations. Probably isn't that common outside of projects in that domain.
>>>
>>> On Mon, Apr 18, 2016 at 5:28 PM, Timothy Baldridge <[email protected]>
>>> wrote:
>>>
>>>> assoc-in is defined in terms of assoc:
>>>> https://github.com/clojure/clojure/blob/clojure-1.7.0/src/clj/clojure/core.clj#L5901
>>>>
>>>> And this structure is fairly common these days, it's basically a index
>>>> of tuples [e a v], and you're creating a eav index and then an av index.
>>>> Datomic does this same sort of thing, for the datom [e a v t] it creates
>>>> indices for :eavt :avet and a few others that escape my memory at the
>>>> moment.
>>>>
>>>> On Mon, Apr 18, 2016 at 5:08 PM, JvJ <[email protected]> wrote:
>>>>
>>>>> I'm implementing a map data structure where most of the values are
>>>>> maps or sets, and these values can be cross-indexed by the keys they
>>>>> contain. I don't know if it already has a name, but I'm calling it a
>>>>> cross-map. It's similar to a two-way map, but they're not the same thing.
>>>>>
>>>>> For instance, a common operation would be something like "give me all
>>>>> values of this map that contain the key :a."
>>>>>
>>>>> In order to do this efficiently, I'm maintaining a second map that
>>>>> maps keys in the values of the main map to keys of the main map whose
>>>>> values contain that key.
>>>>>
>>>>> If that sounds confusing, consider this:
>>>>> main-map:
>>>>> {:foo {:a 1 :b 2} :bar {:a 2 :c 4} :baz {:b 3 :c 5}}
>>>>>
>>>>> Corresponding cross-indices:
>>>>> {:a #{:foo :bar} :b #{:foo :baz} :c #{:bar :baz}}
>>>>>
>>>>> As you can see, each key maintains references to those entries where
>>>>> it is found.
>>>>>
>>>>> When a nested update occurs that adds an entry to one of the main
>>>>> map's values, the efficient thing to do would be to simply conj that new
>>>>> key onto its corresponding cross-index set.
>>>>>
>>>>> However, I am trying to implement this as a clojure IPersistentMap,
>>>>> and the only method I can override is assoc, not assoc-in.
>>>>>
>>>>> Using regular assoc, I would have to compare the old value's keys to
>>>>> the new value's keys and find the set difference of the two, which is not
>>>>> an O(1) operation.
>>>>>
>>>>> Is there any way to override the behaviour of nested associations or
>>>>> updates?
>>>>>
>>>>> Thanks
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Clojure" group.
>>>>> To post to this group, send email to [email protected]
>>>>> Note that posts from new members are moderated - please be patient
>>>>> with your first post.
>>>>> To unsubscribe from this group, send email to
>>>>> [email protected]
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/clojure?hl=en
>>>>> ---
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Clojure" group.
>>>>> To unsubscribe from this group and stop receiving emails from it, send
>>>>> an email to [email protected].
>>>>> For more options, visit https://groups.google.com/d/optout.
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> “One of the main causes of the fall of the Roman Empire was
>>>> that–lacking zero–they had no way to indicate successful termination of
>>>> their C programs.”
>>>> (Robert Firth)
>>>>
>>>
>>>
>>>
>>> --
>>> “One of the main causes of the fall of the Roman Empire was that–lacking
>>> zero–they had no way to indicate successful termination of their C
>>> programs.”
>>> (Robert Firth)
>>>
>> --
>> You received this message because you are subscribed to the Google
>> Groups "Clojure" group.
>> To post to this group, send email to [email protected]
>> <javascript:>
>> Note that posts from new members are moderated - please be patient with
>> your first post.
>> To unsubscribe from this group, send email to
>> [email protected] <javascript:>
>> For more options, visit this group at
>> http://groups.google.com/group/clojure?hl=en
>> ---
>> You received this message because you are subscribed to the Google Groups
>> "Clojure" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to [email protected] <javascript:>.
>> For more options, visit https://groups.google.com/d/optout.
>>
>
>
>
> --
> “One of the main causes of the fall of the Roman Empire was that–lacking
> zero–they had no way to indicate successful termination of their C
> programs.”
> (Robert Firth)
>
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
