13_ER_Modeling

Proses Desain Basis Data

Desain basis data terdiri atas beberapa fase:

Fase awal: mengarakterisasi secara penuh kebutuhan data dari calon pengguna basis data.
Fase kedua — memilih data model: menerapkan konsep data model yang dipilih, menerjemahkan kebutuhan menjadi skema konseptual basis data. Skema konseptual yang matang menunjukkan kebutuhan fungsional enterprise — jenis operasi (transaksi) apa saja yang akan dilakukan terhadap data.
Fase akhir — memindahkan data model abstrak ke implementasi:
- Logical design: menentukan skema basis data — mencari kumpulan skema relasi yang “baik”. Ini melibatkan keputusan bisnis (atribut apa yang perlu direkam) dan keputusan ilmu komputer (skema relasi apa yang dibutuhkan, dan bagaimana atribut didistribusikan ke skema-skema tersebut).
- Physical design: menentukan tata letak fisik basis data.

Menghindari Desain Buruk

Dalam mendesain skema basis data, dua kesalahan utama yang harus dihindari:

Redundancy: desain buruk dapat menghasilkan informasi yang berulang. Representasi informasi yang redundan dapat menyebabkan inkonsistensi data antar-salinan informasi.
Incompleteness: desain buruk dapat membuat aspek tertentu dari enterprise sulit atau tidak mungkin dimodelkan.

Menghindari desain buruk saja tidak cukup — bisa jadi ada banyak desain “baik” yang harus dipilih salah satunya.

Dua Pendekatan Desain

Entity-Relationship (ER) Model (materi utama topik ini): memodelkan enterprise sebagai kumpulan entity dan relationship, direpresentasikan secara diagram lewat ER diagram.
Normalization theory: memformalkan desain seperti apa yang buruk, dan menyediakan cara mengetesnya (dibahas di materi lain).

Model Entity-Relationship (ER)

ER data model dikembangkan untuk memudahkan desain basis data dengan memungkinkan spesifikasi enterprise schema yang merepresentasikan struktur logis keseluruhan basis data. ER model memakai tiga konsep dasar: entity set, relationship set, dan attribute, plus representasi diagram (ER diagram) untuk mengekspresikan struktur logis basis data secara grafis.

Entity Set

Entity: objek yang eksis dan dapat dibedakan dari objek lain (mis. orang, perusahaan, event, tumbuhan tertentu).
Entity set: himpunan entity dengan tipe sama yang berbagi properti yang sama (mis. himpunan semua orang, perusahaan, pohon, hari libur).
Entity direpresentasikan oleh sekumpulan atribut — properti deskriptif yang dimiliki semua anggota entity set. Contoh: instructor = (ID, name, salary), course = (course_id, title, credits).
Subset atribut membentuk primary key dari entity set — atribut yang secara unik mengidentifikasi tiap anggota himpunan.

Representasi di ER diagram: rectangle merepresentasikan entity set, atribut dituliskan di dalam rectangle, dan garis bawah (underline) menandai atribut primary key.

Relationship Set

Relationship: asosiasi antara beberapa entity. Contoh: 44553 (Peltier) —advisor— 22222 (Einstein) (student entity — relationship set — instructor entity).
Relationship set adalah relasi matematis di antara n ≥ 2 entity, masing-masing diambil dari entity set: {(e1, e2, …, en) | e1 ∈ E1, e2 ∈ E2, …, en ∈ En}. Contoh: (44553, 22222) ∈ advisor.
Representasi: diamond merepresentasikan relationship set; garis menghubungkan entity yang berelasi.
Relationship set juga bisa punya atribut sendiri — mis. relationship set advisor antara instructor dan student bisa punya atribut date (tanggal mulai bimbingan).

Roles

Entity set dari sebuah relationship tidak harus berbeda — tiap kemunculan entity set memainkan sebuah role dalam relationship tersebut. Contoh: relationship prereq pada entity set course memakai role course_id dan prereq_id untuk membedakan dua kemunculan course yang sama (mata kuliah dan prasyaratnya).

Degree of a Relationship Set

Binary relationship: melibatkan dua entity set (derajat dua) — mayoritas relationship set pada sistem basis data adalah binary.
Non-binary relationship: relationship antar lebih dari dua entity set jarang terjadi, tapi kadang lebih nyaman digunakan. Contoh: proj_guide adalah relationship ternary antara instructor, student, dan project (mahasiswa mengerjakan project riset di bawah bimbingan seorang instructor).

Atribut Kompleks

Tipe-tipe atribut:

Simple vs composite attribute: atribut composite dapat dipecah menjadi sub-bagian (atribut lain). Contoh: atribut name terdiri dari first_name, middle_initial, last_name; atribut address terdiri dari street (yang sendiri composite: street_number, street_name, apartment_number), city, state, postal_code.
Single-valued vs multivalued attribute: contoh atribut multivalued adalah phone_number (dinotasikan dengan { phone_number }).
Derived attribute: dapat dihitung dari atribut lain. Contoh: age dapat diturunkan dari date_of_birth (dinotasikan age()).
Domain: himpunan nilai yang diizinkan untuk tiap atribut.

Mapping Cardinality Constraints

Mapping cardinality mengekspresikan jumlah entity yang dapat diasosiasikan dengan entity lain lewat suatu relationship set — paling berguna untuk mendeskripsikan binary relationship set. Untuk binary relationship set, mapping cardinality harus salah satu dari:

Tipe	Deskripsi
One to one	Satu entity di A berpasangan dengan paling banyak satu entity di B, dan sebaliknya.
One to many	Satu entity di A dapat berpasangan dengan banyak entity di B, tapi satu entity di B paling banyak berpasangan dengan satu entity di A.
Many to one	Kebalikan one-to-many.
Many to many	Satu entity di A dapat berpasangan dengan banyak entity di B, dan sebaliknya.

Catatan: pada semua tipe di atas, beberapa elemen di A dan B mungkin tidak berpasangan dengan elemen manapun di himpunan lainnya.

Representasi di ER diagram: garis berarah (→) menandakan “one”, garis tak-berarah (—) menandakan “many”, digambar antara relationship set dan entity set. Contoh relationship advisor antara instructor dan student:

One-to-one: student berasosiasi dengan paling banyak satu instructor via advisor.
One-to-many: satu instructor berasosiasi dengan beberapa (termasuk 0) student via advisor, tapi satu student paling banyak satu instructor.
Many-to-one: kebalikannya — satu instructor paling banyak satu student, satu student bisa beberapa instructor.
Many-to-many: instructor dan student sama-sama bisa berasosiasi dengan beberapa pasangan (termasuk 0).

Cardinality Constraint pada Relationship Ternary+

Untuk relationship berderajat ternary (atau lebih), hanya diperbolehkan paling banyak satu panah keluar dari relationship untuk menandai cardinality constraint (mis. panah dari proj_guide ke instructor berarti tiap student punya paling banyak satu guide untuk suatu project). Jika ada lebih dari satu panah, maknanya menjadi ambigu (dua kemungkinan interpretasi berbeda dipakai pada formalisme berbeda) — sehingga lebih dari satu panah dilarang untuk menghindari kebingungan.

Total dan Partial Participation

Total participation (ditandai garis ganda pada ER diagram): setiap entity di entity set berpartisipasi dalam minimal satu relationship di relationship set. Contoh: partisipasi student pada relasi advisor bersifat total — setiap student harus punya instructor pembimbing.
Partial participation: sebagian entity mungkin tidak berpartisipasi dalam relationship manapun. Contoh: partisipasi instructor pada advisor bersifat partial.

Primary Key

Primary key menyediakan cara menentukan bagaimana entity dan relationship dibedakan satu sama lain — berlaku untuk entity set, relationship set, dan weak entity set.

Primary key untuk entity set: setiap entity secara definisi berbeda; dari sudut pandang basis data, perbedaan tersebut harus diekspresikan lewat atributnya — tidak boleh ada dua entity dalam satu entity set yang punya nilai sama persis untuk seluruh atribut. Key adalah sekumpulan atribut yang cukup untuk membedakan entity satu sama lain.
Primary key untuk relationship set: misalkan relationship set R melibatkan entity set E1, E2, …, En — primary key R terdiri dari union primary key entity set E1…En. Jika R punya atribut sendiri a1, a2, …, am, atribut tersebut juga masuk primary key R. Contoh: primary key relationship advisor terdiri dari instructor.ID dan student.ID.
Pemilihan primary key relationship set bergantung pada mapping cardinality:

Mapping cardinality	Pilihan primary key relationship
Many-to-many	Union seluruh primary key entity yang terlibat (minimal superkey)
One-to-many	Primary key sisi “many” saja sudah minimal superkey
Many-to-one	Primary key sisi “many” saja sudah minimal superkey
One-to-one	Primary key salah satu entity set (mana saja) sudah minimal superkey

Weak Entity Set

Masalah motivasi: entity section (kelas paralel suatu mata kuliah) diidentifikasi secara unik oleh course_id, semester, year, dan sec_id. Relationship sec_course antara section dan course mengandung informasi redundan karena section sudah punya atribut course_id yang mengidentifikasi mata kuliah terkait.

Opsi menghilangkan relationship sec_course membuat relasi section–course menjadi implisit lewat atribut — tidak diinginkan.
Opsi lain: tidak menyimpan atribut course_id di entity section, hanya menyimpan sec_id, year, semester. Namun section jadi tidak punya atribut cukup untuk diidentifikasi secara unik.
Solusinya: memperlakukan sec_course sebagai relationship khusus yang menyediakan informasi tambahan (course_id) yang diperlukan untuk mengidentifikasi section secara unik.

Definisi: weak entity set adalah entity set yang eksistensinya bergantung pada entity lain, disebut identifying entity-nya. Alih-alih memiliki primary key sendiri, weak entity memakai identifying entity plus atribut tambahan yang disebut discriminator untuk mengidentifikasi weak entity secara unik.

Entity set yang bukan weak entity set disebut strong entity set.
Weak entity dikatakan existence dependent terhadap identifying entity set-nya; identifying entity set memiliki (own) weak entity set yang diidentifikasinya.
Relationship yang mengasosiasikan weak entity set dengan identifying entity set disebut identifying relationship.
Skema relasional yang akhirnya dibuat dari entity section tetap memiliki atribut course_id (alasannya dijelaskan pada materi reduksi ER-ke-relasional, lihat Relational Data Model), meski atribut tersebut sudah “dilepas” dari entity set section pada level ER.

Representasi di ER diagram:

Weak entity set digambarkan dengan double rectangle.
Discriminator weak entity set diberi garis bawah putus-putus (dashed underline).
Relationship set yang menghubungkan weak entity ke identifying strong entity set digambarkan dengan double diamond.
Primary key untuk section = (course_id, sec_id, semester, year).

E-R Diagram Lengkap: Contoh Universitas

Diagram berikut menggabungkan seluruh konsep di atas (entity set, relationship set, mapping cardinality, total/partial participation, weak entity, composite & multivalued attribute) dalam satu skema enterprise universitas: department, instructor, student, course, section (weak entity dari course), time_slot, classroom, beserta relationship inst_dept, stud_dept, course_dept, advisor, teaches, takes (dengan atribut grade), sec_course (identifying relationship, double diamond), sec_time_slot, sec_class, dan prereq.

Extended E-R Features

Specialization

Specialization adalah proses desain top-down: kita menetapkan subgrouping di dalam suatu entity set yang berbeda dari entity lain di himpunan tersebut. Subgrouping ini menjadi entity set lower-level yang punya atribut atau berpartisipasi dalam relationship yang tidak berlaku untuk entity set higher-level.

Digambarkan lewat komponen triangle berlabel ISA (mis. customer “is a” person).
Attribute inheritance: entity set lower-level mewarisi seluruh atribut dan partisipasi relationship dari entity set higher-level yang dihubungkan dengannya.

Generalization

Generalization adalah proses desain bottom-up — menggabungkan sejumlah entity set yang berbagi fitur sama ke dalam satu entity set higher-level. Specialization dan generalization adalah inversi satu sama lain dan direpresentasikan dengan cara sama di ER diagram (istilahnya dipakai bergantian). Relationship ISA juga disebut relationship superclass–subclass.

Satu entity set bisa punya beberapa specialization berbeda berdasarkan fitur berbeda sekaligus. Contoh: employee bisa dispesialisasi jadi permanent-employee vs temporary-employee sekaligus jadi officer vs teller vs secretary — tiap employee tertentu adalah anggota salah satu dari kelompok pertama dan salah satu dari kelompok kedua.

graph TD
  Person["Person<br/>name, street, city"]
  Employee["Employee<br/>salary"]
  Customer["Customer<br/>credit-rating"]
  Officer["Officer<br/>office-number"]
  Teller["Teller<br/>station-number, hours-worked"]
  Secretary["Secretary<br/>hours-worked"]
  Person -->|ISA| Employee
  Person -->|ISA| Customer
  Employee -->|ISA| Officer
  Employee -->|ISA| Teller
  Employee -->|ISA| Secretary

Design Constraints pada Specialization/Generalization

Constraint keanggotaan (entity mana yang boleh jadi anggota suatu lower-level entity set):

Condition-defined: keanggotaan ditentukan lewat kondisi eksplisit pada suatu atribut (mis. type = "employee").
User-defined: tidak ada kondisi eksplisit — keanggotaan ditentukan manual oleh user/aplikasi.

Constraint tumpang-tindih (apakah entity boleh jadi anggota lebih dari satu lower-level entity set dalam satu generalization):

Disjoint: satu entity hanya boleh jadi anggota satu lower-level entity set. Ditandai tulisan disjoint di sebelah triangle ISA.
Overlapping: satu entity boleh jadi anggota lebih dari satu lower-level entity set (tidak ada tulisan disjoint).

Completeness constraint (apakah entity di higher-level entity set harus jadi anggota salah satu lower-level entity set):

Total: entity harus menjadi anggota salah satu lower-level entity set — ditandai garis ganda dari higher-level entity ke triangle ISA.
Partial: entity tidak wajib menjadi anggota lower-level entity set manapun — ditandai garis tunggal.

Aggregation

Masalah motivasi: pada relationship ternary proj_guide (antara instructor, student, project), misalkan kita ingin mencatat evaluasi seorang student oleh guide-nya pada suatu project lewat relationship baru eval_for (menghubungkan proj_guide ke entity evaluation). Relationship set eval_for dan proj_guide merepresentasikan informasi yang tumpang tindih: setiap relationship eval_for berkorespondensi dengan sebuah relationship proj_guide, tapi tidak semua proj_guide punya eval_for — sehingga proj_guide tidak bisa dibuang begitu saja.

Aggregation menghilangkan redundansi ini dengan memperlakukan sebuah relationship sebagai entity abstrak — memungkinkan relationship antar-relationship (abstraksi suatu relationship menjadi entity baru).

graph TD
  subgraph proj_guide_group["proj_guide (diperlakukan sebagai satu entity abstrak)"]
    instructor[instructor]
    project[project]
    student[student]
  end
  proj_guide_group -->|eval_for| evaluation[evaluation]

Tanpa memperkenalkan redundansi, diagram ini merepresentasikan: (1) seorang student dibimbing oleh instructor tertentu pada project tertentu, dan (2) kombinasi (student, instructor, project) tersebut mungkin punya evaluasi terkait.

Isu Desain Entity-Relationship

Kesalahan Umum pada ER Diagram

(a) Penggunaan atribut yang salah — redundant attribute: misalkan entity set student (atribut ID, name, tot_cred, dept_name) dan department (atribut dept_name, building, budget), dengan relationship set stud_dept yang memodelkan fakta tiap student punya department terkait. Atribut dept_name pada student meniru informasi yang sudah ada di relationship — ini redundan dan sebaiknya dihapus dari entity student (meski saat direduksi ke tabel relasional, atribut ini kadang muncul kembali — lihat Relational Data Model).

(b) Penggunaan atribut relationship yang keliru: menaruh atribut assignment dan marks langsung pada relationship stud_section (antara student dan section) adalah keliru karena assignment sebenarnya adalah entity tersendiri (satu section bisa punya banyak assignment, tiap assignment punya banyak nilai per student). Alternatif yang benar:

Jadikan assignment entity set sendiri, dengan relationship sec_assign (section–assignment) dan marks_in (student–assignment, beratribut marks); atau
Jika ingin tetap satu relationship stud_section, jadikan atributnya berupa set {assignment_marks: {assignment, marks}} (multivalued composite attribute) alih-alih atribut tunggal.

Entities vs. Attributes

Trade-off antara memodelkan sesuatu sebagai atribut vs sebagai entity set tersendiri. Contoh: phone_number bisa jadi atribut biasa pada instructor, atau dijadikan entity set phone tersendiri (dengan relationship inst_phone) jika ingin menyimpan informasi tambahan tentang nomor telepon (mis. location) atau mendukung banyak nomor telepon per instructor secara lebih fleksibel.

Entities vs. Relationship Sets

Panduan umum: gunakan relationship set untuk mendeskripsikan sebuah aksi yang terjadi antar-entity. Contoh: alih-alih relationship langsung section–student, bisa dimodelkan lewat entity registration yang dihubungkan oleh relationship section_reg dan student_reg — jika “pendaftaran” itu sendiri punya makna sebagai objek independen.

Penempatan atribut relationship: misalnya atribut date pada relationship advisor — bisa juga dipertimbangkan sebagai atribut pada student alih-alih pada relationship, tergantung makna semantik yang diinginkan.

Binary vs. Non-Binary Relationships

Walaupun secara teknis setiap relationship non-binary (ternary ke atas) bisa digantikan oleh sejumlah relationship binary, relationship ternary kadang lebih jelas menunjukkan bahwa beberapa entity berpartisipasi dalam satu relationship yang sama.

Beberapa relationship yang tampak non-binary sebenarnya lebih baik direpresentasikan sebagai relationship binary. Contoh: relationship ternary parents (menghubungkan anak ke ayah dan ibunya) lebih baik digantikan dua relationship binary father dan mother — ini memungkinkan informasi parsial (mis. hanya ibu yang diketahui).
Namun ada relationship yang memang secara alami non-binary, contoh: proj_guide.

Konversi Relationship Non-Binary ke Bentuk Binary

Secara umum, relationship non-binary apapun dapat direpresentasikan memakai relationship binary dengan membuat sebuah entity set artifisial E:

Ganti relationship R (antara entity set A, B, C) dengan entity set baru E, plus tiga relationship set: R_A (E–A), R_B (E–B), R_C (E–C).
Buat atribut pengidentifikasi untuk E, dan tambahkan atribut R (jika ada) ke E.
Untuk tiap relationship (aᵢ, bᵢ, cᵢ) di R, buat entity baru eᵢ di E, lalu tambahkan (eᵢ, aᵢ) ke R_A, (eᵢ, bᵢ) ke R_B, dan (eᵢ, cᵢ) ke R_C.

Konstraint juga perlu diterjemahkan — tidak semua constraint bisa diterjemahkan sepenuhnya (bisa muncul instance pada skema hasil translasi yang tidak berkorespondensi dengan instance R manapun). Untuk menghindari perlunya atribut pengidentifikasi eksplisit pada E, E bisa dijadikan weak entity set yang diidentifikasi oleh ketiga relationship set tersebut.

Ringkasan Keputusan Desain ER

Penggunaan atribut vs entity set untuk merepresentasikan suatu objek.
Apakah suatu konsep dunia nyata lebih tepat diekspresikan sebagai entity set atau relationship set.
Penggunaan relationship ternary vs sepasang relationship binary.
Penggunaan strong vs weak entity set.
Penggunaan specialization/generalization — berkontribusi pada modularitas desain.
Penggunaan aggregation — memungkinkan entity set agregat diperlakukan sebagai satu unit tanpa perlu memedulikan detail struktur internalnya.

Sumber

Silberschatz, Korth, Sudarshan: Database System Concepts, 7th ed., Chapter 6 — Database Design Using the E-R Model.

Flashcard

flashcards Sebutkan tiga fase utama proses desain basis data :: Fase awal (karakterisasi kebutuhan data), fase kedua (memilih data model & membuat skema konseptual), fase akhir (logical design dan physical design). Apa dua kesalahan utama yang harus dihindari dalam mendesain skema basis data? :: Redundancy (informasi berulang yang berisiko menyebabkan inkonsistensi data) dan incompleteness (desain gagal memodelkan aspek tertentu dari enterprise). Sebutkan tiga konsep dasar ER data model :: Entity set, relationship set, dan attribute. Apa perbedaan primary key untuk relationship set many-to-many dibanding one-to-many? :: Many-to-many: primary key adalah union seluruh primary key entity yang terlibat. One-to-many: primary key sisi “many” saja sudah cukup (minimal superkey). Apa itu weak entity set dan bagaimana ia diidentifikasi secara unik? :: Entity set yang eksistensinya bergantung pada entity lain (identifying entity); diidentifikasi lewat kombinasi primary key identifying entity plus atribut discriminator milik weak entity itu sendiri. Bagaimana notasi weak entity set, discriminator, dan identifying relationship pada ER diagram? :: Weak entity set = double rectangle; discriminator = garis bawah putus-putus; identifying relationship = double diamond. Kenapa hanya boleh ada paling banyak satu panah keluar dari relationship ternary untuk menandai cardinality constraint? :: Karena lebih dari satu panah menimbulkan ambiguitas — ada dua kemungkinan interpretasi berbeda yang dipakai pada formalisme ER berbeda, sehingga dilarang untuk menghindari kebingungan. Apa perbedaan total participation dan partial participation? :: Total: setiap entity di entity set wajib berpartisipasi minimal satu kali dalam relationship set (digambar garis ganda). Partial: sebagian entity boleh tidak berpartisipasi sama sekali (garis tunggal). Apa perbedaan specialization dan generalization? :: Specialization adalah proses top-down (memecah entity set jadi subgrup lower-level); generalization adalah proses bottom-up (menggabungkan beberapa entity set jadi satu higher-level entity set) — keduanya digambar sama di ER diagram dengan triangle ISA. Apa perbedaan constraint disjoint vs overlapping pada specialization? :: Disjoint: satu entity hanya boleh jadi anggota satu lower-level entity set. Overlapping: satu entity boleh jadi anggota lebih dari satu lower-level entity set sekaligus. Apa fungsi aggregation dalam ER model dan kapan dipakai? :: Memperlakukan sebuah relationship sebagai entity abstrak sehingga bisa direlasikan lebih lanjut dengan entity lain — dipakai saat dua relationship (mis. proj_guide dan eval_for) merepresentasikan informasi yang tumpang tindih dan relationship pertama tidak bisa dibuang begitu saja. Bagaimana cara mengonversi relationship non-binary (ternary) menjadi kumpulan relationship binary? :: Buat entity set artifisial E dengan atribut pengidentifikasi sendiri (plus atribut milik relationship asli), lalu buat relationship binary terpisah dari E ke tiap entity set asal (R_A, R_B, R_C); tiap instance relationship asli menjadi satu entity baru di E yang dihubungkan ke masing-masing entity terkait.

Catatan Kuliah

Penjelajah