Đồng bộ hóa một chiều của hai cấu trúc phân cấp

Question

Tôi hy vọng sẽ viết một thuật toán để đồng bộ hóa hai cấu trúc phân cấp. Các cấu trúc này có thể là đồ thị đối tượng, dữ liệu được lưu trữ trong các bảng cơ sở dữ liệu quan hệ, vv (thậm chí là hai cấu trúc khác nhau, miễn là chúng có khóa tương đương). Việc đồng bộ hóa sẽ là một chiều, tức là, một cấu trúc sẽ là nguyên mẫu và một cấu trúc khác sẽ được sửa đổi để khớp.

Giả sử chúng tôi có chức năng sync. Nó sẽ cần phải chấp nhận những điều sau đây:

1. objA - nguyên mẫu
2. objB - đối tượng phải được sửa đổi
3. keyA - chức năng tạo ra chìa khóa cho objA
4. keyB - chức năng tạo ra chìa khóa cho objB
5. addB - chức năng tạo objB (trả về id của objB mới)
6. setB - chức năng để cập nhật objB
7. remB - chức năng để xóa một objB
8. parB - id của mẹ objB 's - điều này sẽ được chuyển cho addB cho bối cảnh

Vì vậy, chúng tôi có này:

let sync (objA:'a) (objB:'b) (keyA:'a -> 'k) (keyB:'b -> 'k) 
     (addB:'p * 'a -> 'p) (setB:'a * 'b -> unit) (remB:'b -> unit) 
     (parB:'p) = ... 

Bây giờ, đây là nơi tôi đang gặp sự cố. 'a và 'b là phân cấp, do đó, chức năng cần phải biết thuộc tính nào của 'a và 'b nó sẽ đi qua (khi nó so sánh khóa của chúng và quyết định khớp với nhau đến nay và nên được tiếp tục đi qua). Đối với các thuộc tính "con" này, nó cần tất cả các đối số giống nhau được truyền để đồng bộ hóa, nhưng đối với các kiểu tương ứng của chúng.

Đây là khi nó trở nên rõ ràng đây là một vấn đề cấu trúc dữ liệu. Làm thế nào tôi có thể chuỗi lại với nhau thông tin này sao cho đối tượng gốc có thể được chuyển đến sync và nó có thể đi qua các đồ thị xuống? Suy nghĩ ban đầu của tôi là kết hợp tất cả các đối số vào một lớp, mà sẽ có một tài sản trẻ em (một số ResizeArray cùng loại). Nhưng với các thuộc tính khác nhau có các loại khác nhau, tôi không thể tìm ra cách để làm cho nó hoạt động, ngắn ném các loại ra ngoài cửa sổ và làm cho hầu hết hoặc tất cả các đối số kiểu obj.

Vì vậy, đây là những câu hỏi của tôi:

1. Có một phương pháp tốt được thành lập để thực hiện điều này rồi (tôi đã không thể tìm thấy bất cứ điều gì)
2. cấu trúc dữ liệu Những gì tôi có thể sử dụng để đóng gói các dữ liệu cần thiết để thực hiện công việc này?

Tôi đã cố gắng hết sức để giải thích kỹ lưỡng, nhưng nếu mọi thứ vẫn chưa rõ ràng, vui lòng hỏi và tôi sẽ cố gắng cung cấp thông tin tốt hơn.

Answer 1

Tôi chắc chắn điều này là đơn giản hóa nó nhưng đây là ý tưởng của tôi.

Nếu đây là một DAG, bạn có thể thực hiện một giao thoa đầu tiên của objA.Khi bạn enqueue một nút từ objA bao gồm objB và bất kỳ thông tin khác bạn cần (tuple). Sau đó, khi bạn dequeue bạn sửa chữa objB.

Bạn có thể sử dụng một liên minh phân biệt đối xử để xử lý các loại con khác nhau trong quá trình enqueueing của bạn.

Answer 2

Tạo diffgrams từ hai cấu trúc dữ liệu và ánh xạ biến đổi thành vấn đề được chuyển đổi.