Name
Abstract | ||
|---|---|---|
In this paper we define a model of randomly generated databases and show how one can compute the threshold functions for queries expressible in monotone non-recursive datalog≠. We also show that monotone non-recursive datalog≠ cannot express any property with a sharp threshold. Finally, we show that non-recursive datalog≠ has a 0–1 law for a large class of probability functions, defined in the paper. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11549345_51 | MFCS |
Keywords | Field | DocType |
probability function,large class,non-recursive datalog,random databases,queries expressible,sharp threshold,monotone non-recursive datalog,threshold function | Discrete mathematics,Bernstein's theorem on monotone functions,Combinatorics,Database query,Datalog,Mathematics,Recursion,Monotone polygon,Database,Threshold function | Conference |
Volume | ISSN | ISBN |
3618 | 0302-9743 | 3-540-28702-7 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Konstantin Korovin | 1 | 288 | 20.64 |
| Andrei Voronkov | 2 | 2670 | 225.46 |