A PROBABILISTIC VIEW OF DATALOG PARALLELIZATION

Authors
LIFSCHITZ S VIANU V
Citation
S. Lifschitz et V. Vianu, A PROBABILISTIC VIEW OF DATALOG PARALLELIZATION, Theoretical computer science, 190(2), 1998, pp. 211-239
Citations number
30
Categorie Soggetti
Computer Science Theory & Methods","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
190
Issue
2
Year of publication
1998
Pages
211 - 239
Database
ISI
SICI code
0304-3975(1998)190:2<211:APVODP>2.0.ZU;2-J
Abstract
We explore an approach to developing Datalog parallelization strategie s that aims at good expected rather than worst-case performance. To il lustrate, we consider a very simple parallelization strategy that appl ies to all Datalog programs. We prove that this has very good expected performance under equal distribution of inputs. This is done using an extension of 0-1 laws adapted to this context. The analysis is confir med by experimental results on randomly generated data.