پردازش پرس‌وجو بر روی پایگاه‌های داده‌ی ناقص ۲۰۲۲
Query Processing over Incomplete Databases 2022

داده‌های ناقص بخشی از زندگی و تقریباً تمام حوزه‌های مطالعات علمی هستند. کاربران هنگام پر کردن فرم‌های آنلاین تمایل دارند از برخی فیلدها بگذرند؛ شرکت‌کنندگان ترجیح می‌دهند سؤالات حساس در نظرسنجی‌ها را نادیده بگیرند؛ حسگرها از کار می‌افتند و منجر به از دست رفتن برخی قرائت‌ها می‌شوند؛ سرویس‌های نقشه‌برداری ماهواره‌ای قابل مشاهده عموم، در بسیاری از برنامه‌های کاربردی موبایل، داده‌های گمشده دارند؛ و در برنامه‌های کاربردی حفظ حریم خصوصی، داده‌ها به طور عمدی ناقص هستند تا حساسیت برخی از مقادیر ویژگی‌ها حفظ شود.

پردازش پرس‌وجو یک مسئله اساسی در علوم کامپیوتر است و در انواع برنامه‌های کاربردی مفید است. در این کتاب، ما عمدتاً بر روی پردازش پرس‌وجو بر روی پایگاه‌های داده ناقص تمرکز می‌کنیم، که شامل یافتن مجموعه‌ای از اشیاء واجد شرایط از یک مجموعه داده ناقص مشخص شده به منظور پشتیبانی از طیف گسترده‌ای از برنامه‌های کاربردی دنیای واقعی است. ابتدا به تشریح سه نوع کلی از روش‌های مدیریت داده‌های ناقص می‌پردازیم، شامل (i) دور انداختن داده‌ها با مقادیر از دست رفته، (ii) جایگزینی مقادیر از دست رفته، و (iii) فقط تکیه بر مقادیر داده‌های مشاهده شده. برای نوع سوم، معناشناسی جستجوی k نزدیک‌ترین همسایه (kNN)، پرس‌وجوی Skyline و پرس‌وجوی k برتر مسلط بر داده‌های ناقص را به ترتیب معرفی می‌کنیم. در رابطه با سه پرس‌وجوی نماینده بر روی داده‌های ناقص، برخی از تکنیک‌های پیشرفته برای پردازش پرس‌وجوهای داده‌های ناقص، از جمله نمایه سازی، هرس کردن و همچنین تکنیک‌های برون‌سپاری جمعی را بررسی می‌کنیم.

Incomplete data is part of life and almost all areas of scientific studies. Users tend to skip certain fields when they fill out online forms; participants choose to ignore sensitive questions on surveys; sensors fail, resulting in the loss of certain readings; publicly viewable satellite map services have missing data in many mobile applications; and in privacy-preserving applications, the data is incomplete deliberately in order to preserve the sensitivity of some attribute values.

Query processing is a fundamental problem in computer science, and is useful in a variety of applications. In this book, we mostly focus on the query processing over incomplete databases, which involves finding a set of qualified objects from a specified incomplete dataset in order to support a wide spectrum of real-life applications. We first elaborate the three general kinds of methods of handling incomplete data, including (i) discarding the data with missing values, (ii) imputation for the missing values, and (iii) just depending on the observed data values. For the third method type, we introduce the semantics of k-nearest neighbor (kNN) search, skyline query, and top-k dominating query on incomplete data, respectively. In terms of the three representative queries over incomplete data, we investigate some advanced techniques to process incomplete data queries, including indexing, pruning as well as crowdsourcing techniques.