Pertanyaan Mewakili Memesan dalam Basis Data Relasional


Saya memiliki koleksi objek dalam database. Gambar di galeri foto, produk dalam katalog, bab dalam buku, dll. Setiap objek direpresentasikan sebagai baris. Saya ingin dapat secara acak memesan gambar-gambar ini, menyimpan urutan itu dalam database sehingga ketika saya menampilkan objek, mereka akan berada dalam urutan yang benar.

Sebagai contoh, katakanlah saya sedang menulis buku, dan setiap bab adalah sebuah objek. Saya menulis buku saya, dan menyusun bab-bab dalam urutan berikut:

Pendahuluan, Aksesibilitas, Formulir vs Fungsi, Kesalahan, Konsistensi, Kesimpulan, Indeks

Ini pergi ke editor, dan kembali dengan urutan yang disarankan berikut ini:

Pendahuluan, Formulir, Fungsi, Aksesibilitas, Konsistensi, Kesalahan, Kesimpulan, Indeks

Bagaimana saya dapat menyimpan pemesanan ini dalam database dengan cara yang kuat dan efisien?

Saya memiliki ide-ide berikut, tetapi saya tidak senang dengan salah satu dari mereka:

  1. Array. Setiap baris memiliki ID pemesanan, ketika pesanan diubah (melalui penghapusan diikuti oleh penyisipan), ID pesanan diperbarui. Ini memudahkan pengambilan, karena hanya saja ORDER BY, tetapi tampaknya mudah rusak.

    // REMOVAL
    UPDATE ... SET orderingID=NULL WHERE orderingID=removedID
    UPDATE ... SET orderingID=orderingID-1 WHERE orderingID > removedID
    // INSERTION
    UPDATE ... SET orderingID=orderingID+1 WHERE orderingID > insertionID
    UPDATE ... SET orderID=insertionID WHERE ID=addedID

  2. Daftar tertaut. Setiap baris memiliki kolom untuk id dari baris berikutnya dalam pemesanan. Traversal tampaknya mahal di sini, meskipun mungkin ada beberapa cara untuk digunakan ORDER BY bahwa saya tidak memikirkan.

  3. Array spasi. Set orderID (seperti yang digunakan dalam # 1) menjadi besar, jadi objek pertama adalah 100, yang kedua adalah 200, dll. Kemudian ketika penyisipan terjadi, Anda hanya menempatkannya di (objectBefore + objectAfter)/2. Tentu saja, ini perlu diseimbangkan kembali sesekali, jadi Anda tidak memiliki hal-hal yang terlalu berdekatan (bahkan dengan pelampung, Anda akhirnya akan mengalami kesalahan pembulatan).

Tidak ada yang tampak sangat elegan bagi saya. Adakah yang punya cara yang lebih baik untuk melakukannya?


32
2017-08-21 23:01


asal


Jawaban:


Alternatif lain akan (jika RDBMS Anda mendukungnya) untuk menggunakan kolom tipe array. Meskipun ini melanggar aturan normalisasi, itu bisa berguna dalam situasi seperti ini. Satu database yang saya tahu tentang yang memiliki array adalah PostgreSQL.


5
2017-08-22 05:32



The acts_as_list mixin di Rails menangani ini pada dasarnya seperti yang Anda gariskan di # 1. Ini mencari posisi kolom yang disebut INTEGER (yang dapat Anda ganti dengan nama saja) dan menggunakannya untuk melakukan ORDER BY. Ketika Anda ingin mengatur ulang hal-hal yang Anda perbarui posisi. Itu telah melayaniku dengan baik setiap kali aku menggunakannya.

Sebagai catatan tambahan, Anda dapat menghapus kebutuhan untuk selalu melakukan re-positioning pada INSERTS / DELETES dengan menggunakan penomoran sparse - seperti kembali ke dasar pada hari itu ... Anda dapat menghitung posisi Anda 10, 20, 30, dll. dan jika Anda perlu memasukkan sesuatu di antara 10 dan 20 Anda hanya memasukkannya dengan posisi 15. Begitu juga saat menghapus Anda hanya dapat menghapus baris dan meninggalkan celah. Anda hanya perlu melakukan penomoran ulang ketika Anda benar-benar mengubah urutan atau jika Anda mencoba melakukan insert dan tidak ada celah yang tepat untuk dimasukkan ke dalam.

Tentu saja tergantung pada situasi khusus Anda (misalnya apakah Anda memiliki baris lain yang sudah dimuat ke dalam memori atau tidak) mungkin atau mungkin tidak masuk akal untuk menggunakan pendekatan celah.


3
2017-08-21 23:11



Hanya mempertimbangkan pemikiran opsi # 1 vs # 3: tidakkah opsi array spasi (# 3) hanya menunda masalah dari array normal (# 1)? Apapun algoritma yang Anda pilih, apakah itu rusak, dan Anda akan mengalami masalah dengan # 3 nanti, atau berhasil, dan kemudian # 1 harus berfungsi dengan baik.


3
2017-08-25 17:24



Saya akan melakukan nomor berurutan, dengan pemicu di atas meja yang "membuat ruang" untuk prioritas jika sudah ada.


2
2017-08-21 23:12



Jika objek tidak terlalu dikunci oleh tabel lain, dan daftar pendek, menghapus semuanya di domain dan hanya memasukkan kembali daftar yang benar adalah yang paling mudah. Tapi itu tidak praktis jika daftar besar dan Anda memiliki banyak kendala untuk memperlambat penghapusan. Saya pikir metode pertama Anda adalah yang paling bersih. Jika Anda menjalankannya dalam transaksi, Anda bisa yakin tidak ada yang aneh saat Anda berada di tengah pembaruan untuk mengacaukan pesanan.


2
2017-08-22 01:39



Gunakan nomor floating point untuk mewakili posisi setiap item:

Butir 1 -> 0,0

Butir 2 -> 1.0

Butir 3 -> 2.0

Butir 4 -> 3.0

Anda dapat menempatkan item apa pun di antara dua item lainnya dengan pembelahan sederhana:

Butir 1 -> 0,0

Butir 4 -> 0,5

Butir 2 -> 1.0

Butir 3 -> 2.0

(Pindah item 4 antara item 1 dan 2).

Proses pembelahan dapat berlanjut hampir tanpa batas karena cara nomor floating point dikodekan dalam sistem komputer.

Butir 4 -> 0,5

Butir 1 -> 0,75

Butir 2 -> 1.0

Butir 3 -> 2.0

(Pindahkan item 1 ke posisi tepat setelah Item 4)


2
2017-09-18 00:22



Saya melakukan ini dalam proyek terakhir saya, tetapi untuk meja yang hanya sesekali perlu dipesan secara khusus, dan tidak terlalu sering diakses. Saya pikir array spasi akan menjadi pilihan terbaik, karena penataan ulang akan menjadi termurah dalam kasus rata-rata, hanya melibatkan perubahan ke satu nilai dan permintaan pada dua).

Juga, saya akan membayangkan ORDER BY akan sangat dioptimalkan oleh vendor database, sehingga memanfaatkan fungsi itu akan menguntungkan untuk kinerja yang bertentangan dengan implementasi daftar terkait.


1
2017-08-22 01:58



Saya punya masalah ini juga. Saya berada di bawah tekanan waktu yang berat (bukan kita semua) dan saya memilih opsi # 1, dan hanya memperbarui baris yang berubah.

Jika Anda menukar item 1 dengan item 10, cukup lakukan dua pembaruan untuk memperbarui nomor urut item 1 dan butir 10. Saya tahu itu sederhana secara algoritme, dan itu adalah kasus terburuk O (n), tetapi kasus terburuk adalah ketika Anda memiliki permutasi total daftar. Seberapa sering hal itu akan terjadi? Itu untuk Anda jawab.


1
2017-09-18 00:34



Karena saya kebanyakan bertemu dengan ini dengan Django, saya telah menemukan solusi ini menjadi yang paling bisa diterapkan. Tampaknya tidak ada "cara yang benar" untuk melakukan ini dalam basis data relasional.


1
2018-03-29 14:47



Saya memiliki masalah yang sama dan mungkin menghabiskan setidaknya satu minggu tentang diri saya sendiri tentang pemodelan data yang tepat, tetapi saya pikir saya akhirnya mendapatkannya. Dengan menggunakan tipe data array di PostgreSQL, Anda dapat menyimpan kunci utama dari setiap item yang dipesan dan memperbarui larik tersebut sesuai dengan sisipan atau penghapusan ketika pesanan Anda berubah. Mereferensikan satu baris akan memungkinkan Anda untuk memetakan semua objek berdasarkan urutan di kolom larik.

Ini masih sedikit berombak solusi tetapi kemungkinan akan bekerja lebih baik daripada opsi # 1, karena opsi 1 membutuhkan memperbarui nomor urut semua baris lainnya saat memesan perubahan.


0
2018-01-28 10:32