قواعد - جمل الاستعلام في sql




ما هي خيارات تخزين البيانات الهرمية في قاعدة بيانات علائقية؟ (5)

نظرات عامة جيدة

بشكل عام ، أنت تقوم باتخاذ قرار بين أوقات القراءة السريعة (على سبيل المثال ، مجموعة متداخلة) أو أوقات الكتابة السريعة (قائمة التأشير). عادة ، ينتهي بك الأمر مع مجموعة من الخيارات أدناه التي تناسب احتياجاتك. يوفر ما يلي بعض القراءة المتعمقة:

خيارات

تلك أنا على علم وميزات عامة:

  1. قائمة التجاور :
    • الأعمدة: المعرف ، ParentID
    • سهل التنفيذ.
    • العقدة الرخيصة يتحرك ويدرج وحذف.
    • باهظة الثمن للعثور على المستوى (يمكن تخزين كعمود محسوب) ، والنسب والأحفاد (الجدول الجسر جنبا إلى جنب مع عمود المستوى يمكن أن تحل) ، المسار (يمكن حل العمود الأميال).
    • استخدم تعبيرات جدول شائعة في قواعد البيانات هذه التي تدعمها لاجتياز.
  2. مجموعة متداخلة (ويعرف أيضًا باسم Travers Tree Pass Traversal)
    • شعبية من قبل جو Celko في العديد من المقالات وكتابه الأشجار والتسلسلات الهرمية في SQL ل Smarties
    • الأعمدة: اليسار واليمين
    • مستوى رخيص ، النسب ، أحفاد
    • تشفير متقلب - التحركات ، إدراج ، حذف أكثر تكلفة.
    • يتطلب ترتيبًا محددًا (على سبيل المثال ، تم إنشاؤه). لذا فإن فرز كل الأحفاد بترتيب مختلف يتطلب عملاً إضافيًا.
  3. فترات متداخلة
    • مثل مجموعة متداخلة ، ولكن مع / float / decimal حقيقي بحيث لا يكون التشفير متقلبًا (نقل / إدراج / حذف رخيص)
    • يجب أن تتعامل مع قضايا التمثيل الحقيقي / تعويم / العشرية
    • يضيف متغير تشفير أكثر تعقيدًا لمصفوفة ميزة ترميز السلف ، مثل مسار مائي لـ "free"
  4. الجدول الجسر (ويعرف أيضا باسم جدول الإغلاق : بعض الأفكار الجيدة حول كيفية استخدام المحفزات للحفاظ على هذا النهج)
    • الأعمدة: سلف ، سليل
    • يقف بصرف النظر عن الجدول الذي يصفه.
    • يمكن أن تتضمن بعض العقد في أكثر من التسلسل الهرمي.
    • النسب والأحفاد رخيصة (وإن لم يكن في أي ترتيب)
    • للحصول على معرفة كاملة بالتسلسل الهرمي ، يجب دمجها مع خيار آخر.
  5. جدول مسطح
    • تعديل في قائمة Adjacency التي تضيف عمودًا للمستوى والترتيب (على سبيل المثال الترتيب) لكل سجل.
    • حركة مكلفة وحذف
    • النسب رخيصة وأحفاد
    • الاستخدام الجيد: مناقشة مترابطة - منتديات / مدونة التعليقات
  6. عمود Lineage (ويعرف أيضاً بمسار مقيس ، تعداد المسار)
    • العمود: النسب (على سبيل المثال / الوالد / الطفل / الحفيد / الخ ...)
    • الحد إلى مدى عمق التسلسل الهرمي.
    • أحفاد رخيصة (على سبيل المثال LEFT(lineage, #) = '/enumerated/path' )
    • النسب صعبة (استعلامات قاعدة بيانات محددة)
  7. أعمدة النسب متعددة
    • الأعمدة: واحد لكل مستوى سلالة ، يشير إلى جميع الوالدين إلى الجذر ، المستويات من مستوى العنصر محددة إلى NULL
    • الحد إلى مدى عمق التسلسل الهرمي
    • أسلاف رخيصة ، أحفاد ، مستوى
    • إدراج رخيصة ، وحذف ، ونقل الأوراق
    • غالية إدراج ، حذف ، نقل العقد الداخلية

ملاحظات قاعدة البيانات محددة

الخلية

وحي

  • استخدم CONNECT BY لاجتياز قوائم Adjacency

كيو

خادم قاعدة البيانات

  • الملخص العام
  • يقدم 2008 نوع بيانات HierarchyId يظهر للمساعدة في نهج Lineage Column وتوسيع العمق الذي يمكن تمثيله.

نموذج Adjacency + نموذج مجموعات متداخلة

ذهبت لذلك لأنني يمكن إدراج عناصر جديدة إلى الشجرة بسهولة (تحتاج فقط إلى معرف الفرع لإدراج عنصر جديد إليه) وأيضا الاستعلام بسرعة كبيرة.

+-------------+----------------------+--------+-----+-----+
| category_id | name                 | parent | lft | rgt |
+-------------+----------------------+--------+-----+-----+
|           1 | ELECTRONICS          |   NULL |   1 |  20 |
|           2 | TELEVISIONS          |      1 |   2 |   9 |
|           3 | TUBE                 |      2 |   3 |   4 |
|           4 | LCD                  |      2 |   5 |   6 |
|           5 | PLASMA               |      2 |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |      1 |  10 |  19 |
|           7 | MP3 PLAYERS          |      6 |  11 |  14 |
|           8 | FLASH                |      7 |  12 |  13 |
|           9 | CD PLAYERS           |      6 |  15 |  16 |
|          10 | 2 WAY RADIOS         |      6 |  17 |  18 |
+-------------+----------------------+--------+-----+-----+
  • في كل مرة تحتاج فيها إلى جميع الأطفال من أي أحد ، يمكنك فقط الاستعلام عن العمود parent .
  • إذا كنت بحاجة إلى جميع أحفاد أي والد كنت تستعلم عن العناصر التي لها lft بين lft و rgt من الوالدين.
  • إذا كنت في حاجة إلى جميع الآباء من أي عقدة تصل إلى جذر الشجرة ، يمكنك الاستعلام عن العناصر التي لديها أقل من lft من lft في عقدة و rgt أكبر من rgt وفرز حسب parent .

كنت بحاجة إلى الوصول إلى الشجرة والاستفسار عنها أسرع من إدراجها ، ولهذا اخترتها

المشكلة الوحيدة هي إصلاح الأعمدة right عند إدخال عناصر جديدة. حسنًا ، لقد أنشأت إجراءًا مخزّنًا له وأدعوه في كل مرة أدخلت عنصرًا جديدًا نادرًا في حالتي ولكنه سريع جدًا. حصلت على فكرة من كتاب جو Celko ، ويتم شرح الإجراء المخزن وكيف توصلت إليه هنا في DBA SE https://dba.stackexchange.com/q/89051/41481


أستخدم PostgreSQL مع جداول الإغلاق للتسلسل الهرمي الخاص بي. لدي إجراء تخزين عالمي واحد لقاعدة البيانات بأكملها:

CREATE FUNCTION nomen_tree() RETURNS trigger
    LANGUAGE plpgsql
    AS $_$
DECLARE
  old_parent INTEGER;
  new_parent INTEGER;
  id_nom INTEGER;
  txt_name TEXT;
BEGIN
-- TG_ARGV[0] = name of table with entities with PARENT-CHILD relationships (TBL_ORIG)
-- TG_ARGV[1] = name of helper table with ANCESTOR, CHILD, DEPTH information (TBL_TREE)
-- TG_ARGV[2] = name of the field in TBL_ORIG which is used for the PARENT-CHILD relationship (FLD_PARENT)
    IF TG_OP = 'INSERT' THEN
    EXECUTE 'INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT $1.id,$1.id,0 UNION ALL
      SELECT $1.id,ancestor_id,depth+1 FROM ' || TG_ARGV[1] || ' WHERE child_id=$1.' || TG_ARGV[2] USING NEW;
    ELSE                                                           
    -- EXECUTE does not support conditional statements inside
    EXECUTE 'SELECT $1.' || TG_ARGV[2] || ',$2.' || TG_ARGV[2] INTO old_parent,new_parent USING OLD,NEW;
    IF COALESCE(old_parent,0) <> COALESCE(new_parent,0) THEN
      EXECUTE '
      -- prevent cycles in the tree
      UPDATE ' || TG_ARGV[0] || ' SET ' || TG_ARGV[2] || ' = $1.' || TG_ARGV[2]
        || ' WHERE id=$2.' || TG_ARGV[2] || ' AND EXISTS(SELECT 1 FROM '
        || TG_ARGV[1] || ' WHERE child_id=$2.' || TG_ARGV[2] || ' AND ancestor_id=$2.id);
      -- first remove edges between all old parents of node and its descendants
      DELETE FROM ' || TG_ARGV[1] || ' WHERE child_id IN
        (SELECT child_id FROM ' || TG_ARGV[1] || ' WHERE ancestor_id = $1.id)
        AND ancestor_id IN
        (SELECT ancestor_id FROM ' || TG_ARGV[1] || ' WHERE child_id = $1.id AND ancestor_id <> $1.id);
      -- then add edges for all new parents ...
      INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT child_id,ancestor_id,d_c+d_a FROM
        (SELECT child_id,depth AS d_c FROM ' || TG_ARGV[1] || ' WHERE ancestor_id=$2.id) AS child
        CROSS JOIN
        (SELECT ancestor_id,depth+1 AS d_a FROM ' || TG_ARGV[1] || ' WHERE child_id=$2.' 
        || TG_ARGV[2] || ') AS parent;' USING OLD, NEW;
    END IF;
  END IF;
  RETURN NULL;
END;
$_$;

ثم أقوم بإنشاء مشغل لكل جدول يوجد به تسلسل هرمي

CREATE TRIGGER nomenclature_tree_tr AFTER INSERT OR UPDATE ON nomenclature FOR EACH ROW EXECUTE PROCEDURE nomen_tree('my_db.nomenclature', 'my_db.nom_helper', 'parent_id');

لتعبئة جدول الإغلاق من التسلسل الهرمي الحالي ، استخدم هذا الإجراء المخزن:

CREATE FUNCTION rebuild_tree(tbl_base text, tbl_closure text, fld_parent text) RETURNS void
    LANGUAGE plpgsql
    AS $$
BEGIN
    EXECUTE 'TRUNCATE ' || tbl_closure || ';
    INSERT INTO ' || tbl_closure || ' (child_id,ancestor_id,depth) 
        WITH RECURSIVE tree AS
      (
        SELECT id AS child_id,id AS ancestor_id,0 AS depth FROM ' || tbl_base || '
        UNION ALL 
        SELECT t.id,ancestor_id,depth+1 FROM ' || tbl_base || ' AS t
        JOIN tree ON child_id = ' || fld_parent || '
      )
      SELECT * FROM tree;';
END;
$$;

يتم تعريف جداول الإغلاق مع 3 أعمدة - ANCESTOR_ID ، DESCENDANT_ID ، DEPTH. من الممكن (وأنا حتى المشورة) لتخزين السجلات مع نفس القيمة لل ANCESTOR و DESCENDANT ، وقيمة صفر ل DEPTH. هذا سوف تبسيط الاستعلامات لاستعادة التسلسل الهرمي. وهي بسيطة للغاية في الواقع:

-- get all descendants
SELECT tbl_orig.*,depth FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth <> 0;
-- get only direct descendants
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth = 1;
-- get all ancestors
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON ancestor_id = tbl_orig.id WHERE descendant_id = XXX AND depth <> 0;
-- find the deepest level of children
SELECT MAX(depth) FROM tbl_closure WHERE ancestor_id = XXX;

جوابي المفضل هو ما اقترحته الجملة الأولى في هذا الموضوع. استخدم قائمة Adjacency للحفاظ على التسلسل الهرمي واستخدام مجموعات متداخلة للاستعلام عن التسلسل الهرمي.

تكمن المشكلة حتى الآن في أن طريقة الانقلاب من قائمة Adjacecy إلى مجموعات متداخلة كانت بطيئة بشكل مخيف لأن معظم الناس يستخدمون أسلوب RBAR المتطرف المعروف باسم "Push Stack" للقيام بالتحويل ، وقد تم اعتباره طريقة مكلفة للوصول إلى السكينة من بساطة الصيانة من خلال قائمة Adjacency والأداء الرائع للمجموعات المتداخلة. ونتيجة لذلك ، ينتهي الأمر بأن ينتهي معظم الأشخاص بالالتزام بواحد أو آخر ، خاصة إذا كان هناك أكثر من 100 ألف عقد رديء أو ما شابه. يمكن أن يستغرق استخدام طريقة تكديس الدفع يومًا كاملاً لإجراء التحويل على ما قد يعتبره MLM'ers عبارة عن تسلسل هرمي قدره مليون عقدة.

ظننت أنني سأعطي سيلكو بعض المنافسة من خلال طرح طريقة لتحويل قائمة Adjacency إلى مجموعات متداخلة بسرعات تبدو مستحيلة. إليك أداء طريقة دفع المكدس على الكمبيوتر المحمول i5.

Duration for     1,000 Nodes = 00:00:00:870 
Duration for    10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10)
Duration for   100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) 
Duration for 1,000,000 Nodes = 'Didn't even try this'

وهنا مدة الأسلوب الجديد (مع طريقة دفع المكدس بين قوسين).

Duration for     1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870)
Duration for    10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783)
Duration for   100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730)
Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!)

نعم هذا صحيح. تم تحويل مليون عقدة في أقل من دقيقة و 100 عقدة في أقل من 4 ثوانٍ.

يمكنك القراءة عن الطريقة الجديدة والحصول على نسخة من الشفرة على عنوان URL التالي. http://www.sqlservercentral.com/articles/Hierarchy/94040/

أنا أيضا وضعت التسلسل الهرمي "المجمعة مسبقا" باستخدام أساليب مماثلة. سوف MLM'ers والناس جعل فواتير المواد مهتمة بشكل خاص في هذه المقالة. http://www.sqlservercentral.com/articles/T-SQL/94570/

إذا توقفت عن إلقاء نظرة على أي من المقالات ، فانتقل إلى رابط "الانضمام إلى المناقشة" وأخبرني برأيك.


لم يذكر هذا التصميم بعد:

أعمدة النسب متعددة

على الرغم من وجود قيود ، إذا كنت تستطيع تحملها ، فهي بسيطة جدًا وفعالة للغاية. ميزات:

  • الأعمدة: واحد لكل مستوى سلالة ، يشير إلى جميع الوالدين إلى الجذر ، مستويات أقل من مستوى العناصر الحالية يتم تعيينها إلى NULL
  • الحد إلى مدى عمق التسلسل الهرمي
  • أسلاف رخيصة ، أحفاد ، مستوى
  • إدراج رخيصة ، وحذف ، ونقل الأوراق
  • غالية إدراج ، حذف ، نقل العقد الداخلية

وفيما يلي مثالاً على ذلك - الشجرة التصنيفية للطيور ، لذا فإن التسلسل الهرمي هو Class / Order / Family / Genus / Species - الأنواع هي أدنى مستوى ، صف 1 = 1 taxon (الذي يتوافق مع الأنواع في حالة العقد الورقية):

CREATE TABLE `taxons` (
  `TaxonId` smallint(6) NOT NULL default '0',
  `ClassId` smallint(6) default NULL,
  `OrderId` smallint(6) default NULL,
  `FamilyId` smallint(6) default NULL,
  `GenusId` smallint(6) default NULL,
  `Name` varchar(150) NOT NULL default ''
);

ومثال البيانات:

+---------+---------+---------+----------+---------+-------------------------------+
| TaxonId | ClassId | OrderId | FamilyId | GenusId | Name                          |
+---------+---------+---------+----------+---------+-------------------------------+
|     254 |       0 |       0 |        0 |       0 | Aves                          |
|     255 |     254 |       0 |        0 |       0 | Gaviiformes                   |
|     256 |     254 |     255 |        0 |       0 | Gaviidae                      |
|     257 |     254 |     255 |      256 |       0 | Gavia                         |
|     258 |     254 |     255 |      256 |     257 | Gavia stellata                |
|     259 |     254 |     255 |      256 |     257 | Gavia arctica                 |
|     260 |     254 |     255 |      256 |     257 | Gavia immer                   |
|     261 |     254 |     255 |      256 |     257 | Gavia adamsii                 |
|     262 |     254 |       0 |        0 |       0 | Podicipediformes              |
|     263 |     254 |     262 |        0 |       0 | Podicipedidae                 |
|     264 |     254 |     262 |      263 |       0 | Tachybaptus                   |

هذا أمر رائع لأنك بهذه الطريقة يمكنك إنجاز جميع العمليات المطلوبة بطريقة سهلة جدًا ، طالما أن الفئات الداخلية لا تغير مستوىها في الشجرة.


هذه إجابة جزئية جدًا على سؤالك ، لكنني آمل أن يكون مفيدًا.

يقوم Microsoft SQL Server 2008 بتنفيذ ميزتين مفيدتين للغاية لإدارة البيانات الهرمية:

  • نوع البيانات HierarchyId .
  • تعبيرات جدول شائع ، باستخدام الكلمة الأساسية.

إلقاء نظرة على "نموذج التسلسلات الهرمية البيانات الخاصة بك مع SQL Server 2008" بواسطة كينت Tegels على MSDN لتبدأ. راجع أيضًا سؤالي الخاص: استعلام متساوي نفس الجدول في SQL Server 2008





hierarchical-data