Memperluas (Elementary) Mathematical Data Model dan MatBase dengan dua tipe constraint baru: inexistence dan anti-existence

Definisi formal, analisis kompleksitas, dan implementasi MatBase untuk constraint eksistensi ganda

Christian Mancas· 2026· DOI 10.48550/arXiv.2605.24021

Masalah inti

(Elementary) Mathematical Data Model (EMDM) menyediakan fondasi yang ketat untuk constraint basis data. Karya sebelumnya mendefinisikan constraint existence dan non-existence, yang memastikan bahwa tuple tertentu harus atau tidak boleh ada dalam suatu relasi. Makalah ini memperkenalkan dua tipe constraint baru—inexistence dan anti-existence—yang merupakan dual dari existence dan non-existence. Constraint ini memperluas daya ekspresif EMDM dengan memungkinkan spesifikasi persyaratan negatif: misalnya, menyatakan bahwa kombinasi nilai tertentu tidak boleh ada, atau bahwa jika satu tuple ada, tuple lain tidak boleh ada. Makalah ini mendefinisikan constraint tersebut secara formal, mengarakterisasi propertinya, dan mempelajari well-formedness, satisfiability, coherence, serta minimality dari himpunan yang memuat ketujuh subtipe constraint existence. Makalah ini juga menyajikan algoritma pseudocode yang tertanam dalam SQL untuk mengelola himpunan tersebut, membuktikannya berkompleksitas konstan, sound, complete, dan optimal. Selanjutnya, algoritma untuk menegakkan constraint inexistence dan anti-existence disediakan, dengan kompleksitas linear dalam jumlah aritas fungsi (Cartesian produ

Makalah ini mendefinisikan secara formal dua tipe constraint baru: inexistence dan anti-existence, masing-masing dengan dua subtipe, sehingga menghasilkan empat subtipe baru. Bersama dengan tiga subtipe constraint existence yang sudah ada, totalnya menjadi tujuh subtipe. Definisi formal disertai contoh nyata, seperti basis data universitas di mana seorang mahasiswa tidak dapat terdaftar dalam dua mata kuliah yang dijadwalkan pada waktu yang sama (constraint anti-existence). Kajian well-formedness, satisfiability, coherence, dan minimality menunjukkan bahwa himpunan constraint ini dapat diperiksa secara efisien. Algoritma pengelolaan terbukti berkompleksitas konstan, artinya menambah, menghapus, atau memeriksa constraint memerlukan waktu yang tidak bergantung pada ukuran basis data. Algoritma penegakan terbukti berkompleksitas linear dalam jumlah aritas fungsi (Cartesian product) yang terlibat. Misalnya, jika suatu constraint melibatkan dua relasi dengan aritas 3 dan 4, waktu penegakannya adalah O (7) . Algoritma juga terbukti sound (tidak pernah menolak basis data yang valid), complete (selalu menolak basis data yang tidak valid), dan optimal (tidak ada algoritma yang dapat lebih b

(Elementary) Mathematical Data Model (EMDM) menyediakan fondasi yang ketat untuk constraint basis data. Karya sebelumnya mendefinisikan constraint existence dan non-existence, yang memastikan bahwa tuple tertentu harus atau tidak boleh ada dalam suatu relasi. Makalah ini memperkenalkan dua tipe constraint baru—inexistence dan anti-existence—yang merupakan dual dari existence dan non-existence. Constraint ini memperluas daya ekspresif EMDM dengan memungkinkan spesifikasi persyaratan negatif: misalnya, menyatakan bahwa kombinasi nilai tertentu tidak boleh ada, atau bahwa jika satu tuple ada, tuple lain tidak boleh ada. Makalah ini mendefinisikan constraint tersebut secara formal, mengarakterisasi propertinya, dan mempelajari well-formedness, satisfiability, coherence, serta minimality dari himpunan yang memuat ketujuh subtipe constraint existence. Makalah ini juga menyajikan algoritma pseudocode yang tertanam dalam SQL untuk mengelola himpunan tersebut, membuktikannya berkompleksitas konstan, sound, complete, dan optimal. Selanjutnya, algoritma untuk menegakkan constraint inexistence dan anti-existence disediakan, dengan kompleksitas linear dalam jumlah aritas fungsi (Cartesian product) yang terlibat. Semua algoritma diimplementasikan di kedua versi MatBase, sebuah prototipe sistem manajemen basis data dan pengetahuan cerdas yang secara otomatis menghasilkan kode untuk menegakkan ketujuh subtipe constraint existence.

Metodologi penelitian mengikuti pendekatan formal. Pertama, penulis memperluas EMDM dengan mendefinisikan constraint inexistence dan anti-existence beserta empat subtipe-nya. Constraint ini dispesifikasikan secara formal menggunakan teori himpunan dan logika orde pertama. Untuk skema relasi R dan constraint C tertentu, kondisi pemenuhan dinyatakan sebagai:

Pengenalan constraint inexistence dan anti-existence melengkapi dualitas constraint existence di EMDM. Kompleksitas konstan algoritma pengelolaan memastikan himpunan constraint dapat dipelihara secara efisien bahkan untuk skema besar. Kompleksitas linear algoritma penegakan bersifat optimal karena algoritma apa pun setidaknya harus memeriksa tuple yang terlibat dalam Cartesian product. Bukti soundness, completeness, dan optimality memberikan jaminan kuat untuk kebenaran dan efisiensi implementasi. Integrasi ke MatBase menunjukkan penerapan praktis: sistem dapat secara otomatis menghasilkan kode SQL untuk menegakkan constraint ini, mengurangi beban pengembang basis data. Makalah ini juga membahas implikasi untuk desain basis data, dengan mencatat bahwa constraint ini memungkinkan pemodelan persyaratan dunia nyata yang lebih presisi, seperti mencegah penugasan yang bertentangan atau memastikan kombinasi nilai tertentu tidak pernah terjadi. Pekerjaan selanjutnya mencakup perluasan model untuk mendukung constraint temporal dan basis data terdistribusi. Secara keseluruhan, penelitian ini meningkatkan daya ekspresif EMDM dan menyediakan fondasi teoretis serta praktis yang solid untuk pengelolaan constraint tingkat lanjut.

Praktisi dan peneliti ilmu komputer

Membuka konten member…