Re: A searchable datastructure for represeting attributes?

Well thank you all for your responses. To summarize what was said it seems that mine is an annoying problem to have and though it has some solutions none of them are very satisfying.

• CELKO --, I did use words like "keys" and "objects" and "attributes" out of context for this group and they were misleading. I did not mean the word "key" as in phrase foreign key or primary key. I meant it more in the sense of key of a hashtable. I did not use the words attributes in the RDBMS sense but in LDAP sense - a collection of key/value pairs. Sorry for the confusion. After I reread my post in the RDBMS frame of mind I can see how it would not make a lot of sense in the relational meaning of these words.

Ilya, Obnoxio thanks for the pointers I will check them out.

My problem is very legititmate though and does not arise from poor understanding of relational approach to things though I do admit that RDBMS is not quite the right tool for what I need to do. I am not building a migration from "legacy to the web, shopping cart etc" type of application so the critisizm of how it's going to have unit_of_measure and the rest of METABASE related stuff is not applicable here (though generally valid)

By saying that approach_2 is "denormalized in a way" again I used a poor choice of words. I did not mean in Dr. Codd sense of having one piece of data in one place only but in a sense that in my case it is bound to keep lots of uncessary data a critical factor here.

Again, since car seems to be a popular example imagine you have a database of cars in a town where almost 99% everyone likes exactly the same sort of car a blue toyota. If you store a 5 million rows like:

id make color
1 toyota blue
2 toyota blue
3 toyota blue
.....
5000000 totoyta blue

Yes it is very good and normalized in Dr Codd sense but you still store 100 times more information than you need to store with what I described in approach_1. That is absense of a key indicates a default of make=toyota and color=blue. Yes I can see how this is anathema to relational design but it is a real world problem.

The closest analogy is LDAP systems. They are implemented on top of Relational Databases yet they allow to assign a separate schema for every node in the tree and do not waste space for Attributes that have no value assigned to them. I was wondering if there was some established way of representing this kind of situation in the Relational world and that was the essense of my question.

Dre

no_spam_for_me_at_thankyou.very_much wrote:

> THE QUESTION: Is there any good datastructure for representing
> attributes which has the advantages of approach_1 and the search and
> sort convenience of approach_2 below? Seems like a problem many people
> would
> have run into.
>
> 1)
>
> objectid key value
> 78 phone 555-1212
> 78 addr Main Street
> 79 phone 222-2222
> 79 addr Green Street
>
> (keys could be normalized of course but I skip that for this example)
>
> 2)
>
> objectid phone addr
>
> 78 555-1212 Main Street
> 79 222-2222 Green Street
>
> The first approach has several advantages
>
> a) It is flexible. That is you do not need to change the schema to add
> new attribute types.
> b) It is normalized in a sense that if an attribute does not have a
> value you can represent it by its absense in the table istead of
> duplicating NULL in every feild that does
> not have a value. In my case this is actually a critical thing
> because there are a lot of attributes whose values are not set.
>
> Overall the first approach serves my case much better than second
> approach. However it has important disadvantages in that the search by a
>
> combination of attributes as
> well is sort by attributes is very cumbersome and slow. For example if I
>
> wanted to find all objects where phone number is 555-1212 AND address
> equals "Main Street" I would need to
> do a self join like
>
> select t1.objectid from mytable t1, mytable t2 where
> t1.objectid=t2.objectid and t1.phone='555-1212' and t2.addr='Main
> Street'. There are many problems here
>
> 1) very slow when table is large
> 2) you need to do a self join for every attribute in the AND-ed
> expression.
> 3) If you want to sort by an attribute other than the search key you
> need to self join yet again.
>
> By contrast with approach 2 all these problems go away:
>
> select id from mytable where phone='555-1212' and addr='Main Street'
> order by some_field
>
> Thank you so much for your response
>
> Dre
Received on Thu Feb 28 2002 - 14:01:58 CST