Probabilistic Databases

by Dan Suciu

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

179 pages, Paperback

First published July 7, 2011

Reviews

[Aleksandar Janjic · Rating 3 out of 5]

О базама података (првенствено оним релационим) већ сам писао нешто раније, а ове пробабилистичке базе података из наслова су базе код којих је сваком податку прикачена одређена вјероватноћа - што ће рећи да подаци у бази нису "сигурни". Теорија пробабилистичких база података бави се, не сасвим неочекивано, питањем какве све одговоре можемо да измуземо од овакве базе података и какву цијену то има.

Основна прича, изнесена на првих неколико страна, је једноставна, међутим чим аутори пређу на детаљније разматрање и комплексније ствари, ту настаје прави пакао. Ја сам разумио да се књига бави анализирањем цијене извршавања одређених упита, али све преко тога ми је потпуно мутно, за што ћемо наравно окривити ауторе и њихову неспособност/недостатак воље да пишу јасно и разумљиво за просјечног читаоца, а не мене зато што сам превише глуп да то разумијем.

Кад си универзитецки професор, постоје два могућа мотива за писање књиге о области којом се бавиш: 1) Хоћеш да помогнеш студентима (и осталим заинтересованим особама) да савладају градиво поменуте области и нешто науче и 2) Потребно ти је да се твоје име појави на некој књизи због избора у више звање (из очигледних разлога, овде не долази у обзир мотив стицања славе и групи дјевојака које ће да те спопадају у бекстејџу након потписивања књиге). У случају бр 1) покушаћеш да пишеш што је могуће јасније и разумљивије, пажљиво пазећи при том да лијепо објасниш комплекснију материју и илуструјеш великим бројем примјера. Случај бр. 2) наравно може да се искомбинује са случајем бр 1), али генерално ако пишете књигу само због напредовања, тешко да ће да вас боли дупе разумију ли студенти то о чему лапрдате или не. Искрено речено, ја њушим да је код ове књиге у питању мотивација бр. 2). Наравно, могуће је да гријешим и да систем избора у звање на западу нема никакве сличности са нашим и да ником није потребно да пише књиге итд., али садржај ове књиге једноставно вришти у том смјеру. Потпуни недостатак било каквих примјера (осим на самом почетку књиге) поставља непремостив дебели зид између ове књиге и читаоца који није отприје упознат са материјом - а онај ко је упознат, тешко да ће научити нешто ново.

Можете да сматрате да сам ја неспособни идиот и да је ово комплексна материја високо преко мог максималног нивоа спознаје, али да се не зезамо - на првој години студија прочитао сам (и скоро у потпуности разумио) дивну Херштајнову књигу из апстрактне алгебре, крунисану доказом да је број "пи" трансцендентан. Разлог што сам разумио је диван ауторов стил и свјесност коме је књига намијењена. Добро писање научне и стручне литературе није само низање тачних формула и теорема, има ту нешто мало и педагогије. И немој само да ми неко каже да су пробабилистичке базе комплекснија област од апстрактне алгебре, јер ће тај неко моментално да буде одаламљен тавом по глави.

Опет, да не буде да сам неправедно извријеђао ауторе, немам никакву сумњу у њихову стручност и сигуран сам да је све у књизи исправно - једноставно, она одбија од себе неупућеног читаоца. С друге стране, неком ко је мало више загазио у ту област биће сигурно од користи јер представља солидан приказ тренутног стања у њој, са наведеним отвореним проблемима и обимним списком литературе и библиографским напоменама које су велика помоћ потенцијалним истраживачима.