Boolesk konjunktivfråga

I teorin om relationsdatabaser är en boolesk konjunktivfråga en konjunktivfråga utan distingerade predikat, dvs en fråga i formen $R_{1}(t_ {1})\wedge \cdots \wedge R_{n}(t_{n})$ , där varje $R_{i}$ är en relationssymbol och varje $t_{i}$ är en tupel av variabler och konstanter; antalet element i $t_{i}$ är lika med ariteten av $R_{i}$ . En sådan fråga utvärderas till antingen sant eller falskt beroende på om relationerna i databasen innehåller lämpliga tuplar av värden, dvs. konjunktionen är giltig enligt fakta i databasen.

Som ett exempel, om ett databasschema innehåller relationssymbolerna $Fader$ (binär, vem är fadern till vem) och $Anställd$ (ärlig, vem är anställd), kan en konjunktivfråga vara $Fader({\text{Mark}},x)\wedge Anställd(x)$ . Den här frågan utvärderas till sant om det finns en individ $x$ som är barn till Mark och anställd. Med andra ord uttrycker denna fråga frågan: "har Mark ett anställt barn?"

Se även

G. Gottlob; N. Leone; F. Scarcello (2001). "Komplexiteten hos acykliska konjunktiva frågor". Journal of the ACM . 48 (3): 431–498. doi : 10.1145/382780.382783 .