A searchable datastructure for represeting attributes?

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

78             555-1212     Main Street
79              222-2222    Green Street

The first approach has several advantages

1. It is flexible. That is you do not need to change the schema to add new attribute types.
2. 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 Wed Feb 27 2002 - 17:16:15 CET