· Guides

AP Subject A #13: Database keys, functional dependencies, and normalization

Keys and attribute closure, full, partial and transitive dependencies, anomalies, 1NF to 3NF, lossless decomposition and the BCNF boundary for AP Subject A, with five original questions.

応用情報技術者試験科目Aデータベース正規化関数従属

AP Subject A · Installment 13 · An independent study resource for the 2026 exam and Syllabus Ver.7.2. It is not affiliated with IPA and does not guarantee a pass. Open the series hub

This is an independent study note with no affiliation with IPA. It contains no copied third-party commentary, uses no past exam questions, and does not guarantee a pass.

Learning index

1. Official scope

  • Source: IPA 応用情報技術者試験（レベル3）シラバス Ver.7.2 — https://www.ipa.go.jp/shiken/syllabus/omgdg50000005kq5-att/syllabus_ap_ver7_2.pdf (checked 2026-10-21; database design and normalization at PDF pp. 42–43 (printed pp. 38–39), data-centred design at PDF p. 67 (printed p. 63))
  • Hierarchy mapping:
    • 大分類3 技術要素 › 中分類9 データベース › 2. データベース設計
      • (1) データ分析 — term example: データ重複の排除
      • (2) データベースの設計 › ③ データベースの論理設計 — 主キー・外部キー, 一貫性制約 (一意性制約, 参照制約, 検査制約)
      • (3) データの正規化 — 第1正規形, 第2正規形, 第3正規形など; term examples 完全関数従属, 部分関数従属, 推移関数従属
      • (4) データベースのパフォーマンス設計 — 非正規化
    • 大分類4 開発技術 › 中分類12 システム開発技術 › 2. 設計 › （9）ソフトウェア設計手法 › ② データ中心設計 — data-centric design terms: 正規化, 一事実一箇所
  • BCNF note: the syllabus says “第1正規形，第2正規形，第3正規形など” (1NF, 2NF, 3NF, etc.). It does not name BCNF explicitly. BCNF is covered here only as supplementary depth under that “etc.”.
  • Out of scope here: SQL syntax and queries (AP14). Schemas and FDs are written in relational notation only.

2. Terminology table (KO / JA / EN)

Korean Japanese English
후보키 候補キー candidate key
주키(기본키) 主キー primary key
외래키 外部キー foreign key
슈퍼키 スーパーキー superkey
주요 속성(키 속성) / 비주요 속성 主属性（キー属性）／非キー属性 prime / non-prime attribute
함수 종속 関数従属性 functional dependency (FD)
결정자 / 종속자 決定項 / 従属項 determinant / dependent
속성 폐포 属性閉包 attribute closure
완전 함수 종속 完全関数従属 full functional dependency
부분 함수 종속 部分関数従属 partial functional dependency
이행 함수 종속 推移関数従属 transitive functional dependency
갱신 이상 / 삽입 이상 / 삭제 이상 更新時異状 / 挿入時異状 / 削除時異状 update / insertion / deletion anomaly
정규형 正規形 normal form
무손실 분해 無損失分解 lossless(-join) decomposition
종속성 보존 従属性保存 dependency preservation
참조 무결성 参照整合性（参照制約） referential integrity
비정규화 非正規化 denormalization

3. Main example and assumptions

ENROLLMENT_RAW(StudentID, CourseID, StudentName, CourseTitle,
               InstructorID, InstructorName, Grade)

Functional dependencies F:

  1. StudentID -> StudentName
  2. CourseID -> CourseTitle, InstructorID
  3. InstructorID -> InstructorName
  4. (StudentID, CourseID) -> Grade

Business assumptions: one ID identifies one student; one course has one title and one assigned instructor; one instructor ID has one name; one student has at most one grade per course. All values are atomic (the starting relation is already in 1NF). No other nontrivial FDs are assumed.

Sample rows (for illustrating anomalies):

StudentID CourseID StudentName CourseTitle InstructorID InstructorName Grade
S01 C10 Kim Database I7 Tanaka A
S02 C10 Lee Database I7 Tanaka B
S01 C20 Kim Networks I8 Sato B

4. Keys and attribute closure

Definitions

  • Superkey: an attribute set whose values determine every attribute of the relation.
  • Candidate key: a minimal superkey — removing any attribute makes it no longer a superkey.
  • Primary key: the one candidate key selected to identify tuples (no NULLs, unique).
  • Foreign key: an attribute set whose values must match values of a candidate key / unique key in the referenced relation (typically its primary key, but not necessarily). It enforces referential integrity.

Closure algorithm

To compute X⁺: start with X; repeatedly, for each FD Y -> Z in F with Y ⊆ current set, add Z; stop when a full pass adds nothing new.

{StudentID, CourseID}+:

Pass FD applied Set after step
start — {StudentID, CourseID}
1 StudentID -> StudentName + StudentName
2 CourseID -> CourseTitle, InstructorID + CourseTitle, InstructorID
3 InstructorID -> InstructorName + InstructorName
4 (StudentID, CourseID) -> Grade + Grade
next pass nothing new all 7 attributes
  • {CourseID}+ = {CourseID, CourseTitle, InstructorID, InstructorName} only.
  • {StudentID}+ = {StudentID, StudentName} only.

Why (StudentID, CourseID) is the only candidate key

  1. Neither StudentID nor CourseID appears on the right-hand side of any FD in F, so no other attributes can derive them. Every key must contain both.
  2. {StudentID, CourseID}+ is all seven attributes → it is a superkey.
  3. Removing either attribute fails ({StudentID}+ and {CourseID}+ above are incomplete) → it is minimal.
  4. Any other superkey contains this pair plus extra attributes, so it is not minimal.

Therefore (StudentID, CourseID) is the only candidate key under F, and it is selected as the primary key. Prime attributes: StudentID, CourseID. Non-prime: the other five.

5. Classifying functional dependencies

Relative to the composite candidate key K = (StudentID, CourseID):

Type Dependency Reason
Full FD K -> Grade Neither StudentID alone nor CourseID alone determines Grade.
Partial FD StudentID -> StudentName A non-prime attribute depends on a proper part of K.
Partial FD CourseID -> CourseTitle, InstructorID Same: a proper part of K is the determinant.
Transitive FD CourseID -> InstructorID -> InstructorName InstructorName depends on CourseID via the non-key attribute InstructorID.

Precision notes:

  • CourseID -> InstructorName is inferred (by transitivity), not one of the given FDs. In the raw relation, InstructorName therefore depends on part of K partially and transitively. Do not call every inferred dependency an immediate (given) FD.
  • In the 2NF relation COURSE_2NF (section 7), CourseID is the key, so CourseID -> InstructorID -> InstructorName is a transitive dependency of a non-prime attribute on the key through a non-key attribute.
  • Determinant = left side; dependent = right side. “X -> Y” reads “X determines Y” / “Y is functionally dependent on X”.

6. Update anomalies

All three come from redundancy (the same fact stored in many rows) and mixed facts (student, course, instructor and enrollment facts in one relation).

  • Update anomaly: Tanaka (I7) is stored in two rows. Changing the name in only one row leaves the data inconsistent.
  • Insertion anomaly: a new course C30 taught by I9 cannot be stored until someone enrolls, because the primary key (StudentID, CourseID) must be complete (no NULL in StudentID).
  • Deletion anomaly: if S01 drops C20 and that is the last enrollment for C20, deleting the row also erases the facts “C20 = Networks, taught by I8 Sato”.

7. 1NF → 2NF → 3NF

  • 1NF: every attribute value is atomic (no repeating groups). ENROLLMENT_RAW already is 1NF — and the anomalies above still exist. 1NF alone does not remove partial or transitive dependencies.
  • 2NF: 1NF, and every non-prime attribute is fully dependent on every candidate key (no partial dependencies).
  • 3NF: 2NF, and no non-prime attribute is transitively dependent on a candidate key. Equivalent test: for every nontrivial X -> A, X is a superkey OR A is a prime attribute.
  • BCNF: for every nontrivial X -> A, X is a superkey (the “A is prime” escape is removed).

2NF decomposition (remove partial FDs)

STUDENT(StudentID PK, StudentName)
COURSE_2NF(CourseID PK, CourseTitle, InstructorID, InstructorName)
ENROLLMENT(StudentID PK/FK, CourseID PK/FK, Grade)   -- composite PK (StudentID, CourseID)

Partial dependencies are gone from ENROLLMENT. But COURSE_2NF still has the transitive dependency CourseID -> InstructorID -> InstructorName (instructor names still repeat per course).

3NF / final decomposition (remove transitive FD)

STUDENT(StudentID PK, StudentName)
INSTRUCTOR(InstructorID PK, InstructorName)
COURSE(CourseID PK, CourseTitle, InstructorID FK -> INSTRUCTOR.InstructorID)
ENROLLMENT(StudentID FK -> STUDENT.StudentID,
           CourseID  FK -> COURSE.CourseID,
           Grade,
           PK(StudentID, CourseID))

FK direction: the “many” side references the “one” side — ENROLLMENT → STUDENT, ENROLLMENT → COURSE, COURSE → INSTRUCTOR.

Under the FDs projected onto each table, every determinant is a superkey (StudentID in STUDENT, InstructorID in INSTRUCTOR, CourseID in COURSE, (StudentID, CourseID) in ENROLLMENT). So each final table is in 3NF and BCNF.

The final schema stores each fact in one place (“一事実一箇所”): change Tanaka’s name once in INSTRUCTOR; insert C30 into COURSE without any enrollment; delete an enrollment without losing course data.

Performance note: normalization does not always make queries faster — reads may need more joins. Denormalization (非正規化) is a deliberate, measured performance trade-off made after integrity requirements are understood, not a default.

8. Lossless decomposition and dependency preservation

Criterion: decomposing R into R1 and R2 is lossless if (R1 ∩ R2) -> R1 or (R1 ∩ R2) -> R2 follows from F (the shared attributes are a key of at least one side).

Staged binary decompositions:

Step Split R1 ∩ R2 Check Result
1 RAW → STUDENT + REST1(StudentID, CourseID, CourseTitle, InstructorID, InstructorName, Grade) StudentID StudentID -> {StudentID, StudentName} = all of STUDENT lossless
2 REST1 → COURSE_2NF + ENROLLMENT CourseID CourseID -> {CourseID, CourseTitle, InstructorID, InstructorName} = all of COURSE_2NF lossless
3 COURSE_2NF → COURSE + INSTRUCTOR InstructorID InstructorID -> {InstructorID, InstructorName} = all of INSTRUCTOR lossless

Each step is lossless, so the staged final decomposition is lossless under F. With valid key and foreign-key data, the natural join ENROLLMENT ⋈ STUDENT ⋈ COURSE ⋈ INSTRUCTOR reconstructs exactly the original tuples — no tuples lost and no spurious tuples added.

Dependency preservation — every FD in F can be checked inside one final table:

FD Checked in
StudentID -> StudentName STUDENT
CourseID -> CourseTitle, InstructorID COURSE
InstructorID -> InstructorName INSTRUCTOR
(StudentID, CourseID) -> Grade ENROLLMENT

9. BCNF boundary (supplementary depth)

(Supplementary depth under the syllabus’s “第3正規形など”; BCNF is not named in the syllabus.)

TEACH(Student, Subject, Instructor)
FDs (only): (Student, Subject) -> Instructor
            Instructor -> Subject
  • Candidate keys: (Student, Subject) and (Student, Instructor) — {Student, Instructor}+ adds Subject via Instructor -> Subject. Every attribute is prime.
  • Instructor -> Subject: Subject is prime → 3NF is satisfied. Instructor is not a superkey → BCNF is violated.
  • BCNF decomposition: INSTRUCTOR_SUBJECT(Instructor, Subject) and STUDENT_INSTRUCTOR(Student, Instructor). Lossless: the intersection Instructor determines all of INSTRUCTOR_SUBJECT.
  • Trade-off: (Student, Subject) -> Instructor is no longer contained in a single relation, so it is not preserved; enforcing it may need an additional constraint or check. Not every BCNF decomposition preserves all dependencies; 3NF decomposition can always be made both lossless and dependency-preserving.

10. Quick sheet

  • Candidate key = minimal superkey; primary key = the chosen candidate key; foreign key → candidate/unique key of another relation (referential integrity).
  • X⁺: apply F repeatedly until nothing new. X⁺ = all attributes → X is a superkey.
  • Attribute never on any RHS → it is in every key.
  • Full: depends on the whole key. Partial: on part of a composite key. Transitive: key → non-key → non-key.
  • 1NF atomic → 2NF no partial → 3NF no transitive (X superkey or A prime) → BCNF (X superkey).
  • Lossless binary split: (R1 ∩ R2) -> R1 or -> R2.
  • Dependency preserving: each FD checkable within one table.
  • Main example final: STUDENT, INSTRUCTOR, COURSE(→INSTRUCTOR), ENROLLMENT(→STUDENT, →COURSE).

11. Common traps

  • “1NF means anomalies are gone” — false; ENROLLMENT_RAW is 1NF and has all three anomalies.
  • Calling a non-minimal superkey (e.g. StudentID, CourseID, Grade) a candidate key.
  • Treating partial FDs as possible with a single-attribute key — partial FDs require a composite key.
  • Calling InstructorID -> InstructorName “partial” — InstructorID is not part of K.
  • “A foreign key must reference a primary key” — it references a candidate/unique key (usually the PK).
  • Splitting on attributes that do not determine either side (empty intersection, or a non-unique name) → spurious tuples.
  • “BCNF decomposition always preserves dependencies” — false (TEACH).
  • “Normalization always improves performance” — false; denormalization is a measured trade-off.

12. Practice questions (5, original)

Original questions written for this note. None is an IPA past question.

Q1

For ENROLLMENT_RAW under F, which statement is correct?

  • ア {CourseID}+ contains all seven attributes, so CourseID alone is a candidate key.
  • イ {StudentID, CourseID}+ contains all seven attributes, and neither {StudentID}+ nor {CourseID}+ does, so (StudentID, CourseID) is a candidate key.
  • ウ (StudentID, CourseID, Grade) is a candidate key because its closure contains all seven attributes.
  • エ (StudentID, InstructorID) is also a candidate key because InstructorID determines InstructorName.

Answer: イ

  • ア Wrong. {CourseID}+ = {CourseID, CourseTitle, InstructorID, InstructorName}; StudentID, StudentName and Grade are missing.
  • イ Correct. The closure is complete, and removing either attribute gives an incomplete closure, so the pair is a minimal superkey.
  • ウ Wrong. It is a superkey but not minimal; Grade can be removed.
  • エ Wrong. {StudentID, InstructorID}+ = {StudentID, StudentName, InstructorID, InstructorName}; CourseID cannot be derived because it is on no RHS.

Q2

Relative to K = (StudentID, CourseID), which classification is correct?

  • ア K -> Grade is a partial FD because StudentID is part of K.
  • イ StudentID -> StudentName is a transitive FD because StudentName is a non-key attribute.
  • ウ K -> Grade is full; StudentID -> StudentName is partial; InstructorName depends on CourseID transitively through the non-key InstructorID.
  • エ InstructorID -> InstructorName is a partial FD on K because InstructorID is part of K.

Answer: ウ

  • ア Wrong. Grade needs the whole K; neither part alone determines it, so it is full.
  • イ Wrong. The determinant StudentID is a proper part of K with no intermediate non-key attribute, so it is partial, not transitive.
  • ウ Correct. All three labels match the definitions (CourseID -> InstructorID -> InstructorName is the transitive chain).
  • エ Wrong. InstructorID is a non-key attribute, not part of K; this FD forms the second link of the transitive chain.

Q3

Which is the correct 3NF final decomposition, including PK/FK direction?

  • ア STUDENT(StudentID PK, StudentName), COURSE(CourseID PK, CourseTitle, InstructorID, InstructorName), ENROLLMENT(StudentID FK, CourseID FK, Grade, PK(StudentID, CourseID))
  • イ STUDENT(StudentID PK, StudentName), INSTRUCTOR(InstructorID PK, InstructorName, CourseID FK -> COURSE), COURSE(CourseID PK, CourseTitle), ENROLLMENT(StudentID FK, CourseID FK, Grade, PK(StudentID, CourseID))
  • ウ STUDENT(StudentID PK, StudentName), INSTRUCTOR(InstructorID PK, InstructorName), COURSE(CourseID PK, CourseTitle, InstructorID FK -> INSTRUCTOR), ENROLLMENT(StudentID PK, CourseID FK -> COURSE, Grade)
  • エ STUDENT(StudentID PK, StudentName), INSTRUCTOR(InstructorID PK, InstructorName), COURSE(CourseID PK, CourseTitle, InstructorID FK -> INSTRUCTOR), ENROLLMENT(StudentID FK -> STUDENT, CourseID FK -> COURSE, Grade, PK(StudentID, CourseID))

Answer: エ

  • ア Wrong. This is only 2NF; COURSE still has CourseID -> InstructorID -> InstructorName.
  • イ Wrong. FK direction is reversed: InstructorID -> CourseID is not in F (one instructor may teach several courses), and CourseID -> InstructorID is no longer checkable in one table.
  • ウ Wrong. StudentID alone is not a key of ENROLLMENT (a student takes many courses), and the FK to STUDENT is missing.
  • エ Correct. Every FD is in one table, every determinant is a key, and FKs point from the many side to the one side.

Q4

Which is a valid proof that a decomposition step is lossless?

  • ア Splitting COURSE_2NF into COURSE(CourseID, CourseTitle, InstructorID) and INSTRUCTOR(InstructorID, InstructorName) is lossless because the intersection InstructorID determines all attributes of INSTRUCTOR.
  • イ Splitting ENROLLMENT_RAW into STUDENT and REST1 is lossless because both relations have the same number of tuples.
  • ウ Splitting ENROLLMENT_RAW into R1(StudentID, StudentName, Grade) and R2(CourseID, CourseTitle, InstructorID, InstructorName) is lossless because each part has its own determinant.
  • エ Splitting COURSE_2NF into (CourseID, CourseTitle, InstructorName) and (InstructorID, InstructorName) is lossless because the intersection is InstructorName.

Answer: ア

  • ア Correct. (R1 ∩ R2) = InstructorID, and InstructorID -> R2 follows from F.
  • イ Wrong. Tuple counts are not the criterion (and STUDENT usually has fewer tuples). The correct reason is StudentID -> STUDENT.
  • ウ Wrong. The intersection is empty, so the join is a Cartesian product with spurious tuples; the student–course link is lost.
  • エ Wrong. InstructorName -> InstructorID is not in F (names may repeat), so the intersection determines neither side.

Q5

For TEACH(Student, Subject, Instructor) with only (Student, Subject) -> Instructor and Instructor -> Subject, which is correct?

  • ア TEACH violates 2NF because Instructor -> Subject is a partial dependency.
  • イ TEACH is in BCNF because every attribute is prime.
  • ウ TEACH is in 3NF but not BCNF; decomposing into INSTRUCTOR_SUBJECT(Instructor, Subject) and STUDENT_INSTRUCTOR(Student, Instructor) is lossless, but (Student, Subject) -> Instructor is not preserved within one relation.
  • エ Decomposing into (Student, Subject) and (Student, Instructor) is lossless and preserves all dependencies.

Answer: ウ

  • ア Wrong. 2NF and 3NF restrict non-prime attributes; Subject is prime, so TEACH is in 2NF and 3NF.
  • イ Wrong. BCNF requires every nontrivial determinant to be a superkey; Instructor is not.
  • ウ Correct. 3NF holds because Subject is prime; BCNF fails; the split is lossless via Instructor, but the original FD may need an extra constraint/check.
  • エ Wrong. The intersection Student determines neither side, so the split is lossy (spurious tuples).

Answer key: イ, ウ, エ, ア, ウ (1-based: 2, 3, 4, 1, 3)

13. Self-check and 1/3/7-day review

Self-check:

  • I can compute {StudentID, CourseID}+, {CourseID}+ and {StudentID}+ from F without notes.
  • I can explain why the pair is the only candidate key (RHS argument + minimality).
  • I can label full / partial / transitive FDs and explain the inferred CourseID -> InstructorName.
  • I can give one update, insertion and deletion anomaly from the sample rows.
  • I can write the 2NF and 3NF schemas with PK/FK direction.
  • I can state the 3NF and BCNF conditions and the lossless-split criterion.
  • I can explain why TEACH is 3NF but not BCNF and what the BCNF split loses.

Review plan:

  • Day 1: redo sections 4–5 on paper; retake Q1–Q2.
  • Day 3: rewrite the 2NF/3NF schemas and the three lossless steps from memory; retake Q3–Q4.
  • Day 7: explain the TEACH trade-off aloud; retake all five questions and review any wrong option explanations.

14. Revision history

  • 2026-10-28: Corrected the official hierarchy for data-centred design to 大分類4：開発技術／中分類12：システム開発技術／2. 設計／（9）ソフトウェア設計手法／② データ中心設計, corrected the source pages to PDF pp. 42–43 (printed pp. 38–39) for database design and normalization and PDF p. 67 (printed p. 63) for data-centred design, and added this item to the syllabus coverage in the series metadata. The explanations, practice questions and answers are unchanged.

Back to the blog