3

This question branches out of this question, What are the differences between algorithms using data structures and algorithms using databases?.

The General Question

Should a database table(s) structure match its intended data structure(s) in the logic?

Some Context

The simplest example (and it may be oversimplified) of what I am thinking about is a database table whose columns match the properties of a linked list data structure. So the properties I think of for a linked list are the following:

Linked List

  • Node identity.
  • Item/Content in node.
  • Next node.

In regards to the general question, the database table columns that I think of getting mapped are the following:

Linked List > Database Table

  • Node Identity > Primary Key Column(s).
  • Item/Content in node > Column(s) containing data that is to be persisted.
  • Next node > Column containing a reference to the record that is to follow it in the same table.

An application I can think of that represents the above is to say, keep track of a trail of points you have been to on a map. So I can imagine saving the coordinates of point A then putting in the mapped Next node column, the coordinates of point B. Letting my imagination run a little further, then retrieve this data and load it into a linked list, use its properties to do the traversal, and draw these points on a map again at a later point in time.

Questions

  1. I can see how creating a mapping like this simplifies thinking about the data, but I also feel it restricts you to thinking about the data in only this way. How conforming do you make your database tables to data structure(s), if at all?
  2. Should databases be viewed as realms of raw data that are to be shaped and molded (translated) to data structures selected dependent on the program's purpose?

I restate what I said in the last post. I know answers without a specific context are difficult. Food-for-thought, advice, or discussion points are mainly what I'm looking for and would be most appreciated! I did try to give a more specific context in this post.

0

6 Answers 6

5

As a database person I want to throw up at the idea of someone designing a database table that way.

Database tables should be designed using three main criteria:

  1. Data integrity
  2. Performance of querying the database
  3. Data security

A good database design often needs fields that are not used by the application in any way (but may be needed for data imports or auditing or for some other reason) and in many databases, multiple applications will need to access the data and have differing needs.

What looks easy to do for data entry screens may not work at all for reporting (which is often a totally different application that the developer designing only for his logic doesn't even know about) because reports tend to deal with larger data sets than data entry screens which typically only concern one record at a time. So a database struture that looks logical from the application programmers perspective (Like an EAV table, shudder!) can be the worst possible thing to use when getting data back out of the database later. Especially if there will be millions of records.

Databases are optimized to use normalized tables and should be designed with normalization priciples in mind not using Object-oriented principles. Yes there is mismatch between what is best for the database and what is best for an object-oriented application. Yes you have to deal with that and no it isn't a good idea to deal with it by making the database match the orject-orientation.

2
  • Apologies for making you throw up. +1 for the criteria, thanks! Jan 4, 2013 at 22:08
  • 1
    Sorry but you hit on one of my pet peeves. Too many databases are designed in a short sighted manner and with agile and ORMs it is my observation that it is getting worse and the data quality is getting worse. Databases will generally be there years after the orginal application and need to be designed for the long term.
    – HLGEM
    Jan 4, 2013 at 22:40
6

Square Peg, Round Hole

I can see how creating a mapping like this simplifies thinking about the data, but I also feel it restricts you to thinking about the data in only this way. How conforming do you make your database tables to data structure(s), if at all?

I don't conform the database, at all. Assuming the benefits to be gained from a particular data structure in code can be mapped directly to the database is a failure to understand the strengths of databases.

It's a good idea to represent data in it's truest form, stripped of implementation because the implementation will most likely change over time.

The simple rule is,"separate data from implementation".

Should databases be viewed as realms of raw data that are to be shaped and molded (translated) to data structures selected dependent on the program's purpose?

Ask yourself this. Would you duplicate all of the functionality of a database in code (including indexing, primary keys, foreign keys, etc)? Of course not, because in the context of the program they don't add any value.

All you want is data matching the parameters you input.

It's best to model the structure of the database in the best possible manner for storage retrieval, and model the data structures in the application in the best manner for how they will be used in code.

You won't understand how to build an ideal database until you gain a firm understanding of what databases are designed to accomplish.

The point is, there is no 1-1 mapping from DB to any data structure. The database could be considered it's own type of higher level special purpose data structure based on a whole collection of lower level data structures.

2
  • So your answer is yes/(yes with reservations) to the second question regarding translation of data? Jan 4, 2013 at 21:25
  • @hulkmeister: As I read the answer, it can be summarized as: No, a database should be viewed as a data structure in its own right, same as a list, (dynamic) array or tree. Jan 5, 2013 at 11:44
1

Specifically for the linked list situation: in SQL-databases it is usually far easier to store an 'ordering' field (numerical) which is renumbered if you ever want to insert or remove a node: even updating a large number of columns (ordering = ordering+1) is usually fast. Navigating a list of linked nodes is very unpractical, since you can't do it with a simple query.

This in itself is a perfect example why datastructures and implementation don't always map well to each other.

2
  • The same is even more true for in-memory data structures. So this leads to: since linkeds lists have seldom advantages over arrays with an ordering field, don't use them if you don't have a very specific reason, neither in DB nor in-memory, which results again in a DB which is modeled equally to the in-memory structure. So are those models then equal again because the DB model follows the in-memory model?
    – Doc Brown
    Jan 5, 2013 at 10:34
  • There's virtually no reason to ever model a linked list in a database as you never do things like manually sorting the data. Instead, you put the information which the data would be sorted over as a column in the table and state that that's an ordering constraint in the query. With an index, that's as fast as manual sorting, but far more consistent logically, and it allows the data to support many different sort orders according to what makes sense for the queries in use. Jan 5, 2013 at 22:47
0

To be perfectly blunt, this sounds like a bad idea. This model mixes up some things which should stay separate.

From this spec, I see three data tables list, node, datum.

list

  • id
  • name

node

  • id
  • position_in_list
  • list_id
  • datum_id

datum

  • id
  • data_value_1
  • data_value_2

OK, so obviously you won't have a datum table, but it's a placeholder for your real data.

A list name 'foo' in the can then be reconstructed with:

SELECT datum.*
  FROM datum
  LEFT JOIN node ON datum.id = node.datum_id
  LEFT JOIN list ON node.list_id = list.id
WHERE list.name = 'foo'
  BY node.position_in_list
0

Short answer: NO

Longer answer:

A single database can be used my many applications, and one application can use many databases.

Also: program against views, not against tables.

0

Should a database table(s) structure match its intended data structure(s) in the logic?

In short: NO, it is a technical failure to think in that way.

Any project should have its database design and structure based on ONLY and ONLY on business requirements that are provided and approved by the project stake-holders. Any minor alterations and improvements to DB structure might potentially be done in the later stages of the project, depending on trade-offs of performance and usability.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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