پایگاه‌های داده احتمالی ۲۰۲۲
Probabilistic Databases 2022

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

این کتاب، آخرین دستاوردهای موجود در زمینه‌ی فرمالیسم‌های نمایش و تکنیک‌های پردازش پرس و جو برای داده‌های احتمالی را ارائه می‌دهد. کتاب با بحث درباره‌ی اصول اولیه‌ی نمایش پایگاه داده‌های احتمالی بزرگ، از طریق تجزیه‌ی آن‌ها به جداول مستقل-تایی، جداول مجزای مستقل-بلوکی یا پایگاه‌داده‌های U، آغاز می‌شود. سپس، به بررسی دو دسته از تکنیک‌ها برای ارزیابی پرس و جو بر روی پایگاه داده‌های احتمالی می‌پردازد.

در ارزیابی پرس و جوی گسترده، کل استنتاج احتمالی را می‌توان به موتور پایگاه داده منتقل کرد و بنابراین، به همان اندازه‌ی ارزیابی پرس و جوهای استاندارد SQL، به طور موثر پردازش کرد. پرس و جوهای رابطه‌ای که می‌توانند به این روش ارزیابی شوند، پرس و جوهای امن نامیده می‌شوند. در ارزیابی پرس و جوی درونی، استنتاج احتمالی بر روی یک فرمول گزاره‌ای به نام عبارت تبار انجام می‌شود: هر پرس و جوی رابطه‌ای را می‌توان به این روش ارزیابی کرد، اما پیچیدگی داده به طور چشمگیری به پرس و جویی که ارزیابی می‌شود، بستگی دارد و می‌تواند P-سخت باشد.

این کتاب همچنین به بحث در مورد برخی از موضوعات پیشرفته در مدیریت داده‌های احتمالی مانند پردازش پرس و جوی top-k، پایگاه داده‌های احتمالی ترتیبی، نمایه‌سازی و نماهای مادی‌شده و پایگاه داده‌های مونت کارلو می‌پردازد.

فهرست مطالب: مروری / مدل داده و پرس و جو / مسئله‌ی ارزیابی پرس و جو / ارزیابی پرس و جوی گسترده / ارزیابی پرس و جوی درونی / تکنیک‌های پیشرفته

Probabilistic databases are databases where the value of some attributes or the presence of some records are uncertain and known only with some probability. Applications in many areas such as information extraction, RFID and scientific data management, data cleaning, data integration, and financial risk assessment produce large volumes of uncertain data, which are best modeled and processed by a probabilistic database. This book presents the state of the art in representation formalisms and query processing techniques for probabilistic data. It starts by discussing the basic principles for representing large probabilistic databases, by decomposing them into tuple-independent tables, block-independent-disjoint tables, or U-databases. Then it discusses two classes of techniques for query evaluation on probabilistic databases. In extensional query evaluation, the entire probabilistic inference can be pushed into the database engine and, therefore, processed as effectively as the evaluation of standard SQL queries. The relational queries that can be evaluated this way are called safe queries. In intensional query evaluation, the probabilistic inference is performed over a propositional formula called lineage expression: every relational query can be evaluated this way, but the data complexity dramatically depends on the query being evaluated, and can be #P-hard. The book also discusses some advanced topics in probabilistic data management such as top-k query processing, sequential probabilistic databases, indexing and materialized views, and Monte Carlo databases. Table of Contents: Overview / Data and Query Model / The Query Evaluation Problem / Extensional Query Evaluation / Intensional Query Evaluation / Advanced Techniques