Back to Questions
5.5k
views2
comments
Looking for the best data structure
f#functionalocamlb-treehashtriestructuresdata

My youngest son is a C# programmer at a quickly-growing startup. I'm 46, and although I've been coding procedurally my entire career, I'm fairly new (1 year/5 small apps) to functional programming and F#.

He came to me with a question. Here's the setup:

He has a data model that has two tables. Table 1 is for security groups. It is self-referential, that is, each security group can have another security group as a parent -- ad infinitum. (There are no loops. It's a DAG)

Table 2 is just like table 1, except it's for organizational groups. Each organizational group can have another organizational group as a parent, ad infinitum.

So for situation X, a client's security group may be: world-users-administrators-dayworkers. A client's organizational group may be: United States-Virginia-Richmond-Blue Creek Office.

Each combination between security group and organization group can have a rule. So, in our example, there could be a rule for word/United States, a rule for world/Virginia, and a rule for world/Richmond. And so on. Or perhaps there is no rule. It varies. It's sort of like a cartesian product, only it's sparse. (I think)

For any particular web client that connects, he needs a list of the rules that apply. They had been using a database, but the multiple views and such was killing performance -- there's just no way they can look up all these rules each time a client connects. Because the numbers get huge quickly, they also just can't brute-force a cache. So they started caching some pieces of the puzzle and reading others.

Maybe I'm wrong, but I feel like there is a general way to solve this using functional programming, I'm just not sure of the data structures involved. I'm thinking some combination of tries? The trie path would be the list of parent-children, and as you walked each node for say security you would look up the corresponding trie for organization. So it would be a nested trie? yes?

Any help would be appreciated. I started talking to him about sparse trees and realized I got quickly out of my depth.

Thanks!

.

This sounds like a problem that should be solved in the database (SQL is functional). Perhaps the table design or queries need to be optimized? Is there a Rule table with foreign keys to SecurityGroup and OrganizationalGroup? Assuming yes, in SQL Server you could take the following steps to build the rule set:

1. build the SecurityGroup hierarchy using recursive CTE
2. likewise build the OrganizationalGroup hierarchy
3. cross join those two result sets and join that set to the Rule table

It should be possible to make this efficient with appropriate indexes.

By on 1/31/2012 9:10 PM ()

I'm not sure you answered my question, but I really appreciate the response! Maybe I'm missing something or didn't state it clearly enough.

Yes, there's no doubt that a fully-normalized set of tables is the best space-efficient means of storing the data, and SQL is a very functional language. The problem is that the overhead of cross-process communication is simply too much for each hit from a web client. This is why you see most all of the major web services use some sort of key-value RAM-based lookup as a means of keeping performance up.

I could just load up each table into a hashtable and do lookups, but the recursion involved means a lot of lookups for each hit. Since the trie structure allows me to both find the leaf and also walk all the parent nodes, I was thinking that it would be best for what I'm looking for. Perhaps it would scale linearly?

Thanks again for the reply.

By on 2/3/2012 7:11 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper