3

To make things easier, the table contains all the words in the English dictionary.

What I would like to do is be able to store the data as a trie. This way I can traverse the different branches of the trie and return the most relevant result.

First, how do I store the data in the table as a trie?

Second, how do I traverse the tree?

If it helps at all, the suggestion in this previous question is where this question was sparked from.

Please make sure it's SQL we're talking about. I understood the Mike Dunlavey's C implementation because of pointers but can't see how this part (The trie itself) works in SQL.

Thanks,
Matt

Community
  • 1
  • 1
Matt
  • 5,547
  • 23
  • 82
  • 121
  • possible duplicate of [How do you store a trie in a relational database?](http://stackoverflow.com/questions/355051/how-do-you-store-a-trie-in-a-relational-database) – Robert Harvey May 28 '10 at 05:31
  • Sorry, I searched up "trie" and "SQL" and didn't get that result pop up, I was under the impression that in those cases duplicates were allowed. Anyways, the answer they gave... wouldn't that turn my table of 1.5 million distinct words into over 10 million records? Is that really the right way to go about it? – Matt May 28 '10 at 05:55
  • If it's really a trie, 10 million records doesn't sound that bad. That should cost you about 100 megabytes or so (give or take an index), which is quite manageable. – Robert Harvey May 28 '10 at 06:46
  • I'm not worried about db size, just how much it's going to affect run time of any queries that hit that table... I don't know much about SQL optimization though, and this trie setup seems like a good option so I'll work with that and see how it goes. – Matt May 28 '10 at 06:57
  • It would be great if you could let us know how it worked out. – Robert Harvey May 29 '10 at 04:49
  • Still working on it. I'll post all the details once I've finish it. Check back in a week or so and it'll be up. – Matt May 29 '10 at 06:25

2 Answers2

1

You model your data hierarchies with SQL Server 2008 using hierarchy id. See this MSDN magazine reference.

Dori
  • 915
  • 1
  • 12
  • 20
renjucool
  • 314
  • 8
  • 19
0

I don't think you need to implement Trie in DB. You can simply use like %~word% query and it would work exactly the same. I don't know your reason for trying to implement Trie in DB but it sounds quite inefficient.

Shlok Ishan
  • 41
  • 5