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