sql - একটি গাছ মধ্যে একটি সমতল টেবিল বিশ্লেষণ সবচেয়ে দক্ষ/মার্জিত উপায় কি?




algorithm recursion (10)

অনুমান করুন যে আপনার একটি সমতল টেবিল রয়েছে যা একটি ক্রম অনুসারে সাজানো গাছপালা সংরক্ষণ করে:

Id   Name         ParentId   Order
 1   'Node 1'            0      10
 2   'Node 1.1'          1      10
 3   'Node 2'            0      20
 4   'Node 1.1.1'        2      10
 5   'Node 2.1'          3      10
 6   'Node 1.2'          1      20

এখানে একটি চিত্র, যেখানে আমরা [id] Name । রুট নোড 0 কাল্পনিক।

                       [0] ROOT
                          /    \ 
              [1] Node 1          [3] Node 2
              /       \                   \
    [2] Node 1.1     [6] Node 1.2      [5] Node 2.1
          /          
 [4] Node 1.1.1

সঠিকভাবে নির্দেশিত, সঠিকভাবে ইন্ডেন্ট গাছ হিসাবে এইচটিএমএল (বা টেক্সট, যে ক্ষেত্রে) জন্য আউটপুট আউটপুট ব্যবহার করার জন্য আপনি কোন সহজ পদ্ধতি ব্যবহার করবেন?

অনুমান করুন আপনার কেবলমাত্র প্রাথমিক ডেটা স্ট্রাকচারগুলি (অ্যারে এবং হ্যাশহ্যাপস) রয়েছে, প্যারেন্ট / শিশু রেফারেন্সগুলির সাথে কোনও অভিনব বস্তু নেই, কোনও ORM, কোন ফ্রেমওয়ার্ক নেই, কেবল আপনার দুটি হাত রয়েছে। টেবিলটি ফলাফল সেট হিসাবে উপস্থাপিত হয়, যা এলোমেলোভাবে অ্যাক্সেস করা যেতে পারে।

ছদ্ম কোড বা প্লেইন ইংরেজি ঠিক আছে, এই বিশুদ্ধরূপে একটি ধারণাগত প্রশ্ন।

বোনাস প্রশ্ন: একটি RDBMS এ যেমন একটি গাছ কাঠামো সংরক্ষণ করার জন্য একটি মৌলিকভাবে ভাল উপায় আছে?

সম্পাদনা এবং অ্যাড

একজন মন্তব্যকারীর ( মার্ক বেসির ) প্রশ্নের উত্তর দিতে: একটি রুট নোড প্রয়োজনীয় নয়, কারণ এটি যে কোনওভাবে প্রদর্শিত হবে না। ParentId = 0 "এই শীর্ষ স্তরের" প্রকাশ করার জন্য কনভেনশন। অর্ডার কলামটি একই পিতামাতার সাথে নোডগুলি কীভাবে সাজানো হবে তা সংজ্ঞায়িত করে।

আমি যে "ফলাফল সেট" কথা বলেছি তা হাশম্যাপগুলির একটি অ্যারের রূপে চিত্রিত করা যেতে পারে (যে পরিভাষায় থাকার জন্য)। আমার উদাহরণের জন্য ইতিমধ্যে সেখানে বোঝানো ছিল। কিছু উত্তর অতিরিক্ত মাইল যান এবং এটি প্রথম নির্মাণ, কিন্তু ঠিক আছে।

গাছ ইচ্ছাকৃতভাবে গভীর হতে পারে। প্রতিটি নোড এন শিশুদের থাকতে পারে। আমার মনে আছে ঠিক তেমন "লক্ষ লক্ষ এন্ট্রি" গাছ নেই।

কিছু নির্ভর করার জন্য নোড নামকরণের ('নোড 1.1.1') আমার পছন্দটি ভুল করবেন না। নোডগুলি সমানভাবে ফ্র্যাঙ্ক বা বব নামে পরিচিত হতে পারে, কোনও নামকরণের কাঠামো ইঙ্গিত করা হয় না, এটি কেবল এটি পাঠযোগ্য করে তুলতে পারে।

আমি আমার নিজের সমাধান পোস্ট করেছি তাই আপনি ছেলেরা এটা টুকরা টানতে পারেন।


Nested হ্যাশ মানচিত্র বা অ্যারে তৈরি করা যেতে পারে, তাহলে আমি কেবল শুরু থেকে টেবিল নিচে যেতে এবং প্রতিটি আইটেম ন্যস্ত অ্যারে যোগ করতে পারেন। নেস্টেড অ্যারে কোন স্তরের সন্নিবেশ করতে হবে তা জানতে আমাকে রুট নোডের প্রতিটি লাইন ট্রেস করতে হবে। আমি মেমোজাইজেশন নিযুক্ত করতে পারি যাতে আমাকে একই অভিভাবককে আবার ওঠার প্রয়োজন হয় না।

সম্পাদন করুন: আমি সম্পূর্ণ টেবিলে প্রথম অ্যারেটি পড়ব, তাই এটি বারবার ডাবিকে জিজ্ঞাসা করবে না। আপনার টেবিল খুব বড় যদি অবশ্যই এই ব্যবহারিক হবে না।

কাঠামোটি তৈরি করার পরে, প্রথমে এটির মাধ্যমে গভীরতার গভীরতা এবং HTML প্রিন্ট আউট করতে হবে।

এই টেবিলের সাহায্যে এই তথ্য সংরক্ষণের কোনও ভাল মৌলিক উপায় নেই (যদিও আমি ভুল হতে পারি;), এবং একটি ভাল সমাধান দেখতে চাই)। যাইহোক, যদি আপনি গতিশীলভাবে নির্মিত ডিবি টেবিলগুলি নিযুক্ত করার জন্য একটি প্রকল্প তৈরি করেন তবে সরলতার উত্সর্গ এবং SQL সার্কেলের ঝুঁকিতে আপনি একটি সম্পূর্ণ নতুন বিশ্ব খুলেন;)।


আপনি যদি জানেন যে মূল উপাদানটি শূন্য হয় তবে অনুমান করুন এখানে ছদ্মকোডটি পাঠ্য থেকে আউটপুট হয়:

function PrintLevel (int curr, int level)
    //print the indents
    for (i=1; i<=level; i++)
        print a tab
    print curr \n;
    for each child in the table with a parent of curr
        PrintLevel (child, level+1)


for each elementID where the parentid is zero
    PrintLevel(elementID, 0)

আপনি হাশম্যাপের সাথে অন্য কোনও ডেটা গঠন অনুকরণ করতে পারেন, তাই এটি একটি ভয়ানক সীমাবদ্ধতা নয়। উপরের থেকে নীচের দিকে স্ক্যান করা, প্রতিটি কলামের জন্য একটি এন্ট্রি সহ ডাটাবেসের প্রতিটি সারির জন্য একটি হ্যাশম্যাপ তৈরি করুন। এই হ্যাশম্যাপগুলি প্রতিটিতে "মাস্টার" হ্যাশম্যাপে যোগ করুন, আইডিটিতে কী কী আছে। যদি কোনও নোডের একটি "পিতা-মাতা" আছে যা আপনি এখনও দেখেননি, তবে মাস্টার হ্যাশহ্যাপ-এ এটির জন্য একটি স্থানধারক এন্ট্রি তৈরি করুন এবং যখন আপনি প্রকৃত নোড দেখেন তখন এটি পূরণ করুন।

এটি প্রিন্ট করার জন্য, একটি সহজ গভীরতা-প্রথমটি তথ্য দিয়ে পাস করুন, পাশাপাশি ইন্ডেন্ট স্তরের ট্র্যাক রাখুন। আপনি প্রতিটি সারির জন্য একটি "শিশু" এন্ট্রি রেখে এটিকে আরও সহজ করে তুলতে পারেন এবং এটি ডেটা স্ক্যান করার সময় এটি বাড়িয়ে তুলতে পারেন।

ডেটাবেসে একটি গাছ সংরক্ষণ করার জন্য "ভাল" উপায় থাকা সত্ত্বেও, আপনি কীভাবে ডেটা ব্যবহার করতে যাচ্ছেন তার উপর নির্ভর করে। আমি এমন সিস্টেমে দেখেছি যা সর্বাধিক পরিচিত গভীরতা যা পংক্তির প্রতিটি স্তরের জন্য একটি ভিন্ন টেবিল ব্যবহার করে। বৃক্ষের মাত্রাগুলি সব পরে সমান নয় (শীর্ষ স্তরের বিভাগগুলি পাতা থেকে আলাদা) যদি এটি অনেক অর্থপূর্ণ করে তোলে।


এখন মাইএসকিউএল 8.0 রিলিজের কাছাকাছি, সব জনপ্রিয় এসকিউএল ডেটাবেস স্ট্যান্ডার্ড সিনট্যাক্সে পুনরাবৃত্তিমূলক প্রশ্নগুলিকে সমর্থন করবে

WITH RECURSIVE MyTree AS (
    SELECT * FROM MyTable WHERE ParentId IS NULL
    UNION ALL
    SELECT m.* FROM MyTABLE AS m JOIN MyTree AS t ON m.ParentId = t.Id
)
SELECT * FROM MyTree;

আমি MySQL 8.0 এ পুনরাবৃত্তিমূলক ক্যোয়ারী পরীক্ষা করে দেখলাম আমার উপস্থাপনায় পুনরাবৃত্তিমূলক প্রশ্ন থ্রোডাউন 2017।

নীচে আমার মূল উত্তর 2008 থেকে:

একটি সম্পর্কীয় ডাটাবেসের মধ্যে গাছ-কাঠামোগত তথ্য সংরক্ষণ করার বিভিন্ন উপায় আছে। আপনি আপনার উদাহরণে কী দেখেন দুটি পদ্ধতি ব্যবহার করে:

  • Adjacency তালিকা ("অভিভাবক" কলাম) এবং
  • পথ পরিমাপ (আপনার নাম কলামের ডট-সংখ্যার সংখ্যা)।

আরেকটি সমাধান নেস্টেড সেট বলা হয়, এবং এটি একই টেবিলে সংরক্ষণ করা যেতে পারে। এই ডিজাইনগুলিতে অনেক বেশি তথ্যের জন্য জো সেলকোর দ্বারা "স্মার্টফোনের জন্য এসকিউএলগুলিতে গাছ এবং বংশবৃদ্ধি" পড়ুন।

আমি সাধারণত গাছ-কাঠামোগত ডেটা সংরক্ষণের জন্য ক্লোজার টেবিল (উকিল "অ্যাডজ্যাকেন্সি রিলেশন") নামে একটি নকশা পছন্দ করি। এটি অন্য টেবিল প্রয়োজন, কিন্তু তারপর গাছ জিজ্ঞাসা বেশ সহজ।

আমি আমার উপস্থাপনায় ক্লোজার টেবিলটি আচ্ছাদন করছি এসকিউএল এবং পিএইচপি সহ হায়ারার্কিক্যাল ডেটা এবং আমার বই এসকিউএল এন্টিপ্টার্নসগুলিতে: ডেটাবেস প্রোগ্রামিংয়ের সমস্যাগুলি এড়ানো

CREATE TABLE ClosureTable (
  ancestor_id   INT NOT NULL REFERENCES FlatTable(id),
  descendant_id INT NOT NULL REFERENCES FlatTable(id),
  PRIMARY KEY (ancestor_id, descendant_id)
);

ক্লোজার টেবিলে সমস্ত পাথ সংরক্ষণ করুন, যেখানে একটি নোড থেকে অন্য একটি সরাসরি বংশধর রয়েছে। নিজেই উল্লেখ করতে প্রতিটি নোডের জন্য একটি সারি অন্তর্ভুক্ত করুন। উদাহরণস্বরূপ, আপনার ডেটা সেট ব্যবহার করে আপনি আপনার প্রশ্নে দেখিয়েছেন:

INSERT INTO ClosureTable (ancestor_id, descendant_id) VALUES
  (1,1), (1,2), (1,4), (1,6),
  (2,2), (2,4),
  (3,3), (3,5),
  (4,4),
  (5,5),
  (6,6);

এখন আপনি এই ধরনের নোড 1 এ শুরু হওয়া একটি গাছ পেতে পারেন:

SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1;

আউটপুট (মাইএসকিউএল ক্লায়েন্টে) নীচের মত দেখাচ্ছে:

+----+
| id |
+----+
|  1 | 
|  2 | 
|  4 | 
|  6 | 
+----+

অন্য কথায়, নোড 3 এবং 5 বাদ দেওয়া হয়, কারণ তারা একটি পৃথক অনুক্রমের অংশ, নোড 1 থেকে নেমে না।

Re: অবিলম্বে শিশুদের (বা অবিলম্বে পিতামাতা) সম্পর্কে ই সাটিস থেকে মন্তব্য। আপনি path_length একটি " path_length " কলাম যোগ করতে পারেন যাতে এটি বিশেষভাবে তাত্ক্ষণিক সন্তানের বা অভিভাবকের (অথবা অন্য কোনও দূরত্ব) জন্য অনুসন্ধান করা সহজ করে।

INSERT INTO ClosureTable (ancestor_id, descendant_id, path_length) VALUES
  (1,1,0), (1,2,1), (1,4,2), (1,6,1),
  (2,2,0), (2,4,1),
  (3,3,0), (3,5,1),
  (4,4,0),
  (5,5,0),
  (6,6,0);

তারপরে আপনি প্রদত্ত নোডের অবিলম্বে শিশুদের জিজ্ঞাসা করার জন্য আপনার অনুসন্ধানে একটি শব্দ যোগ করতে পারেন। এই বংশধর যাদের পথ path_length 1।

SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
  AND path_length = 1;

+----+
| id |
+----+
|  2 | 
|  6 | 
+----+

@ আশরাফের মন্তব্য করুনঃ "পুরো গাছটি [নাম অনুসারে] সাজানোর কীভাবে?"

নোড 1 এর বংশধর সমস্ত নোড ফেরত দেওয়ার জন্য এখানে একটি উদাহরণ অনুসন্ধান রয়েছে, ফ্ল্যাটটেবলে তাদের সাথে যোগ দিন যাতে name হিসাবে অন্যান্য নোড বৈশিষ্ট্য রয়েছে এবং name সাজান।

SELECT f.name
FROM FlatTable f 
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
ORDER BY f.name;

@ ন্যেট থেকে মন্তব্য করুন:

SELECT f.name, GROUP_CONCAT(b.ancestor_id order by b.path_length desc) AS breadcrumbs
FROM FlatTable f 
JOIN ClosureTable a ON (f.id = a.descendant_id) 
JOIN ClosureTable b ON (b.descendant_id = a.descendant_id) 
WHERE a.ancestor_id = 1 
GROUP BY a.descendant_id 
ORDER BY f.name

+------------+-------------+
| name       | breadcrumbs |
+------------+-------------+
| Node 1     | 1           |
| Node 1.1   | 1,2         |
| Node 1.1.1 | 1,2,4       |
| Node 1.2   | 1,6         |
+------------+-------------+

একটি ব্যবহারকারী আজ একটি সম্পাদনা প্রস্তাব। তাই মডারেটর সম্পাদনা অনুমোদন, কিন্তু আমি এটা বিপরীত করছি।

সম্পাদনাটি প্রস্তাব করেছে যে উপরের শেষ প্রশ্নের মধ্যে ORDER BY b.path_length, f.name হওয়া উচিত, সম্ভবত অনুক্রমটি অনুক্রমের সাথে মেলে কিনা তা নিশ্চিত করার জন্য। কিন্তু এটি কাজ করে না, কারণ এটি "নোড 1.1.1" এর পরে "নোড 1.1.1" অর্ডার করবে।

যদি আপনি অনুজ্ঞাসূচকভাবে আধিপত্যের সাথে মেলানোর ক্রমটি চান তবে এটি সম্ভব, তবে কেবলমাত্র পথের দৈর্ঘ্য অনুসারে ক্রমানুসারে। উদাহরণস্বরূপ, মাইএসকিউএল ক্লোজার টেবিল হায়ারার্কিকাল ডেটাবেসে আমার উত্তরটি দেখুন - সঠিক ক্রমে তথ্যটি কীভাবে টানতে হয়


এটি দ্রুত লেখা হয়েছিল এবং এটি খুব সুন্দর বা দক্ষ ছিল না (প্লাস এটি খুব স্বতঃস্ফূর্ত, int এবং Integer মধ্যে রূপান্তর করা বিরক্তিকর!), তবে এটি কাজ করে।

এটি সম্ভবত আমার নিজস্ব অবজেক্ট তৈরি করার কারণে নিয়মগুলি ভেঙ্গে দেয় তবে হেই আমি বাস্তব কাজ থেকে একটি বিচ্ছিন্নতা হিসাবে এটি করছি :)

এটিও অনুমান করে যে ফলাফলগুলি / টেবিলটি কোনও ধরণের কাঠামোর মধ্যে সম্পূর্ণরূপে পড়তে পারে, যা আপনি নোড নির্মাণ শুরু করার আগে, যা আপনার লক্ষ লক্ষ সারি থাকলে সর্বোত্তম সমাধান হবে না।

public class Node {

    private Node parent = null;

    private List<Node> children;

    private String name;

    private int id = -1;

    public Node(Node parent, int id, String name) {
        this.parent = parent;
        this.children = new ArrayList<Node>();
        this.name = name;
        this.id = id;
    }

    public int getId() {
        return this.id;
    }

    public String getName() {
        return this.name;
    }

    public void addChild(Node child) {
        children.add(child);
    }

    public List<Node> getChildren() {
        return children;
    }

    public boolean isRoot() {
        return (this.parent == null);
    }

    @Override
    public String toString() {
        return "id=" + id + ", name=" + name + ", parent=" + parent;
    }
}

public class NodeBuilder {

    public static Node build(List<Map<String, String>> input) {

        // maps id of a node to it's Node object
        Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();

        // maps id of a node to the id of it's parent
        Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();

        // create special 'root' Node with id=0
        Node root = new Node(null, 0, "root");
        nodeMap.put(root.getId(), root);

        // iterate thru the input
        for (Map<String, String> map : input) {

            // expect each Map to have keys for "id", "name", "parent" ... a
            // real implementation would read from a SQL object or resultset
            int id = Integer.parseInt(map.get("id"));
            String name = map.get("name");
            int parent = Integer.parseInt(map.get("parent"));

            Node node = new Node(null, id, name);
            nodeMap.put(id, node);

            childParentMap.put(id, parent);
        }

        // now that each Node is created, setup the child-parent relationships
        for (Map.Entry<Integer, Integer> entry : childParentMap.entrySet()) {
            int nodeId = entry.getKey();
            int parentId = entry.getValue();

            Node child = nodeMap.get(nodeId);
            Node parent = nodeMap.get(parentId);
            parent.addChild(child);
        }

        return root;
    }
}

public class NodePrinter {

    static void printRootNode(Node root) {
        printNodes(root, 0);
    }

    static void printNodes(Node node, int indentLevel) {

        printNode(node, indentLevel);
        // recurse
        for (Node child : node.getChildren()) {
            printNodes(child, indentLevel + 1);
        }
    }

    static void printNode(Node node, int indentLevel) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < indentLevel; i++) {
            sb.append("\t");
        }
        sb.append(node);

        System.out.println(sb.toString());
    }

    public static void main(String[] args) {

        // setup dummy data
        List<Map<String, String>> resultSet = new ArrayList<Map<String, String>>();
        resultSet.add(newMap("1", "Node 1", "0"));
        resultSet.add(newMap("2", "Node 1.1", "1"));
        resultSet.add(newMap("3", "Node 2", "0"));
        resultSet.add(newMap("4", "Node 1.1.1", "2"));
        resultSet.add(newMap("5", "Node 2.1", "3"));
        resultSet.add(newMap("6", "Node 1.2", "1"));

        Node root = NodeBuilder.build(resultSet);
        printRootNode(root);

    }

    //convenience method for creating our dummy data
    private static Map<String, String> newMap(String id, String name, String parentId) {
        Map<String, String> row = new HashMap<String, String>();
        row.put("id", id);
        row.put("name", name);
        row.put("parent", parentId);
        return row;
    }
}

এসকিউএল সূচকগুলির অভ্যন্তরীণ বিটিআর উপস্থাপনাটি শোষণ করে এমন অনেক ভাল সমাধান রয়েছে। এই 1998 এর কাছাকাছি ফিরে কিছু মহান গবেষণা উপর ভিত্তি করে।

এখানে একটি উদাহরণ টেবিল (MySQL মধ্যে)।

CREATE TABLE `node` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `tw` int(10) unsigned NOT NULL,
  `pa` int(10) unsigned DEFAULT NULL,
  `sz` int(10) unsigned DEFAULT NULL,
  `nc` int(11) GENERATED ALWAYS AS (tw+sz) STORED,
  PRIMARY KEY (`id`),
  KEY `node_tw_index` (`tw`),
  KEY `node_pa_index` (`pa`),
  KEY `node_nc_index` (`nc`),
  CONSTRAINT `node_pa_fk` FOREIGN KEY (`pa`) REFERENCES `node` (`tw`) ON DELETE CASCADE
)

গাছ প্রতিনিধিত্বের জন্য প্রয়োজনীয় শুধুমাত্র ক্ষেত্র আছে:

  • tw: বাম থেকে ডানে ডাইফেস প্রি-অর্ডার সূচক, যেখানে root = 1।
  • পী: রেফারেন্স (দুইটি ব্যবহার করে) প্যারেন্ট নোডের জন্য, রুটটি নিল।
  • sz: নিজেকে সহ নোড এর শাখা আকার।
  • এনসি: সিনট্যাক্টিক চিনি হিসাবে ব্যবহার করা হয়। এটি tw + nc এবং নোডের "পরবর্তী সন্তানের" টিকে প্রতিনিধিত্ব করে।

এখানে একটি উদাহরণ 24 নোড জনসংখ্যা, দুই দ্বারা আদেশ:

+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|   2 | A       |  2 |    1 |   14 |   16 |
|   3 | AA      |  3 |    2 |    1 |    4 |
|   4 | AB      |  4 |    2 |    7 |   11 |
|   5 | ABA     |  5 |    4 |    1 |    6 |
|   6 | ABB     |  6 |    4 |    3 |    9 |
|   7 | ABBA    |  7 |    6 |    1 |    8 |
|   8 | ABBB    |  8 |    6 |    1 |    9 |
|   9 | ABC     |  9 |    4 |    2 |   11 |
|  10 | ABCD    | 10 |    9 |    1 |   11 |
|  11 | AC      | 11 |    2 |    4 |   15 |
|  12 | ACA     | 12 |   11 |    2 |   14 |
|  13 | ACAA    | 13 |   12 |    1 |   14 |
|  14 | ACB     | 14 |   11 |    1 |   15 |
|  15 | AD      | 15 |    2 |    1 |   16 |
|  16 | B       | 16 |    1 |    1 |   17 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
|  18 | D       | 23 |    1 |    1 |   24 |
|  19 | E       | 24 |    1 |    1 |   25 |
+-----+---------+----+------+------+------+

প্রতিটি গাছ ফলাফল অ recursively করা যেতে পারে। উদাহরণস্বরূপ, নোডের পূর্বপুরুষদের একটি তালিকা পেতে = = 22 '

পূর্বপুরুষ

select anc.* from node me,node anc 
where me.tw=22 and anc.nc >= me.tw and anc.tw <= me.tw 
order by anc.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

ভাইবোন এবং শিশুদের তুচ্ছ - শুধু দু দ্বারা দ্বি ক্ষেত্র ক্রম ব্যবহার।

উত্তরপুরূষ

উদাহরণস্বরূপ tw = 17 এ rooted নোডের সেট (শাখা)।

select des.* from node me,node des 
where me.tw=17 and des.tw < me.nc and des.tw >= me.tw 
order by des.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

অতিরিক্ত নোট

সন্নিবেশ বা আপডেট আছে তুলনায় অনেক বেশী সংখ্যক পাঠ্য আছে যখন এই পদ্ধতি অত্যন্ত দরকারী।

কারণ গাছের নোডের সন্নিবেশ, আন্দোলন, বা আপডেট করার জন্য গাছটিকে সামঞ্জস্য করা দরকার, কর্মের সাথে শুরু করার আগে টেবিলটি লক করা প্রয়োজন।

সন্নিবেশ / মোছা খরচ উচ্চ কারণ সন্নিবেশ বিন্দু, এবং সমস্ত পূর্বপুরুষদের জন্য যথাক্রমে বিন্দু সূচক এবং sz (শাখা আকার) মানগুলি সমস্ত নোডগুলিতে আপডেট করতে হবে।

শাখার চলমান শাখাটির বাইরে শাখাটির দ্বিগুণ মান সঞ্চার করে, তাই শাখাটি সরানোর সময় বিদেশি কী সীমাবদ্ধতা নিষ্ক্রিয় করাও প্রয়োজন। একটি শাখা সরানোর জন্য প্রয়োজনীয় চারটি প্রশ্ন রয়েছে:

  • শাখা বাইরে শাখা সরান।
  • এটা বাকি যে ফাঁক বন্ধ করুন। (অবশিষ্ট গাছ এখন স্বাভাবিক করা হয়)।
  • এটা যেখানে যেতে হবে ফাঁক খুলুন।
  • তার নতুন অবস্থান মধ্যে শাখা সরান।

গাছ ক্যোয়ারী সামঞ্জস্য করুন

গাছের ফাঁক খোলার / বন্ধ করা একটি গুরুত্বপূর্ণ উপ-ফাংশন যা তৈরি / আপডেট / মুছে ফেলার পদ্ধতি ব্যবহার করে, তাই আমি এখানে এটি অন্তর্ভুক্ত করি।

আমাদের দুটি পরামিতি দরকার - একটি পতাকা যা আমরা ডাউনসাইজিং বা আপ্সাইজিং করছি না এবং নোডের টুই সূচক। সুতরাং, উদাহরণস্বরূপ TW = 18 (যা একটি শাখা আকার 5)। আসুন আমরা অনুমান করি যে আমরা ডাউনসাইজিং করছি (দুইটি সরিয়ে ফেলছি) - এর অর্থ হল আমরা নিম্নলিখিত উদাহরণের আপডেটগুলিতে '+' এর পরিবর্তে '-' ব্যবহার করছি।

আমরা প্রথমে sz মান আপডেট করতে একটি (সামান্য পরিবর্তিত) পূর্বপুরুষ ফাংশন ব্যবহার করি।

update node me, node anc set anc.sz = anc.sz - me.sz from 
node me, node anc where me.tw=18 
and ((anc.nc >= me.tw and anc.tw < me.pa) or (anc.tw=me.pa));

তারপরে আমাদের দুইজনকে শাখা থেকে সরিয়ে দেওয়ার জন্য দুজনের চেয়ে বেশি সমন্বয় করা দরকার।

update node me, node anc set anc.tw = anc.tw - me.sz from 
node me, node anc where me.tw=18 and anc.tw >= me.tw;

তারপরে আমরা তাদের পিতামাতার সমন্বয় সাধন করতে হবে যাদের শাখা থেকে সরিয়ে নেওয়া শাখার চেয়ে বেশি।

update node me, node anc set anc.pa = anc.pa - me.sz from 
node me, node anc where me.tw=18 and anc.pa >= me.tw;

বিল এর উত্তরটি বেশ সুন্দর এবং সুন্দর, এই উত্তরটি কিছু জিনিস যোগ করে যা আমার ইচ্ছা করে তাই থ্রেড হওয়া উত্তরের সমর্থিত।

যাইহোক আমি গাছ কাঠামো এবং অর্ডার সম্পত্তি সমর্থন করতে চেয়েছিলেন। আমি প্রতিটি নোডের মধ্যে একটি একক সম্পত্তি অন্তর্ভুক্ত leftSibling যা leftSibling নামে পরিচিত, একই জিনিসটি Order মূল প্রশ্নে করতে হয় (বাম থেকে ডানে বজায় রাখা)।

mysql> desc nodes ;
+-------------+--------------+------+-----+---------+----------------+
| Field       | Type         | Null | Key | Default | Extra          |
+-------------+--------------+------+-----+---------+----------------+
| id          | int(11)      | NO   | PRI | NULL    | auto_increment |
| name        | varchar(255) | YES  |     | NULL    |                |
| leftSibling | int(11)      | NO   |     | 0       |                |
+-------------+--------------+------+-----+---------+----------------+
3 rows in set (0.00 sec)

mysql> desc adjacencies;
+------------+---------+------+-----+---------+----------------+
| Field      | Type    | Null | Key | Default | Extra          |
+------------+---------+------+-----+---------+----------------+
| relationId | int(11) | NO   | PRI | NULL    | auto_increment |
| parent     | int(11) | NO   |     | NULL    |                |
| child      | int(11) | NO   |     | NULL    |                |
| pathLen    | int(11) | NO   |     | NULL    |                |
+------------+---------+------+-----+---------+----------------+
4 rows in set (0.00 sec)

আমার ব্লগে আরো বিস্তারিত এবং এসকিউএল কোড

ধন্যবাদ বিল আপনার উত্তর শুরু করার জন্য সহায়ক ছিল!


বিল এর এসকিউএল সমাধান প্রসারিত করতে আপনি মূলত একটি সমতল অ্যারে ব্যবহার করে একই কাজ করতে পারেন। আরো যদি আপনার স্ট্রিংগুলির সকলের একই দৈর্ঘ্য থাকে এবং আপনার সর্বাধিক সংখ্যক শিশু পরিচিত হয় (বাইনারি গাছের মধ্যে বলুন) আপনি এটি একটি স্ট্রিং (চরিত্র অ্যারে) ব্যবহার করে এটি করতে পারেন। আপনার যদি নির্বিচারে বাচ্চাদের সংখ্যা থাকে তবে এটি কিছুটা জটিল করে তোলে ... কী করা যেতে পারে তা দেখতে আমার পুরানো নোটগুলি যাচাই করতে হবে।

তারপরে, কিছুক্ষন মেমরি উত্সর্গ করুন, বিশেষ করে যদি আপনার গাছটি অস্পষ্ট এবং / অথবা অবাঞ্ছিত হয়, তবে আপনি সূচী গণিতের একটি বিট সহ, আপনার গাছটি সংরক্ষণ করে এলোমেলোভাবে সমস্ত স্ট্রিং অ্যাক্সেস করতে পারেন, তাই অ্যারেতে প্রথম প্রস্থটি (যেমন বাইনারি গাছ):

String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...

আপনি আপনার স্ট্রিং দৈর্ঘ্য জানেন, আপনি এটা জানেন

আমি এখন কাজ করছি তাই এটিতে বেশি সময় ব্যয় করতে পারছি না তবে আগ্রহের সাথে আমি এটি করার জন্য কিছুটা কোড আনতে পারি।

আমরা এটি ডিএনএ কোডনগুলির তৈরি বাইনারি গাছগুলিতে অনুসন্ধান করার জন্য ব্যবহার করি, একটি প্রক্রিয়াটি গাছটি তৈরি করে, তারপর আমরা এটি পাঠ্য নিদর্শনগুলি সন্ধান করতে এবং এটি যখন পাওয়া যায়, যদিও সূচক গণিত (উপরে থেকে বিপরীত) আমরা নোড ফিরে পেতে পারি ... খুব দ্রুত এবং দক্ষ, কঠিন আমাদের গাছ খুব কমই নোড ছিল, কিন্তু আমরা একটি জাফি মধ্যে তথ্য গিগাবাইট অনুসন্ধান করতে পারে।


যদি উপাদানগুলি গাছের ক্রমের মধ্যে থাকে, যেমন আপনার উদাহরণে দেখানো হয়েছে, আপনি নিম্নলিখিত পাইথন উদাহরণের মতো কিছু ব্যবহার করতে পারেন:

delimiter = '.'
stack = []
for item in items:
  while stack and not item.startswith(stack[-1]+delimiter):
    print "</div>"
    stack.pop()
  print "<div>"
  print item
  stack.append(item)

এই কি গাছের বর্তমান অবস্থান প্রতিনিধিত্ব একটি স্ট্যাক বজায় রাখা হয়। টেবিলে প্রতিটি উপাদানটির জন্য, এটি স্ট্যাক উপাদানগুলি (মিলিং ডিভস বন্ধ করা) পপ না হওয়া পর্যন্ত এটি বর্তমান আইটেমটির পিতা-মাতা খুঁজে পায়। তারপর এটি সেই নোডের আউটপুট আউটপুট করে এবং স্ট্যাকে এটি push করে।

আপনি নেস্টেড উপাদানের পরিবর্তে ইন্ডেন্টিং ব্যবহার করে গাছটি আউটপুট করতে চান তবে আপনি ডিভিগুলি মুদ্রণ করতে মুদ্রণ বিবৃতিগুলি কেবল বাদ দিতে পারেন এবং প্রতিটি আইটেমের আগে স্ট্যাকের আকারের কয়েকটি সমান সমান সংখ্যক স্পেস মুদ্রণ করতে পারেন। উদাহরণস্বরূপ, পাইথন ইন:

print "  " * len(stack)

আপনি নেস্টেড তালিকা বা অভিধানগুলির একটি সেট নির্মাণ করতে এই পদ্ধতিটি সহজেই ব্যবহার করতে পারেন।

সম্পাদনা: আমি আপনার স্প্ল্যাফিকেশন থেকে দেখি যে নামটি নোড পাথের উদ্দেশ্যে নয়। যে একটি বিকল্প পদ্ধতির প্রস্তাব করে:

idx = {}
idx[0] = []
for node in results:
  child_list = []
  idx[node.Id] = child_list
  idx[node.ParentId].append((node, child_list))

এটি tuples (!) এর অ্যারের একটি গাছ constructs। idx [0] গাছের মূল (গুলি) প্রতিনিধিত্ব করে। একটি অ্যারে প্রতিটি উপাদান নোড নিজেই এবং তার সব শিশুদের একটি তালিকা গঠিত 2-টুপি। একবার তৈরি হয়ে গেলে, আপনি idx [0] এ ধরে রাখতে এবং idx বাতিল করতে পারবেন না, যতক্ষণ না আপনি তাদের আইডি দ্বারা নোড অ্যাক্সেস করতে চান।


No4j ব্যবহার করে nosql সরঞ্জামগুলি ব্যবহার সম্পর্কে চিন্তা করুন। উদাহরণস্বরূপ লিঙ্কযুক্তিনের মতো নেটওয়ার্কযুক্ত অ্যাপ্লিকেশনটি কোচবেসে ব্যবহার করে (অন্য নোকাল সমাধান)

কিন্তু তথ্য-মার্চের স্তরের প্রশ্নের জন্য শুধুমাত্র নস্কল ব্যবহার করুন এবং লেনদেনগুলি সংরক্ষণ / সংরক্ষণ করবেন না





hierarchical-data