This is the second article in the series; the previous one introduced the problem and specified domains.
| Part | Main Topic | Code (pgSQL) |
|---|---|---|
| 1 | Domains, Types | part 1 |
| 2 | Predicates, Constraints, Relations | part 2 |
The Essence
The idea is to describe the problem using natural language and concepts of domains, predicates, constraints, relations and keys; here are a few simple rules to keep in mind.
From predicates and constraints to relations and keys
- A predicate variable — from a specific domain — maps to an attribute of the relation.
- Internal (to predicate) uniqueness constraints map to keys of the relation.
- External (to predicate) inclusion constraints map to foreign keys between two relations.
- A predicate and the matching relation represent — evaluate to — a set of facts about the universe of discourse (the problem).
- A predicate and the matching relation should not be separated, otherwise information will be lost, for all practical purposes.
For SQL implementation
- Relations map to tables.
- Derived relations map to views.
- Attributes map to columns.
- Domains map to data types.
- A key maps to a primary key or an alternate key (unique constraint).
- A foreign key maps to a foreign key.
- Predicates and constraints are added as comments on matching database objects (tables, keys).
Predicates, Constraints, Relations
[p_01] The column labelled (CL) with the assigned column number (CL_NO) exists.
(c1.1) Each column is assigned exactly one column number.
(c1.2) Each column number is assigned to exactly one column.
a_col { CL col_lbl -- p_01
, CL_NO ordinal_num
}
KEY {CL} -- c1.1
KEY {CL_NO} -- c1.2
[p_02] The row labelled (RW) with the assigned row number (RW_NO) exists.
(c2.1) Each row is assigned exactly one row number.
(c2.2) Each row number is assigned to exactly one row.
a_row { RW row_lbl -- p_02
, RW_NO ordinal_num
}
KEY {RW} -- c2.1
KEY {RW_NO} -- c2.2
[p_03] The board square named (SQUARE) is located in the row labelled (RW) and the column labelled (CL).
(c3.1) Each square is located in exactly one row; for each row it is possible that more than one square is located in that row.
(c3.2) Each square is located in exactly one column; for each column it is possible that more than one square is located in that column.
(c3.3) For each row and column, exactly one square is located in both that row and that column.
(c3.4) If a square is located in a row then that row must exist.
(c3.5) If a square is located in a column then that column must exist.
board { SQUARE square_name -- p_03
, CL col_lbl
, RW row_lbl
}
KEY {SQUARE} -- c3.1, c3.2
KEY {CL, RW} -- c3.3
FOREIGN KEY {RW} -- c3.4
REFERENCES a_row {RW}
FOREIGN KEY {CL} -- c3.5
REFERENCES a_col {CL}
[p_04] The line identified by the starting square (ANCHOR) and the direction of movement (MOV_DIR) exists.
(c4.1) Each line is identified by exactly one starting square and direction of movement combination.
(c4.2) If a starting square is part of a line identifier, then that square must exist.
line { ANCHOR square_name -- p_04
, MOV_DIR mov_dir
}
KEY {ANCHOR, MOV_DIR} -- c4.1
FOREIGN KEY {ANCHOR} -- c4.2
REFERENCES board {SQUARE}
[p_05] The square named (SQUARE) is located on the line identified by the starting square (ANCHOR) and the direction of movement (MOV_DIR).
(c5.1) For each square, that square may be located on more than one line.
(c5.2) For each line, that line may contain more than one square.
(c5.3) For each square and line, that square and line combination occurs at most once.
(c5.4) If a square is located on a line then that square must exist.
(c5.5) If a square is located on a line then that line must exist.
square_line { SQUARE square_name -- p_05
, ANCHOR square_name
, MOV_DIR mov_dir
}
KEY {SQUARE, ANCHOR, MOV_DIR} -- c5.3, c5.2, c5.1
FOREIGN KEY {SQUARE} -- c5.4
REFERENCES board {SQUARE}
FOREIGN KEY {ANCHOR, MOV_DIR} -- c5.5
REFERENCES line {ANCHOR, MOV_DIR}
For convenience I will add a relation that allows me to access a square by name, row and column labels, or row and column numbers. This can be derived from the existing relations: board, a_col, a_row.
[p_06] The board square named (SQUARE) is located in the row labelled (RW), row number (RW_NO); and the column labelled (CL), column number (CL_NO).
-- derived relation
--
board1 { SQUARE square_name -- p_06
, CL col_lbl
, RW row_lbl
, CL_NO ordinal_num
, RW_NO ordinal_num
}
KEY {SQUARE}
KEY {CL, RW}
KEY {CL_NO, RW_NO}
-- derive using
--
board1 = {SQUARE, CL, RW}
JOIN {CL, CL_NO}
JOIN {RW, RW_NO}
board1 = JOIN {board, a_col, a_row}
There is one more predicate and relation to consider: the actual solution. At this point we do know that eight queens have to be placed on eight squares, and that there may be more than one solution. There will be some kind of calculation (algorithm) involved so the final relation will be derived from others.
[p_07] Placing queens on squares (S1), (S2), (S3), (S4), (S5), (S6), (S7), and (S8) is a solution to the puzzle.
(c7.1) A solution is identified by combination of squares S1 … S8.
-- derived relation
--
solution { S1 square_name -- p_07
, S2 square_name
, S3 square_name
, S4 square_name
, S5 square_name
, S6 square_name
, S7 square_name
, S8 square_name
}
KEY {S1, S2, S3, S4, S5, S6, S7, S8} -- c7.1
SQL Implementation
Creating an entity-relationship model is purely optional, but it does help.
Again, the translation from the reasoning to the SQL code is straightforward, here is the part 2 of the code.
What we have now are essentially empty relational variables. The relational variables a_col, a_row, board, line, and square_line need actual relational values to represent sets of facts about the chessboard.
Next time: relation values, propositions, and facts.