in SQL, or Django ORM, what's the conventional way to have an ordered one-to-many?

Question

Say I wanted to have a project, and one-to-many with to-do items, and wanted to re-order the to-do items arbitrarily?

In the past, I've added a numbered order field, and when someone wants to change the order, had to update all the items with their new order numbers. This is probably the worst approach, since it's not atomic & required several updates.

I notice Django has a multi-valued CommaSeparatedIntegerField which could contain the order by storing the ordered keys to the items in the to-do items table right in one field of the project table.

I've pondered a dewey decimal system where if I wanted to take item 3 and put it between 1 and 2 I would change it's order number to 1.5.

Something tells me there's an easier option that I'm missing though...

How would you give order to a one-to-many relationship?

Answer 1

I've run into this so many times that I've settled on managing these dynamically in the BL or UI, and then just persisting the ordering to a purpose-built column once the user is happy. SQL is just intentially designed not to handle orderings, and it always fights back.

Answer 2

I hate this problem ... and I run into it all the time.

For my most recent Django site we had a Newsletter which contained N Articles and, of course, order was important. I assigned the default order as ascending Article.id, but this failed if Articles were entered in something other than "correct" order.

On the Newsletter change_form.html page I added a little bit of jQuery magic using the Interface plugin (http://interface.eyecon.ro/). I show the titles of the associated Articles and the user can drag them around as they like. There is an onChange handler that recomputes the Article.id's in article_order field.

Enjoy,
Peter

For app=content, model=Newsletter, the following is in templates/admin/content/newslettter/change_form.html

{% extends 'admin/change_form.html' %}

{% block form_top %}{% endblock %}
{% block extrahead %}{{ block.super }}
<script type="text/javascript" src="/media/js/jquery.js"></script>
<script type="text/javascript" src="/media/js/interface.js"></script>
<script>
$(document).ready(
    function () {
        $('ol.articles').Sortable(
            {
                accept :        'sortableitem',
                helperclass :   'sorthelper',
                activeclass :   'sortableactive',
                hoverclass :    'sortablehover',
                opacity:        0.8,
                fx:             200,
                axis:           'vertically',
                opacity:        0.4,
                revert:         true,
                trim:           'art_',
                onchange:
                    function(list){
                        var arts = list[0].o[list[0].id];
                        var vals = new Array();
                        var a;
                        for (a in arts) {
                            vals[a] = arts[a].replace(/article./, '');
                        }
                        $('#id_article_order').attr('value', vals.join(','));
                    }
            });
    }
);
</script>
{% endblock %}

{% block after_related_objects %}
{% if original.articles %}
<style>
.sortableitem {
    cursor:move;
    width: 300px;
    list-style-type: none;
    }
</style>

<h4>Associated Articles</h4>
<ol class="articles" id="article_list">
{% for art in original.articles %}
    <li id="article.{{art.id}}" class="sortableitem">{{art.title}}</li>

{% endfor %}
</ol>
{% endif %}
{% endblock %}

Answer 3

"added a numbered order field" - good.

"update all the items with their new order numbers" - avoidable.

Use numbers with gaps.

• Floating point. That way, someone can insert "1.1" between 1 and 2. I find that this works nicely, as most people can understand how the sequencing works. And you don't have to worry too much about how much space to leave -- there's lots and lots of space between each number.

• On the initial load, number the articles by the 100 or 1000 or something with space between each one. In this case, you have to guess how many digits to leave for reordering.

• A comma-separated position. Initially, they're all (1,0), (2,0), (3,0), etc. But when you want to rearrange things, you might have to introduce (2,1) and (2,2) that go after (2,0) but before (3.0).

  This looks kind of complicated, but some people like this kind of complexity. It's essentially the same as floating-point, except the single number is replace by a (whole-number, implicit-fraction) tuple. And this extends to handle hierarchies.

Answer 4

Great answers everyone! Thanks. Peter gets the check for the real-world example.

Answer 5

This is a late answer to the question, but I just wanted to chime in and point out that B-Trees are a great data structure for this sort of thing, especially if your access patterns don't require you to retrieve the entire list at once.

http://en.wikipedia.org/wiki/B-tree