11

I have a state-machine which needs to push/pop some file-names for different users. I would traditionally use stacks as the choice of data structure, but this needs to be done using a database since I don't have a way to retain the data structure between incoming web-requests.

I was wondering what would be a good way to implement the stack functionality using databases ?

I need to support:

  • push(fileName, user) : push a fileName for the user
  • pop(user) : Pop the top-most fileName for the user

EDIT:

I am prototyping an idea, and so I am using sqlite3 with python.

Thanks!

|improve this question
  • do you expect the same user to have multiple concurrent connections? what volumes? what Db engine too please? – gbn Feb 23 '11 at 19:43
  • @gbn Eventually the same user might have concurrent connections. But for now, I am prototyping an idea and I assume single connection per user – brainydexter Feb 23 '11 at 20:45
  • @brainydexter I would very much like to know what you are trying to do. I get the feeling that you may be creating the wrong solution to your problem. You might want to consider telling us your problem, and asking the best avenue to solve it. Implementing a stack as a database table sounds like a bad idea. – xenoterracide Feb 28 '11 at 10:15
  • @xenoterracide: The overall intent of what I am trying to do at SO: stackoverflow.com/questions/5145051/… Stack didn't work completely, so am still looking for a solution to this. – brainydexter Feb 28 '11 at 17:04
  • 1
    @brainydexter not really surprised, SQL is a horrible language to implement a stack, because by relational definition a set is unordered, so your stack, will have no order, and you would have to sort it. Perhaps part of your problem is you're telling people what you want the answer to be, and you're asking how. Instead of telling them what the problem is, and asking what. Even your SO question leads the answer to something specific. Try asking for the solution you won't think of. – xenoterracide Mar 1 '11 at 14:43
6

If you're asking about which database to use, it really depends on personal preference and what you want out of it. As I'm only familiar with MySQL, I'll answer the other part of the question assuming MySQL:

you will want to use INNODB because your table is going to be write-intensive and for large tables, the row-locking of INNODB will be a life-saver over MyISAM.

As far as table design, it seems you only really need one table:

CREATE TABLE `wordpress`.`<table_name>` (
`id` smallint(4) NOT NULL AUTO_INCREMENT UNSIGNED,
`user` varchar(30) NOT NULL,
`filename` varchar(255) NOT NULL,
`date_insert` datetime NOT NULL,
PRIMARY KEY (`id`),
UNIQUE `userFile`(user, filename)
) ENGINE=`InnoDB`;

I went with an arbitrary 'id' column set to AUTO_INCREMENT because the primary key is replicated in every entry of every index. So, doing a primary key of (user, filename) could cause performance issues if your filenames are extremely long.

The size of your 'id' column depends on how big your table is going to grow. Unsigned Smallint will give you 65k rows.

User and filenames are varchar, because they'll vary on length drastically I assume.

The date_insert is just a way to order your results based on when it was inserted (helpful for your POP)

|improve this answer
  • I was thinking of making (id, user) combination as the primary key, since I'd like to push or pop based on the user. What do you think ? Also, for the POP operation, wouldn't it be better to find the record for the user with maximum id ? – brainydexter Feb 23 '11 at 21:12
  • @brainydexter dev.mysql.com/doc/refman/5.0/en/innodb-restrictions.html has some restrictions on autoincrement (it will re-use 'lower' autoincrement values in certain rare cases). because it's a possibility i went with a date_insert field. As for using (id,user) as Primary key, there's no point except taking up more storage. ID uniquely identifies the row. just 'user' by itself doesn't identify the row, so you could just have a non-unique index on 'userID' instead of a unique (user, filename) if you want. – Derek Downey Feb 23 '11 at 21:24
6

If you considering an Oracle database you should consider using Advanced Queuing with a LIFO (last in first out) dequeue pattern.

At the most basic level of queuing, one producer enqueues one or more messages into one queue. Each message is dequeued and processed once by one of the consumers. A message stays in the queue until a consumer dequeues it or the message expires. A producer may stipulate a delay before the message is available to be consumed, and a time after which the message expires. Likewise, a consumer may wait when trying to dequeue a message if no message is available. An agent program or application may act as both a producer and a consumer.

|improve this answer
  • classic producer/consumer setup. Thanks for the info, I'll keep it in mind. – brainydexter Feb 24 '11 at 16:50
  • Hopefully MySQL will get some Adance Queue functionality now that Oracle "owns" mysql... – Derek Downey Feb 24 '11 at 18:11
  • 1
    @DTest : of course, there's also the distinct possibility that mySQL's now less likely to get advanced features, so Oracle can differentiate between free software and one you have to pay for. – Joe Feb 25 '11 at 13:19
  • @Joe thanks for ruining my weekend with that thought! – Derek Downey Feb 25 '11 at 21:45

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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