Một trong những bài toán mà tôi đang theo đuổi đó là bài toán "incremental view-update" - tạm dịch là "cập nhật tăng dần". Đây là một trong những bài toán kinh điển, vốn đã được cộng đồng nghiên cứu cơ sở dữ liệu theo đuổi từ lâu. Tuy nhiên với hướng tiếp cận cho chuyển đổi hai chiều (bidirectional transformations - Bx) thì bài toán này thoả mãn 3 tiêu chí cơ bản trong việc lựa chọn bài toán nghiên cứu: một là bài toán thú vị (interesting problem) do bài toán phổ biến từ lâu nhưng được nhìn lại ở khía cạnh chuyển đổi song phương (Bx); hai là đủ khó (difficult problem): trước nay chưa ai nghiên cứu giải quyết bài toán này cho Bx; và ba là hữu dụng (useful problem): có khả năng giải quyết được rất nhiều bài toán thực tế liên quan đến Incremental view-update trong Bx.
Chuyển đổi hai chiều hiện diện ở rất nhiều trong lĩnh vực công nghệ phần mềm. Sau đây tôi sẽ đưa ra nhiều ví dụ khác nhau để làm rõ thêm về việc ứng dụng chuyển đổi hai chiều trong đó.
Ví dụ như đồng bộ bookmarks ở các trình duyệt khác nhau, hoặc trên nhiều máy tính/thiết bị khác nhau. Khi các bạn xài nhiều máy tính khác nhau, trang web mà bạn đánh dấu trên máy tính này sẽ được tự động đồng bộ với bookmarks của bạn ở các máy tính khác khi bạn bật nó lên. Ví dụ này nhìn bên ngoài tuy đơn giản nhưng làm thế nào để thực hiện việc đồng bộ một cách tự động và chính xác thì lại là một việc không dễ dàng.
Một ví dụ khác là trong quy trình phát triển phần mềm, chúng ta có các bước khác nhau trong quá trình phát triển một phần mềm như lấy yêu cầu, phân tích, thiết kế, cài đặt, kiểm thử và đóng gói cho khác hàng. Nếu thay đổi xảy ra ở một bước nào đó ví dụ như thiết kế, yêu cầu đặt ra là làm sao để thay đổi đó có thể tự động được đồng bộ đến cá bước trước đó (như lấy yêu cầu, phân tích) hay sau đó (như cài đặt, kiểm thử và đóng gói).
Big Picture:
Có nhiều hướng tiếp cận BXs khác nhau, trong đó lens là một cách tiếp cận hướng ngôn ngữ. Lens là một chuyển đổi hai chiều giữa cặp dữ liệu, trong đó những thay đổi dữ liệu của bất kỳ bên nào, sẽ được cập nhật vào vị trí thích hợp cho bên còn lại. Phát biểu một cách nôm na thì Lens là chương trình biến đổi hai chiều (BX program) với 2 hàm get (forward) để biến đổi dữ liệu nguồn sang đích và put (backward) để biến đổi từ dữ liệu đích sang nguồn. Để đảm bảo tính đúng đắn và trong chuyển đổi hai chiều trên lens thì get & put phải thoả mãn hai thuộc tính gọi là well-behavedness properties như sau: (1) GetPut: đảm bảo nếu target không bị thay đổi thì source cũng không bị thay đổi & (2) PutGet: thay đổi trên target phải được cập nhật lên source chính xác.
Hiệu năng trong BXs là một vấn đề rất đáng được quan tâm. Với khối lượng dữ liệu lớn (Big data), thì việc chuyển đổi ở chiều ngược lại (putback hoặc backward transformation) đóng vai trò rất quan trọng. Đưa thêm ví dụ cụ thể để minh hoạ.
Ví dụ với dữ liệu nguồn lớn (source) thì chiều get (forward) chúng ta sẽ thu được những thông tin rút gọn cần thiết ở đích (target). Tuy nhiên khi thực hiện cập nhật ở đích (target) và thể hiện những thay đổi này về nguồn (source) thì putback yêu cầu phải có dữ liệu nguồn ban đầu (original source) để thực hiện việc cập nhật. Trong ngữ cảnh đó việc cập nhật sẽ không hiệu quả vì phải tính toán lại trên toàn bộ dữ liệu nguồn ban đầu (original source) kết hợp với dữ liệu đích mới (modified target). Khi này vấn đề đặt ra là làm thế nào để tăng hiệu năng của phép chuyển đổi hai chiều trong lens và vẫn đảm bảo được qui tắc well-behavedness của lens.
Bài toán đặt ra ở đây là làm thế nào để thực hiện phép biến đổi get/put hiệu quả hơn khi có những thay đổi nhỏ ở nguồn hoặc đích. Thay vì tính toán lại toàn bộ, làm thế nào để tái sử dụng lại nhiều nhất các phép tính toán đã thực hiện và chỉ phải tính lại đúng những phần bị thay đổi mà thôi. Bài toán thuộc dạng này được gọi là Incremental updates - đây là bài toán được nghiên cứu từ lâu trong cộng đồng nghiên
Phương pháp:
Yêu cầu đặt ra của bài toán là làm thế nào để tăng hiệu năng của lens khi thực hiện biến đổi 2 chiều. Cụ thể hơn là với những thay đổi nhỏ ở nguồn (source) hoặc đích (target), ta có thể tái sử dụng lại các phép tính toán và kết quả đã thực hiện trước đó mà không cần thiết phải tính lại toàn bộ.
Có nhiều phương pháp khác nhau để giải quyết bài toán Incremental update trong BXs như là
(1) tính toán lại toàn bộ mà không tái sử dụng bất kỳ phép tính nào - cách này kém hiệu quả,
(2) thiết kế riêng cho từng bài toán, cụ thể trong trường hợp này là thiết kế riêng phương án tăng hiệu năng cho lens - phương pháp này hiệu quả cho từng bài toán cụ thể, nhưng không tổng quát hoá được và áp dụng một cách có hệ thống được
(3) đặc tả những thay đổi có thể xảy ra để khi nguồn hoặc đích bị thay đổi thì chỉ cần tính toán lại trên những thay đổi đó mà thôi (Edit lenses) - cách này yêu cầu nhiều ràng buộc và không thân thiện với người sử dụng
(4) Self-adjusting computation: ghi nhớ lại những phép tính đã thực hiện và khi bị thay đổi thì tái sự lại nhiều nhất các phép tính có thể - cách này có hiệu quả cao hơn hết do có thể biểu diễn mối quan hệ giữa các phép tính và dữ liệu bằng cách xây dựng đồ thi phụ thuộc động (Dynamic dependence graphs), và có thể áp dụng một cách có hệ thống cho nhiều bài toán khác nhau, và thân thiện với người dùng - người dùng không cần biết nhiều về cấu trúc bên trong, chỉ cần thay đổi một ít trong CTDL hiện có của mình và của chương trình mình viết.
Ý tưởng:
Thử nghiệm bằng cách sử dụng phương pháp để giải quyết bài toán Incremental computation trên để giải quyết vấn đề Incremental update trong BXs. Tuy nhiên việc kết hợp này cũng đặt ra nhiều vấn đề liên quan cần giải quyết như: làm thế nào để giải quyết được compositional problem?.
Ví dụ: với dữ liệu nguồn S (Source) và NHIỀU chương trình biến đổi hai chiều f (BX program) chương trình này sẽ áp dụng điều kiện p trên S để thu được V. Mô hình của compositional như sau: S <-> f <-> V1 <-> f <-> V2 <-> f <-> V3 <-> ... <-> V.
Một vấn đề khác cũng được đặt ra đó là làm thế nào để xây dựng phương pháp một cách có hệ thống thay vì một giải pháp tình thế (ad hoc way) ?
Giải pháp:
Kết hợp phương pháp self-adjusting computation với BXs, thử nghiệm bước đầu với Lenses để tăng hiệu năng. Cách tiếp cận này có các ưu điểm sau:
(1) Modularity: với các chương trình BX hiện có, việc xây dựng thành Self-adjusting BX có thể thực hiện một cách có hệ thống mà không cần thay đổi toàn bộ cấu trúc chương trình sẵn có.
(2) Efficiency: cách tiếp cận này có thể tăng hiệu năng của chương trình vì nó tái sử dụng lại các phép tính toán và kết quả đã được thực hiện trước đó một cách chính xác.
(3) Compositional: nhiều chương trình chuyển đổi hai chiều có thể được kết hợp lại với nhau, trong đó output của một chương trình này có thể trở thành input của một chương trình khác một cách dễ dàng.
(Còn tiếp).
Không có nhận xét nào:
Đăng nhận xét