Random databases and threshold for monotone non-recursive datalog

Konstantin Korovin, Andrei Voronkov

    Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish
    Title of host publicationLecture Notes in Computer Science|Lect. Notes Comput. Sci.
    EditorsJ. Jedrzejowicz, A. Szepietowski
    PublisherSpringer Nature
    Pages591-602
    Number of pages11
    Volume3618
    DOIs
    Publication statusPublished - 2005
    Event30th 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

    NameLecture Notes in Computer Science

    Conference

    Conference30th International Symposium on Mathematical Foundations of Computer Science 2005, MFCS 2005
    CityGdansk
    Period1/07/05 → …
    Internet address

    Fingerprint

    Dive into the research topics of 'Random databases and threshold for monotone non-recursive datalog'. Together they form a unique fingerprint.

    Cite this