How to efficiently store and display nested data?

Question

Say, I have a nested structure that is not arbitrary depth. E.g. employees and departments.

The most frequent use I want to support is to display a list of departments and its employees, with paging (X employees/page, not department). Something like this:

 - Department A
  - Person 1
  - Person 2
  - ...
 - Department B
 - ...

How should I store them? And, how should I query them?

My solution so far:

It seems the structure will work nicely with document-based stores (or maybe key-value stores). But, I don't know how to do paging in this scenario.

If I use a relational database, the best I can think of is to fetch X number of employees, and order by the department column in SQL; when displaying, we open a new section for that department if the current person is in a different department than the previous.

Update with an example for a flask solution:

This is what I can do with a flat table or with a join; Jinja's groupby does internal sorting, and applies the logic I stated above.

Let employees be a list of X employees.

<ul>
{% for department in employees|groupby('department') %}
<!-- this is the department name -->
    <li>{{ group.grouper }}
        <!-- list of employees -->
        <ul>
        {% for employee in group.list %}
            <li>{{ person.department_name }} {{ person.name }}</li>
        {% endfor %}
        </ul>
    </li>
{% endfor %}
</ul>

This is what Jinja do in groupby: sorted(map(_GroupTuple, groupby(sorted(value, key=expr), expr)))

Update 2:

My only question is How do I display a one-level nested relationship like above (see the department/person tree)? The storage and querying aspects are the details I want to know about (and to emphasize that the problem is flexible about these options). I initially asked about how it can be extended further to multiple level of nesting, and it is indeed unnecessarily confusing, so that is removed.

Neil has commented hat the data model should be the same "whether or not you are paginating" and whether or not you have "one level or multiple levels of department nesting." Fair enough; if it can be done nicely with the same model, I am happy. For comment #4, if I sort in SQL (and not in python) I can get rid of the inner sorted in the above Jinja code, which may or may not have some benefits.

For comment #2, although "pagination with tree-like GUI widgets" may not be often seen, I do still want it; the fact it is not popular doesn't really change my problem.

Answer 1

UPDATE:

You're asking several questions at once here, so it might be better to split this question into a few independent ones.

Some comments:

1. Your data model should be the same whether or not you are paginating in your UI
2. You don't often see pagination with tree-like GUI widgets, more "start with one branch expanded and request more data if another branch is expanded". Or you could have hyperlinks for each department/subdepartment that show only its employees and deparments
3. Do you have one level or multiple levels of department nesting? You seem to be asking for both. Your data model should be the same either way actually.
4. If you want a stable display order, add a display_order column (a good ORM can update this for you automatically)

My answer is for SQL.

It depends if the data is purely hierarchical, or is graphical (can have more than one parent).

If hierarchical:

create table foo (
  foo_id int primary key,
  name text
);

create table bar (
  bar_id int primary key,
  name text,
  parent_id int null references foo(foo_id)
);

If graphical:

create table foo (
  foo_id int primary key,
  name text
);

create table bar (
  bar_id int primary key,
  name text
);

create table foo_bar (
  foo_id int references foo(foo_id),
  bar_id int references bar(bar_id),

  primary key (foo_id, bar_id),

  check (foo_id <> bar_id)
);

You would use Recursive Common Table Expressions to query these structures (protip: don't use MySQL). A Recursive CTE example. Also How does a Recursive CTE run, line by line?

In the real world, people are sometimes assigned to multiple departments (or work for more than one company), so it's probably a graphical relationship.