Which table design is prefered when considering database normalization rules:
Consider the following designs for a node table that describes an ordered tree. The key is a composite key.
next.parent = parent.design 1:
node(ck_x, ck_y, parent_ck_x, parent_ck_y, next_ck_x, next_ck_y)
design 2:
node(sk, ck_x, ck_y, parent_ck_x, parent_ck_y, next_ck_x, next_ck_y)
design 3:
node(sk, ck_x, ck_y, parent_sk, next_sk)
The first design has 6 columns. The second design adds a surragete key and has 7 columsn. The third design has 5 colums it uses the surrogate to save a column.
Are there any normalization rules (or other database design rules) that prefer one design over the others?
update
Alternative designs: subtype the node table, isParent flag, nested sets. These designs have a larger read/write complexity.
design 4:
This design splits the table into 3 tables. The parent and next table contain a mutually exclusive subset of the keys from the node table. It uses 2+4=6 columns for each node.
node(ck_x, ck_y)
parent(ck_x, ck_y, parent_ck_x, parent_ck_y)
next(ck_x, ck_y, next_ck_x, next_ck_y)
design 5:
This design uses a isParent flag to indicate that the next item is the parent. It uses 4+1=5 columns, and 1 column is only a bit. Which is less space than 5 columns as used in design 3)
node(ck_x, ck_y, next_ck_x, next_ck_y, isParent)
design 6:
This design uses a nested set to create an ordered tree. The composite key is no longer used to define the parents or the order of the children. It uses 2+2=4 columns. But the lower and upper bound column should be both using the sizeof(ck_x)+sizeof(ck_y) which is equal the space of 6 columns used in design 1.
node(ck_x, ck_y, lowerBound, upperBound)
update
design 7:
this uses a index for the position of the node.
node(ck_x, ck_y, parent_ck_x, parent_ck_y, index)
Notes
Using the previous node i.s.o. the next node reduces creation and addition to a single insert compared to insert and update.
Normalization is not about the number of columns or tables.
TL;DR Guessing from what you have given us: From the likely functional dependencies (which determine candidate keys) from how you appear to be representing trees, all of these designs are in 5NF. No design here needs to be changed for reasons of normalization.
Normalization replaces a table by other tables without introducing new columns. Normalization to BCNF requires knowing all functional dependencies; normalization beyond that requires knowing about join dependencies. That requires knowing what a row states about the situation by being in a table and what situations can arise. (If we know that some columns are unique then we know that they functionally determine all columns.)
First pick designs by which you can describe any situation that can arise and by which you can express queries about those situations. Normalization might then improve a design (in terms of reducing update anomalies or certain redundancies), but other aspects of the appropriateness or quality of your design are independent of normalization. Tree-structured relation designs must be chosen with care to suit intended usage and DBMS characteristics.
PS 1 Normalization does not introduce surrogates. Functional dependencies matter; you haven't given them. Candidate keys matter; you haven't given them. (Primary keys only matter in that they are candidate keys.) Read about the basic notions and steps of normalization.
PS 2 The constraint on linked-list siblings sharing the same parent is not addressed by normalization. Just because there are repeated values there needn't be redundancy; redundancy is about repeated statements made by rows being in or not in tables. Re "redundancy". In fact the obvious basic relational way to describe a tree is just a table "parent P has child C" or "parent P has Nth child C". You are relationally representing a tree. Don't relationally represent a (non-relational) representation of a tree.
PS 3 Your concern with the number and size/space of columns (including use of surrogate keys) is almost certainly misdirected. Just make the most straightforward design given your queries and updates. (Which, again, you haven't described.)