MỘT THUẬT TOÁN HIỆU QUẢ ĐỂ CHUYỂN ĐỔI MỘT BẢNG TÍNH CÁC HÀNG CÓ QUAN HỆ CHA-CON NGẦM ĐỊNH VÀO MỘT BẢNG CƠ SỞ DỮ LIỆU CÁC HÀNG CÓ MỐI QUAN HỆ CHA-CON RÕ RÀNG

Tóm tắt

Việc chuyển đổi dữ liệu khó sử dụng thành dữ liệu dễ sử dụng trong các ứng dụng thế giới thực là phổ biến. Bài báo này đề xuất một thuật toán hiệu quả để chuyển đổi dữ liệu từ một bảng tính đầu vào các hàng có mối quan hệ cha-con ngầm định thành một bảng cơ sở dữ liệu gồm các hàng có mối quan hệ cha-con rõ ràng và thứ tự sinh xác định. Ở đây, một hàng có mối quan hệ cha-con ngầm định không có trường tham chiếu đến hàng cha của nó, nhưng cha của nó có thể được xác định bằng cấp và thứ tự của nó. Bảng tính đầu vào khó truy vấn và liên kết với các thành phần giao diện người dùng kiểu cây để hiển thị trong các ứng dụng, trong khi bảng cơ sở dữ liệu đầu ra rất tiện lợi. Độ phức tạp thời gian của thuật toán được đề xuất là O(n), trong đó n là số hàng trong bảng tính đầu vào. Thuật toán cũng sử dụng không gian bộ nhớ hạn chế: nó sử dụng một vài biến kiểu dữ liệu cơ bản và hai danh sách số nguyên, trong đó kích thước của chúng không vượt quá số lượng các cấp khác nhau được sử dụng để gán cho các hàng của bảng tính.