Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I am planning schema for an affiliate network. For all hierarchical queries I am using Postgres tablefunc extension but here is another problem.
Any user can refer only 3 other users at max.
So for example I have this relation of users:

CREATE TABLE users
(
  id serial NOT NULL,
  referred_by integer NOT NULL,
  created_at time without time zone NOT NULL,
  updated_at time without time zone NOT NULL,
  CONSTRAINT primary_key PRIMARY KEY (id),
  CONSTRAINT referred_foreign FOREIGN KEY (referred_by)
      REFERENCES users (id) MATCH SIMPLE
      ON UPDATE CASCADE ON DELETE CASCADE
)

I can use connectby function to query any hierarchy. But when it comes to inserting related models I have to check if a user has not already referred 3 other users before inserting any new user under him. If he already have 3 users then it need to cascade down the tree and put it as a leaf node of tree which is further a heavy query to run on larger hierarchies.

For cascading new users to leaf node Is it possible to determine the nearest node where new user can be put ? for example If this is the data in table:

                    ____________ A ___________
                   /             |            \
                __ B __       __ C __     ____ D ____
               /   |   \     /   |   \   /     |     \
              E    F    G    H   I   J   K     L

And A refers one more user, Now, since A's downline is fully saturated any new user under him should cascade down the tree, and there are 9 places where the new user can be put.

E    F    G    H    I    J    K    L    D

out of which the nearest node is D, so incoming node should go under D instead of E,F..K,L

I have 3 questions:

  1. Most important, Is it possible to restrict the number of records under each user ? I dont want to rely on triggers to check for number of records and cascade down if required. I can change the design if necessary.
  2. How can I 'efficiently' fetch the nearest leaf node of any tree after determining that the root node is saturated ? By efficiently I mean that the same query might need to run a couple hundred times per minute and the data set has no depth limit. Again, I am open for design suggestions if any.
  3. Is it possible to create partial index for referred_foreign so that the first user who will not be referred by anyone can still satisfy the foreign integrity ?

Is there any better design or something that I am missing ? (I know I am missing a lot just dont know what it is)

share|improve this question
2  
Heh, you've just picked a list of things SQL is bad at and said "how can I do all these easily and efficiently" ;-) . Is there any chance you can use PostgreSQL extensions like ltree? If not, I'd probably be looking at recursive PL/PgSQL functions, or maybe a recursive writable CTE. You'll have to think very hard about locking - in particular, you'll need to SELECT ... FOR UPDATE each parent node before inserting a child, to ensure you don't get two concurrent inserts. –  Craig Ringer Feb 5 at 11:10
    
@CraigRinger Yes I've already looked into ltree module but I think I overlooked some of its functionality or I dont completely understand how I can use it in conjugation with other records in database. and of course I need to think about locking, thanks for confirming that I was not over concerned about it. Can you help with some ltree implementations ? –  Gufran Feb 5 at 11:27

1 Answer 1

The following requirement can be easily implemented with a constraint: any user can refer only 3 other users at max.

    CREATE TABLE users
    (
      id serial NOT NULL,
      reference_number SMALLINT NOT NULL,
      CONSTRAINT CHK_reference_number CHECK(reference_number BETWEEN 1 AND 3),
      CONSTRAINT UNQ_reference_number UNIQUE(id, reference_number),
      referred_by integer NOT NULL,
(snip)

Note that your design does not prevent cycles. We can easily enforce that via constraints as well. I can elaborate if you are interested.

Regarding the efficiency of finding qualifying descendants, we can add some redundant data and get much better speed. For example, E is a descendant of A, but not a direct one - B is between them. We can store the following rows:

Ancestor: A
AncestorLevel: 1
Descendant: B
DescendantLevel: 2

Ancestor: B
AncestorLevel: 2
Descendant: E
DescendantLevel: 3

Ancestor: A
AncestorLevel: 1
Descendant: E
DescendantLevel: 3

Once we have this redundant data, finding descendants is easy and fast - just one simple query without recursion. Naturally, with this approach we need substantially more storage.

Of course, with redundant data there is always the risk that it is inconsistent. We can use constraints to enforce the integrity of redundant data. This is complex but doable.

share|improve this answer
    
I see. This is getting closer. please elaborate on your design does not prevent cycles. We can easily enforce that via constraints as well. thanks –  Gufran Feb 5 at 15:13
    
also, when you say 'your design does not prevent cycles' can you suggest any better way to approach this ? I'd prefer a better design. –  Gufran Feb 5 at 15:14
    
@Gufran on preventing cycles: dba.stackexchange.com/questions/14388/… –  AlexKuznetsov Feb 5 at 19:16
    
Thanks, I think in my case having a check like CHECK(ID > ParentID) would do just fine. Because I can't foresee any special condition whe inverse could be the case. –  Gufran Feb 5 at 19:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.