Việc tìm kiếm các phụ thuộc chức năng trong dữ liệu được sử dụng trong các lĩnh vực phân tích dữ liệu khác nhau: quản lý cơ sở dữ liệu, làm sạch dữ liệu, kỹ thuật đảo ngược cơ sở dữ liệu và khám phá dữ liệu. Chúng tôi đã xuất bản về các phần phụ thuộc Anastasia Birillo và Nikita Bobrov. Lần này, Anastasia, sinh viên tốt nghiệp Trung tâm Khoa học Máy tính năm nay, chia sẻ quá trình phát triển công trình này như một phần của công trình nghiên cứu mà cô bảo vệ tại trung tâm.
lựa chọn nhiệm vụ
Khi học tại trung tâm CS, tôi bắt đầu nghiên cứu chuyên sâu về cơ sở dữ liệu, cụ thể là tìm kiếm các phụ thuộc chức năng và sự khác biệt. Chủ đề này liên quan đến chủ đề khóa học của tôi ở trường đại học, vì vậy trong khi thực hiện khóa học, tôi bắt đầu đọc các bài viết về các phần phụ thuộc khác nhau trong cơ sở dữ liệu. Tôi đã viết bài đánh giá về khu vực này - một trong những bài đánh giá đầu tiên của tôi bằng tiếng Anh và gửi tới hội nghị SEIM-2017. Tôi rất vui khi biết cuối cùng cô ấy cũng được nhận và quyết định tìm hiểu sâu hơn về chủ đề này. Bản thân khái niệm này không phải là mới - nó bắt đầu được sử dụng từ những năm 90, nhưng ngay cả bây giờ nó vẫn được sử dụng trong nhiều lĩnh vực.
Trong học kỳ thứ hai tại trung tâm, tôi bắt đầu một dự án nghiên cứu nhằm cải thiện các thuật toán tìm kiếm sự phụ thuộc chức năng. Cô đã nghiên cứu nó cùng với sinh viên tốt nghiệp Đại học bang St. Petersburg Nikita Bobrov tại JetBrains Research.
Độ phức tạp tính toán của việc tìm kiếm các phụ thuộc chức năng
Vấn đề chính là độ phức tạp tính toán. Số lượng phụ thuộc tối thiểu và không tầm thường có thể bị giới hạn ở trên bởi giá trị Đâu - số lượng thuộc tính của bảng. Thời gian hoạt động của thuật toán không chỉ phụ thuộc vào số lượng thuộc tính mà còn phụ thuộc vào số hàng. Vào những năm 90, thuật toán tìm kiếm luật liên bang trên máy tính để bàn thông thường có thể xử lý các tập dữ liệu chứa tối đa 20 thuộc tính và hàng chục nghìn hàng trong tối đa vài giờ. Các thuật toán hiện đại chạy trên bộ xử lý đa lõi phát hiện sự phụ thuộc của các tập dữ liệu bao gồm hàng trăm thuộc tính (tối đa 200) và hàng trăm nghìn hàng trong khoảng thời gian gần như nhau. Tuy nhiên, điều này vẫn chưa đủ: thời gian như vậy là không thể chấp nhận được đối với hầu hết các ứng dụng trong thế giới thực. Do đó, chúng tôi đã phát triển các phương pháp để tăng tốc các thuật toán hiện có.
Sơ đồ bộ nhớ đệm cho các giao điểm phân vùng
Trong phần đầu tiên của công việc, chúng tôi đã phát triển các sơ đồ bộ đệm cho một lớp thuật toán sử dụng phương pháp giao phân vùng. Phân vùng cho một thuộc tính là một tập hợp các danh sách, trong đó mỗi danh sách chứa các số dòng có cùng giá trị cho một thuộc tính nhất định. Mỗi danh sách như vậy được gọi là một cụm. Nhiều thuật toán hiện đại sử dụng phân vùng để xác định xem một phụ thuộc có được giữ hay không, cụ thể là chúng tuân theo bổ đề: Phụ thuộc giữ nếu . Đây một phân vùng được chỉ định và khái niệm về kích thước phân vùng được sử dụng - số lượng cụm trong đó. Các thuật toán sử dụng phân vùng, khi vi phạm phần phụ thuộc, hãy thêm các thuộc tính bổ sung vào phía bên trái của phần phụ thuộc, sau đó tính toán lại, thực hiện thao tác giao nhau của các phân vùng. Hoạt động này được gọi là chuyên môn hóa trong các bài viết. Nhưng chúng tôi nhận thấy rằng các phân vùng dành cho phần phụ thuộc chỉ được giữ lại sau một vài vòng chuyên môn hóa có thể được tái sử dụng một cách tích cực, điều này có thể giảm đáng kể thời gian chạy của thuật toán do hoạt động giao cắt rất tốn kém.
Do đó, chúng tôi đã đề xuất một phương pháp phỏng đoán dựa trên Shannon Entropy và Ginny Uncertainty, cũng như số liệu của chúng tôi mà chúng tôi gọi là Entropy ngược. Đây là một sửa đổi nhỏ của Shannon Entropy và tăng lên khi tính duy nhất của tập dữ liệu tăng lên. Heuristic được đề xuất như sau:
Здесь - mức độ duy nhất của phân vùng được tính toán gần đây Và là trung vị của mức độ duy nhất của các thuộc tính riêng lẻ. Tất cả ba số liệu được mô tả ở trên đều được thử nghiệm dưới dạng số liệu duy nhất. Bạn cũng có thể nhận thấy rằng có hai công cụ sửa đổi trong heuristic. Đầu tiên cho biết mức độ gần của phân vùng hiện tại với khóa chính và cho phép bạn lưu vào bộ nhớ đệm ở mức độ lớn hơn những phân vùng nằm xa khóa tiềm năng. Công cụ sửa đổi thứ hai cho phép bạn giám sát việc chiếm dụng bộ đệm và do đó khuyến khích thêm nhiều phân vùng hơn vào bộ đệm nếu có dung lượng trống. Giải pháp thành công cho vấn đề này cho phép chúng tôi tăng tốc thuật toán PYRO lên 10-40%, tùy thuộc vào tập dữ liệu. Điều đáng chú ý là thuật toán PYRO thành công nhất trong lĩnh vực này.
Trong hình bên dưới, bạn có thể thấy kết quả của việc áp dụng phương pháp phỏng đoán được đề xuất so với phương pháp lưu vào bộ nhớ đệm lật đồng xu cơ bản. Trục X là logarit.
Một cách khác để lưu trữ phân vùng
Sau đó chúng tôi đề xuất một cách khác để lưu trữ các phân vùng. Các phân vùng là một tập hợp các cụm, mỗi cụm lưu trữ số lượng bộ dữ liệu có giá trị giống nhau cho các thuộc tính nhất định. Các cụm này có thể chứa các chuỗi số dài, chẳng hạn như nếu dữ liệu trong bảng được sắp xếp theo thứ tự. Do đó, chúng tôi đã đề xuất một sơ đồ nén để lưu trữ các phân vùng, cụ thể là lưu trữ theo khoảng thời gian các giá trị trong các cụm phân vùng:
$$display$$pi(X) = {{Nâng dưới{1, 2, 3, 4, 5__{Khoảng cách đầu tiên}, nẹp dưới{7, 8__{Khoảng cách thứ hai}, 10}}\ downarrow{ Nén} \ pi(X) = {{Nâng dưới{$, 1, 5__{Khoảng cách đầu tiên}, nẹp dưới{7, 8__{Khoảng cách thứ hai~}, 10}}$$display$$
Phương pháp này có thể giảm mức tiêu thụ bộ nhớ trong quá trình vận hành thuật toán TANE từ 1 xuống 25%. Thuật toán TANE là một thuật toán cổ điển để tìm kiếm luật liên bang; nó sử dụng các phân vùng trong quá trình làm việc. Là một phần của quá trình thực hành, thuật toán TANE đã được chọn vì việc triển khai lưu trữ theo khoảng thời gian trong đó dễ dàng hơn nhiều so với, chẳng hạn như trong PYRO, để đánh giá xem phương pháp đề xuất có hoạt động hay không. Kết quả thu được được trình bày ở hình dưới đây. Trục X là logarit.
Hội nghị ADBIS-2019
Dựa trên kết quả nghiên cứu, vào tháng 2019 năm XNUMX tôi đã xuất bản một bài báo tại Hội nghị Châu Âu lần thứ 23 về Những tiến bộ trong Cơ sở dữ liệu và Hệ thống Thông tin (ADBIS-2019). Trong buổi thuyết trình, công trình đã được ghi nhận bởi Bernhard Thalheim, một người có vai trò quan trọng trong lĩnh vực cơ sở dữ liệu. Các kết quả nghiên cứu đã tạo cơ sở cho luận án thạc sĩ toán học và cơ học của tôi tại Đại học bang St. Petersburg, trong đó cả hai phương pháp đề xuất (bộ nhớ đệm và nén) đều được triển khai trong cả hai thuật toán: TANE và PYRO. Hơn nữa, kết quả cho thấy các phương pháp được đề xuất là phổ biến, vì trên cả hai thuật toán, với cả hai phương pháp, người ta thấy mức tiêu thụ bộ nhớ giảm đáng kể cũng như thời gian hoạt động của thuật toán giảm đáng kể.
Nguồn: www.habr.com