یافتن وابستگیهای تابعی در دادهها در حوزههای مختلف تحلیل دادهها استفاده میشود: مدیریت پایگاه داده، پاکسازی دادهها، مهندسی معکوس پایگاه داده و کاوش دادهها. ما قبلاً در مورد خود وابستگیها مطالبی منتشر کردهایم. آناستازیا بیریلو و نیکیتا بوبروف. این بار، آناستازیا، فارغالتحصیل مرکز علوم کامپیوتر در سال جاری، توسعه این پروژه تحقیقاتی را که در این مرکز از آن دفاع کرده است، به اشتراک میگذارد.
انتخاب کار
هنگام تحصیل در مرکز CS، شروع به مطالعه عمیق پایگاههای داده، به ویژه یافتن وابستگیهای تابعی و تفاضلی کردم. این موضوع مربوط به دروس دانشگاه من بود، بنابراین هنگام کار روی آن، شروع به خواندن مقالاتی در مورد وابستگیهای مختلف در پایگاههای داده کردم. من یک نقد در مورد این زمینه نوشتم - یکی از اولین مطالعات من. به زبان انگلیسی نوشتم و آن را به کنفرانس SEIM-2017 ارسال کردم. وقتی پذیرفته شد، هیجانزده شدم و تصمیم گرفتم عمیقتر به این موضوع بپردازم. خود این مفهوم چیز جدیدی نیست - از دهه 90 وجود داشته است - اما هنوز هم در بسیاری از زمینهها کاربرد دارد.
در ترم دوم تحصیلم در این مرکز، یک پروژه تحقیقاتی را برای بهبود الگوریتمهای یافتن وابستگیهای تابعی آغاز کردم. من روی آن با نیکیتا بوبروف، دانشجوی کارشناسی ارشد دانشگاه ایالتی سن پترزبورگ، در JetBrains Research کار کردم.
پیچیدگی محاسباتی جستجوی وابستگیهای تابعی
مشکل اصلی پیچیدگی محاسباتی است. تعداد وابستگیهای حداقلی و غیربدیهی ممکن از بالا به صورت زیر محدود شده است: 
جایی که 
— تعداد ویژگیهای جدول. زمان اجرای الگوریتمها نه تنها به تعداد ویژگیها، بلکه به تعداد ردیفها نیز بستگی دارد. در دهه 90، الگوریتمهای تشخیص قانون فدرال روی یک رایانه رومیزی معمولی میتوانستند مجموعه دادههایی حاوی حداکثر 20 ویژگی و دهها هزار ردیف را تا چند ساعت پردازش کنند. الگوریتمهای مدرن که روی پردازندههای چند هستهای اجرا میشوند، وابستگیهای مجموعه دادههایی متشکل از صدها ویژگی (تا 200) و صدها هزار ردیف را تقریباً در همان زمان تشخیص میدهند. با این حال، این کافی نیست: چنین زمانی برای اکثر برنامههای دنیای واقعی غیرقابل قبول است. بنابراین، ما رویکردهایی را برای تسریع الگوریتمهای موجود توسعه دادیم.
طرحهای ذخیرهسازی برای تقاطع پارتیشن
در بخش اول مقاله، ما طرحهای ذخیرهسازی پنهان برای دستهای از الگوریتمها با استفاده از روش تقاطع پارتیشن توسعه دادیم. یک پارتیشن برای یک ویژگی، مجموعهای از لیستها است که در آن هر لیست شامل شماره ردیفهایی با مقادیر یکسان برای ویژگی داده شده است. به هر یک از این لیستها خوشه گفته میشود. بسیاری از الگوریتمهای مدرن از پارتیشنها برای تعیین اینکه آیا یک وابستگی برقرار است یا خیر استفاده میکنند، یعنی به لم زیر پایبند هستند: وابستگی 
حفظ میشود اگر 
اینجا 
یک پارتیشن با نشان داده میشود و از مفهوم اندازه پارتیشن - تعداد خوشههای درون آن - استفاده میشود. الگوریتمهایی که از پارتیشنها استفاده میکنند، در صورت نقض یک وابستگی، ویژگیهای اضافی را به سمت چپ وابستگی اضافه میکنند، سپس با انجام عملیات تقاطع پارتیشن، آن را دوباره محاسبه میکنند. این عملیات در مقالات به عنوان تخصصگرایی نامیده میشود. با این حال، ما اشاره کردهایم که پارتیشنهای مربوط به وابستگیهایی که تنها پس از چندین دور تخصصگرایی حفظ میشوند، میتوانند به طور فعال دوباره استفاده شوند، که میتواند زمان اجرای الگوریتمها را به میزان قابل توجهی کاهش دهد، زیرا عملیات تقاطع پرهزینه است.
بنابراین، ما یک روش ابتکاری مبتنی بر آنتروپی شانون و عدم قطعیت جینی، و همچنین معیار خودمان که آن را آنتروپی معکوس مینامیم، پیشنهاد دادیم. این معیار، اصلاح جزئی آنتروپی شانون است و با افزایش منحصر به فرد بودن مجموعه دادهها، افزایش مییابد. روش ابتکاری پیشنهادی به شرح زیر است:
اینجا 
— میزان منحصر به فرد بودن پارتیشن اخیراً محاسبه شده 
و 
میانه درجههای منحصر به فرد بودن برای ویژگیهای منفرد است. هر سه معیار شرح داده شده در بالا به عنوان معیارهای منحصر به فرد بودن آزمایش شدند. همچنین میتوان اشاره کرد که این روش اکتشافی شامل دو اصلاحکننده است. اولین مورد نشان میدهد که پارتیشن فعلی چقدر به کلید اصلی نزدیک است و امکان ذخیرهسازی بیشتر پارتیشنهای دورتر از کلید کاندید را فراهم میکند. اصلاحکننده دوم، میزان اشغال حافظه پنهان را رصد میکند و در نتیجه، در صورت وجود فضا، افزودن پارتیشنهای بیشتر به حافظه پنهان را تشویق میکند. حل موفقیتآمیز این مشکل به الگوریتم PYRO اجازه داد تا بسته به مجموعه دادهها، 10 تا 40 درصد سرعت بگیرد. شایان ذکر است که الگوریتم PYRO در این زمینه موفقترین است.
شکل زیر نتایج اعمال روش ابتکاری پیشنهادی را در مقایسه با رویکرد ذخیرهسازی پایه مبتنی بر پرتاب سکه نشان میدهد. محور x لگاریتمی است.
یک روش جایگزین برای ذخیره پارتیشنها
سپس یک روش جایگزین برای ذخیره پارتیشنها پیشنهاد دادیم. پارتیشنها مجموعهای از خوشهها هستند که هر کدام اعداد تاپل با مقادیر یکسان برای ویژگیهای خاص را ذخیره میکنند. این خوشهها میتوانند شامل توالیهای طولانی از اعداد تاپل باشند، به عنوان مثال، اگر دادههای یک جدول مرتب باشند. بنابراین، ما یک طرح فشردهسازی برای ذخیره پارتیشنها پیشنهاد کردیم، یعنی ذخیره فاصلهای مقادیر در خوشههای پارتیشن:
$$display$$pi(X) = {{underbrace{1, 2, 3, 4, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}\ downarrow{فشردهسازی}\ pi(X) = {{underbrace{$, 1, 5}_{First~interval}, underbrace{7, 8}_{Second~interval}, 10}}$$display$$
این روش توانست مصرف حافظه را در طول اجرای الگوریتم TANE بین ۱ تا ۲۵ درصد کاهش دهد. الگوریتم TANE یک الگوریتم کلاسیک برای جستجوی مناطق منطقی است؛ این الگوریتم در طول عملیات خود از پارتیشنها استفاده میکند. برای اهداف عملی، الگوریتم TANE انتخاب شد زیرا پیادهسازی ذخیرهسازی بازه به طور قابل توجهی آسانتر از، به عنوان مثال، در PYRO برای ارزیابی امکانپذیری رویکرد پیشنهادی بود. نتایج در شکل زیر ارائه شده است. محور x لگاریتمی است.
کنفرانس ADBIS-2019
بر اساس نتایج تحقیق، مقالهای را در سپتامبر ۲۰۱۹ منتشر کردم. در بیست و سومین کنفرانس اروپایی پیشرفتها در پایگاههای داده و سیستمهای اطلاعاتی (ADBIS-2019)، این کار توسط برنارد تالهایم، چهره برجسته در حوزه پایگاههای داده، مورد تقدیر قرار گرفت. نتایج این تحقیق، اساس پایاننامه من برای برنامه کارشناسی ارشد در دانشکده ریاضی و مکانیک دانشگاه ایالتی سن پترزبورگ را تشکیل داد که طی آن هر دو رویکرد پیشنهادی (ذخیرهسازی و فشردهسازی) در هر دو الگوریتم TANE و PYRO پیادهسازی شدند. نتایج نشان داد که رویکردهای پیشنهادی جهانی هستند، زیرا هر دو الگوریتم کاهش قابل توجهی در مصرف حافظه و کاهش قابل توجهی در زمان اجرا نشان دادند.
منبع: www.habr.com
