Random databases and threshold for monotone non-recursive datalog

Konstantin Korovin; Andrei Voronkov

doi:10.1007/11549345_51

Random databases and threshold for monotone non-recursive datalog

Research output: Chapter in Book/Conference proceeding › Conference contribution

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. © Springer-Verlag Berlin Heidelberg 2005.

Original language	English
Title of host publication	Lecture Notes in Computer Science\|Lect. Notes Comput. Sci.
Editors	J. Jedrzejowicz, A. Szepietowski
Publisher	Springer Nature
Pages	591-602
Number of pages	11
Volume	3618
DOIs	https://doi.org/10.1007/11549345_51
Publication status	Published - 2005
Event	30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005 - Gdansk Duration: 1 Jul 2005 → … http://dblp.uni-trier.de/db/conf/mfcs/mfcs2005.html#KorovinV05http://dblp.uni-trier.de/rec/bibtex/conf/mfcs/KorovinV05.xmlhttp://dblp.uni-trier.de/rec/bibtex/conf/mfcs/KorovinV05

Publication series

Name	Lecture Notes in Computer Science

Conference

Conference	30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005
City	Gdansk
Period	1/07/05 → …
Internet address	http://dblp.uni-trier.de/db/conf/mfcs/mfcs2005.html#KorovinV05http://dblp.uni-trier.de/rec/bibtex/conf/mfcs/KorovinV05.xmlhttp://dblp.uni-trier.de/rec/bibtex/conf/mfcs/KorovinV05

Access to Document

10.1007/11549345_51

Cite this

@inproceedings{a692bae7addf4b90b403329e1b72d004,

title = "Random databases and threshold for monotone non-recursive datalog",

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. {\textcopyright} Springer-Verlag Berlin Heidelberg 2005.",

author = "Konstantin Korovin and Andrei Voronkov",

year = "2005",

doi = "10.1007/11549345_51",

language = "English",

volume = "3618",

series = "Lecture Notes in Computer Science",

publisher = "Springer Nature",

pages = "591--602",

editor = "J. Jedrzejowicz and A. Szepietowski",

booktitle = "Lecture Notes in Computer Science|Lect. Notes Comput. Sci.",

address = "United States",

note = "30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005 ; Conference date: 01-07-2005",

url = "http://dblp.uni-trier.de/db/conf/mfcs/mfcs2005.html#KorovinV05http://dblp.uni-trier.de/rec/bibtex/conf/mfcs/KorovinV05.xmlhttp://dblp.uni-trier.de/rec/bibtex/conf/mfcs/KorovinV05",

}

Korovin, K & Voronkov, A 2005, Random databases and threshold for monotone non-recursive datalog. in J Jedrzejowicz & A Szepietowski (eds), Lecture Notes in Computer Science|Lect. Notes Comput. Sci.. vol. 3618, Lecture Notes in Computer Science, Springer Nature, pp. 591-602, 30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005, Gdansk, 1/07/05. https://doi.org/10.1007/11549345_51

Random databases and threshold for monotone non-recursive datalog. / Korovin, Konstantin; Voronkov, Andrei.
Lecture Notes in Computer Science|Lect. Notes Comput. Sci.. ed. / J. Jedrzejowicz; A. Szepietowski. Vol. 3618 Springer Nature, 2005. p. 591-602 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Conference proceeding › Conference contribution

TY - GEN

T1 - Random databases and threshold for monotone non-recursive datalog

AU - Korovin, Konstantin

AU - Voronkov, Andrei

PY - 2005

Y1 - 2005

N2 - 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. © Springer-Verlag Berlin Heidelberg 2005.

AB - 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. © Springer-Verlag Berlin Heidelberg 2005.

U2 - 10.1007/11549345_51

DO - 10.1007/11549345_51

M3 - Conference contribution

VL - 3618

T3 - Lecture Notes in Computer Science

SP - 591

EP - 602

BT - Lecture Notes in Computer Science|Lect. Notes Comput. Sci.

A2 - Jedrzejowicz, J.

A2 - Szepietowski, A.

PB - Springer Nature

T2 - 30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005

Y2 - 1 July 2005

ER -

Random databases and threshold for monotone non-recursive datalog

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this