General Database questions

Game Play & Game Design
#1

(I couldn’t find a good forum for this post so I put it here)

I am designing the database for my current online game. The problem I am having is the arrangement of lists. For example, if I have 10 items on my character and I save him to the database…I have to have 10 differen’t columns for these items. What about the person who hordes everything? I would need much may, say 100 columns.

This is not practical. So I am looking to find a solution so I can still use databases rather then flat files. One solution I have is to put it in 1 column titled, “items” which would hold the item IDs. Each item would them be broken up with a comma. When the server loads this column they will parse it for item IDs and then in turn, load them from the item DB based upon the IDs.

Example:
Items
1,2,3

So the player has items 1 2 and 3. (I would have to do more then this because items could be in a certain condition, or there could be more then 1).

Another solution would be to just increase the number of columns, which before I said wasn’t very practical.

So my overall question is: how do you design a DB for data that is unknown in length and size and can be very big?

Thank you.

#2

I took a break and then thought about it some more. I came up with this.

A table with the ID and the owner will be put there. The number of items will equal the number of items. Then, all is well.

Sometimes I just get so caught up with things and it’s hard to see the answer in front of you.

#3

Good! The question you asked is part of the fundamental design of RDBMS’s, so I’m glad you worked out the official way you’re supposed to do it ;).

If you’re interested, google for “1st normal form” and “normalized data” with DB and have a read. You might learn some useful ideas from it that help with your organization of data.

But just don’t ever try and store a tree in an RDBMS. Try it, if you’re bored, but it’s not fun and it’s slow.

#4

I’ll take the bait on that.

A binary tree is simple enough, columns for parentNodeID, nodeID, data, leftChildNodeID and rightChildNodeID. It’s quick to go either way in the tree (up or down). You do need to know the id of the root though.

A tree with any number of child nodes is a bit more awkard. I suspect that parentNodeID, nodeID and data are about all you can do efficiently. Maybe indexes on parentNodeID and nodeID, that way to find out all the children of a particular node is a case of searching an indexed column. Still not ideal, but it should work.

Next! :slight_smile:

Endolf

#5

The problem is that access time tends to be (at best!) linear in the depth of the tree :(. And you get all sorts of fun trying to keep optimal indexes in memory to do it :). You can do better, of course (hence … if anyone wants something to play with, it can be interesting), but the best way is generally via access to the underlying DB implementation, since trying to be strictly Relational is the bugger that makes it all hard.

If your tree has a depth of 100 nodes, it can get real nasty real quick.

Also … if you come up with something that’s substantially better than plain linear on SQL then you might be able to make the openLDAP people happy - IIRC their main implementation of LDAP is a fairly straightforward tree overlaid on MySQL. At least, it was the last time I looked.

#6

RDBMS suck :slight_smile:

If you want it easy: http://www.db4o.net

#7

Sadly I do not have enough money to pay for that.

#8

db4o is GPL, or ask them for sponsorship.

Or try any other like http://odb.neodatis.org/ http://speedo.objectweb.org/

In any case I’d avoid O/R mapping, this sucks so much. Last fallback: Hibernate

#9

storing xml stuff in databases is becoming an increasingly used thing,since they are tree-like.

any self refering relation (directly or indirectly) provides you a tree, in a rdbms.

by ‘strictly Relational’ you mean avoiding redudancy and enforcing referencial integity or do you mean avoid some kind of mulplexing/direct storage.

#10

A tree depth of 100?! So, 2^100 items in a binary tree; more in other kinds of trees?! “What the heck are you storin’ in that thar thing o’ yours, son?!?!”

I’m just getting to the point where I’m about to store oct-tree data in a DB, although I’ve not started, yet. My problem is that the entire oct-tree doesn’t fit in memory at once (because I do have a bazillion items), so I’m planning to use the RDBM to help me cull. Each item has an “address” indicating it’s oct-tree node, vis: R17023 (meaning the 3rd octant off the 2nd octant off the 0th octant off the 7th octant off the 1st octant off the root.) Conveniently, the parent node is simply R1702; it’s parent is R170, etc. :slight_smile:

Anyway, I’m thinking that I can get a set of potential collisions by asking the DB for objects with ADDRESS LIKE “R17023%” OR ADDRESS=“R1702” OR ADDRESS=“R170” OR Address=“R17”…

Am I about to step into a world of hurt? This seems really logical to me; is there some widely known better way?

Thanks!

#11

There is nothing illogical about it, but also there is nothing relational about it, hence you’ll find you’re not benefitting from the normal speeds of an RDBMS, and you can expect that the DB will probably be significantly slower than your own hand-written implementation would be. Possibly a lot slower, depending upon vendor. There is little reason for an RDBMS to be optimized for non-RelationalDBMS work :). (although, off the top of my head, a lot of the common ones like MySQL are so frequently abused like this that they do have some support for it. Even with MySQL though, IME, that support is SO little that it’s fairly rapidly outclassed by a quick n dirty manual implementation using flat files. Really)

All I’m trying to say is … if you do trees with RDB’s, you can throw out the window all the conventional wisdom on “DB’s are faster and better than the manual flat files you’ll come up with, by a long way”. They’re still safer, since they still have transactions, and binary logs, etc - but can be very slow.