I know that this sort of goes against the principles of a relational database but let me describe the situation.
I have a page where the user will place a number of items.
________________
| -Item1 |
| -Item2 |
| -Item3 |
| -Item4 |
|________________|
These items have must stay in a the order the user gives them. However this order may be changed an arbitrary number of times by the user.
________________
| -Item1 |
| -Item4 |
| -Item2 |
| -Item3 |
|________________|
Approach 1
My original thought was to give the items an index to represent thier place in the list
Page Item
----------- ---------------
FK | pid FK | pid
| name PK | iid
| index
| content
With this solution you can select items where pid = Page.pid and order by index which is convenient. However every time you change the order you have to change anywhere between one other item (best case) and all the other items (worst case).
Approach 2
I also considered making a "linked list" like data structure where each item points to the next item in the list.
Page Item
----------- ---------------
FK | pid FK | pid
| name PK | iid
| next
| content
This potentially makes changing the order less expensive but we would have to rely on front end programming to extract the order.
Is there an approach that I haven't thought of? Please let me know.
I think @a1ex07 is on the right track here (+1). I don't think gaps in itemOrder violate 3NF, but I do worry about a different violation of 3NF (more on this below). We also have to watch out for bad data in the itemOrder field. Here's how I'd start:
create table pages (
pid int,
primary key (pid)
);
create table users (
uid int,
primary key (uid)
);
create table items (
iid int,
primary key (iid)
);
create table details (
pid int not null references pages(pid),
uid int not null references users(uid),
iid int not null references items(iid),
itemOrder int,
primary key (pid, uid, iid),
unique (pid, uid, itemOrder)
);
The primary key ensures that for each page, for each user, there are unique items. The unique constraint ensures that for each page, for each user, there are unique itemOrders. Here's my worry about 3NF: in this scenario, itemOrder is not fully dependent on the primary key; it depends only on the (pid, uid) parts. That's not even 2NF; and that's a problem. We could include itemOrder in the primary key, but then I worry that it might not be minimal, as PKs need to be. We might need to decompose this into more tables. Still thinking . . .
[ EDIT - More thinking on the topic . . . ]
Assumptions
There are users.
There are pages.
There are items.
(page, user) identifies a SET of items.
(page, user) identifies an ordered LIST of slots in which we can store items if we like.
We do not wish to have duplicate items in a (page,user)'s list.
Plan A
Kill the details table, above.
Add a table, ItemsByPageAndUser, to represent the SET of items identified by (page, user).
create table ItemsByPageAndUser (
pid int not null references pages(pid),
uid int not null references users(uid),
iid int not null references items(iid),
primary key (pid, uid, iid)
)
Add table, SlotsByPageAndUser, to represent the ordered LIST of slots that might contain items.
create table SlotsByPageAndUser (
pid int not null references pages(pid),
uid int not null references users(uid),
slotNum int not null,
iidInSlot int references items(iid),
primary key (pid, uid, slotNum),
foreign key (pid, uid, iid) references ItemsByPageAndUser(pid, uid, iid),
unique (pid, uid, iid)
)
Note 1: iidInSlot is nullable so that we can have empty slots if we want to. But if there is an item present it has to be checked against the items table.
Note 2: We need the last FK to ensure that we don't add any items that are not in the set of possible items for this (user,page).
Note 3: The unique constraint on (pid, uid, iid) enforces our design goal of having unique items in the list (assumption 6). Without this we could add as many items from the set identified by (page,user) as we like so long as they are in different slots.
Now we have nicely decoupled the items from their slots while preserving their common dependence on (page, user).
This design is certainly in 3NF and might be in BCNF, though I worry about SlotsByPageAndUser in that regard.
The problem is that because of the unique constraint in table SlotsByPageAndUser the cardinality of the relationship between SlotsByPageAndUser and ItemsByPageAndUser is one-to-one. In general, 1-1 relationships that are not entity subtypes are wrong. There are exceptions, of course, and maybe this is one. But maybe there's an even better way . . .
Plan B
Kill the SlotsByPageAndUser table.
Add a slotNum column to ItemsByPageAndUser.
Add a unique constraint on (pid, uid, iid) to ItemsByPageAndUser.
Now it's:
create table ItemsByPageAndUser (
pid int not null references pages(pid),
uid int not null references users(uid),
iid int not null references items(iid),
slotNum int,
primary key (pid, uid, iid),
unique (pid, uid, slotNum)
)
Note 4: Leaving slotNum nullable preserves our ability to specify items in the set that are not in the list. But . . .
Note 5: Putting a unique constraint on a expression involving a nullable column might cause "interesting" results in some databases. I think it will work as we intend it to in Postgres. (See this discussion here on SO.) For other databases, your mileage may vary.
Now there is no messy 1-1 relationship hanging around, so that's better.
It's still 3NF as the only non-key attribute (slotNum) depends on the key, the whole key, and nothing but the key. (You can't ask about slotNum without telling me what page, user, and item you are talking about.)
It's not BCNF because [ (pid, uid, iid) -> slotNum ] and [(pid,uid,slotNum) -> iid ]. But that's why we have the unique constraint on (pid, uid, slotNum) which prevents the data from getting into an inconsistent state.
I think this is a workable solution.