Konjunktiv fråga

I databasteorin är en konjunktivfråga en begränsad form av första ordningens frågor som använder den logiska konjunktionsoperatorn. Många första ordningens frågor kan skrivas som konjunktiva frågor. I synnerhet kan en stor del av frågor som ställs på relationsdatabaser uttryckas på detta sätt. Konjunktiva frågor har också ett antal önskvärda teoretiska egenskaper som större klasser av frågor (t.ex. de relationella algebrafrågorna ) inte delar.

Definition

Konjunktivfrågorna är fragmentet av (domänoberoende) första ordningens logik som ges av uppsättningen formler som kan konstrueras från atomformler med hjälp av konjunktion ∧ och existentiell kvantifiering ∃, men inte med disjunktion ∨, negation ¬ eller universell kvantifiering ∀. Varje sådan formel kan skrivas om (effektivt) till en likvärdig formel i prenex normal form , så denna form antas vanligtvis helt enkelt.

Konjunktiva frågor är alltså av följande allmänna form:

(x_{1},\ldots ,x_{k}).\exists x_{k+1},\ldots x_{m}.A_{1}\wedge \ldots \ kil A_{r}

,

där de fria variablerna $x_{1},\ldots ,x_{k}$ kallas distinguished variables, och de bundna variablerna $x_{ k+1},\ldots ,x_{m}$ kallas odistinguished variabler. $A_{1},\ldots ,A_{r}$ är atomformler .

Som ett exempel på varför begränsningen till domänoberoende första ordningens logik är viktig, överväg ${\displaystyle x_{1}.\exists x_{2}.R(x_{2})} ,$ som inte är domänoberoende; se Codds sats . Denna formel kan inte implementeras i select-project-join-fragmentet av relationalgebra, och bör därför inte betraktas som en konjunktiv fråga.

Konjunktiva frågor kan uttrycka en stor andel av frågor som ofta skickas i relationsdatabaser . För att ge ett exempel, föreställ dig en relationsdatabas för att lagra information om studenter, deras adress, de kurser de läser och deras kön. Att hitta alla manliga studenter och deras adresser som går en kurs som också går av en kvinnlig student uttrycks med följande konjunktivfråga:

(student, adress) . ∃ (student2, kurs) . deltar(student, kurs) ∧ kön(student, 'man') ∧ deltar(student2, kurs) ∧ kön(student2, 'kvinna') ∧ lever(student, adress)

Observera att eftersom den enda entiteten av intresse är den manliga studenten och hans adress, är dessa de enda särskiljande variablerna, medan variablerna kurs , student2 endast är existentiellt kvantifierade , dvs odistinguished.

Fragment

Konjunktiva frågor utan distingerade variabler kallas booleska konjunktiva frågor . Konjunktiva frågor där alla variabler särskiljs (och inga variabler är bundna) kallas equi-join-frågor , eftersom de är ekvivalenta, i relationskalkylen , till equi-join- frågorna i den relationella algebra (när man väljer alla kolumner i resultatet ).

Förhållande till andra frågespråk

Konjunktiva frågor motsvarar också select-project-join-frågor i relationalgebra (dvs relationalgebrafrågor som inte använder operationsunionen eller skillnaden) och till select-from-where-frågor i SQL där where-villkoret enbart använder konjunktioner av atomära jämlikhetsvillkor, dvs. villkor konstruerade från kolumnnamn och konstanter utan användning av andra jämförelseoperatorer än "=", kombinerade med "och". Detta utesluter särskilt användningen av aggregering och underfrågor. Till exempel kan frågan ovan skrivas som en SQL-fråga för det konjunktiva frågefragmentet som

  
      
          
        
     
          
          
          
          
          välj  l  .  student  ,  l  .  adress  från  går  a1  ,  kön  g1  ,  går på  a2  ,  kön  g2  ,  bor  l  där  a1  .  student  =  g1  .  student  och  a2  .  elev  =  g2  .  student  och  l  .  student  =  g1  .  student  och  a1  .  kurs  =  a2  .  kurs  och  g1  .  kön  =  'man'  och  g2  .  kön  =  'kvinna'  ;

Datalog

Förutom deras logiska notation kan konjunktiva frågor också skrivas som datalogregler . Många författare föredrar faktiskt följande Datalog-notation för frågan ovan:

        
                                
                               resultat  (  student  ,  adress  )  :-  deltar  (  student  ,  kurs  ),  kön  (  student  ,  man  ),  deltar  (  student 2  ,  kurs  ),  kön  (  student 2  ,  kvinna  ),  bor  (  student  ,  adress  ).

Även om det inte finns några kvantifierare i denna notation, är variabler som förekommer i regelns huvud fortfarande implicit universellt kvantifierade , medan variabler som endast förekommer i regelns kropp fortfarande är implicit existentiellt kvantifierade.

Även om vilken konjunktiv fråga som helst kan skrivas som en Datalog-regel, kan inte alla Datalog-program skrivas som en konjunktiv fråga. Faktum är att endast enstaka regler över förlängningspredikatsymboler lätt kan skrivas om som en likvärdig konjunktivfråga. Problemet med att avgöra om det för ett givet Datalog-program finns ett ekvivalent icke-rekursivt program (motsvarande en positiv relationell algebrafråga, eller, på motsvarande sätt, en formel för positiv existentiell första ordningens logik , eller, som ett specialfall, en konjunktiv fråga) är känt som Datalog boundedness-problemet och kan inte avgöras.

Tillägg

Tillägg av konjunktiva frågor som fångar mer uttryckskraft inkluderar:

sammanslutningar av konjunktiva frågor , som motsvarar positiv (dvs. negationsfri ) relationalgebra
konjunktiva frågor utökade med union och negation , som enligt Codds sats motsvarar relationalgebra och första ordningens logik
konjunktiva frågor med inbyggda predikat , t.ex. aritmetiska predikat
konjunktiva frågor med aggregerade funktioner .

Den formella studien av alla dessa tillägg motiveras av deras tillämpning i relationsdatabaser och är inom databasteorin .

Komplexitet

För att studera den beräkningsmässiga komplexiteten i att utvärdera konjunktiva frågor måste två problem särskiljas. Det första är problemet med att utvärdera en konjunktiv fråga på en relationsdatabas där både frågan och databasen anses vara en del av indata. Komplexiteten i detta problem brukar kallas kombinerad komplexitet , medan komplexiteten i problemet med att utvärdera en fråga i en relationsdatabas, där frågan antas vara fixerad, kallas datakomplexitet .

Konjunktiva frågor är NP-kompletta med avseende på kombinerad komplexitet, medan datakomplexiteten för konjunktiva frågor är mycket låg, i den parallella komplexitetsklassen AC0 , som finns i LOGSPACE och därmed i polynomtid . NP -hårdheten för konjunktiva frågor kan tyckas överraskande, eftersom relationalgebra och SQL strikt subsumerar konjunktivfrågorna och därmed är minst lika hårda (i själva verket är relationsalgebra PSPACE -komplett med avseende på kombinerad komplexitet och är därför ännu svårare under allmänt höll komplexitetsteoretiska antaganden). Men i det vanliga tillämpningsscenariot är databaserna stora, medan frågorna är mycket små, och datakomplexitetsmodellen kan vara lämplig för att studera och beskriva deras svårighetsgrad.

Problemet med att lista alla svar på en icke-boolesk konjunktiv fråga har studerats i samband med uppräkningsalgoritmer , med en karakterisering (under vissa antaganden om beräkningshårdhet ) av de frågor för vilka uppräkning kan utföras med linjär tidsförbehandling och konstant fördröjning mellan varje lösning. Specifikt är dessa de acykliska konjunktiva frågorna som också uppfyller ett villkor för fri anslutning .

Formella egenskaper

databasteorins stora framgångshistorier genom att många intressanta problem som är beräkningsmässigt svåra eller oavgörbara för större klasser av frågor är möjliga för konjunktiva frågor. Tänk till exempel på frågan om inneslutningsproblem. Vi skriver $R\subseteq S$ för två databasrelationer $R,S$ i samma schema om och endast om varje tupel som förekommer i $R$ också förekommer i $S$ . Givet en fråga $Q$ och en relationsdatabasinstans $I$ $Q(I)$ skriver vi resultatrelationen för att utvärdera frågan på instansen helt enkelt som ( . Med tanke på två frågor $Q_{1}$ och $Q_{2}$ och ett databasschema , är frågans inneslutningsproblem problemet med att bestämma om för alla möjliga databasinstanser $I$ över indatabasschemat $Q_{1}(I)\subseteq Q_{2}(I)$ . Den huvudsakliga tillämpningen av frågeinneslutning är frågeoptimering: Att bestämma om två frågor är likvärdiga är möjligt genom att helt enkelt kontrollera ömsesidig inneslutning.

Frågeinneslutningsproblemet är oavgörbart för relationalgebra och SQL men är avgörbart och NP-komplett för konjunktiva frågor. Faktum är att det visar sig att frågeinneslutningsproblemet för konjunktiva frågor är exakt samma problem som frågeutvärderingsproblemet. Eftersom frågor tenderar att vara små, NP-fullständighet här vanligtvis vara acceptabel. Frågainneslutningsproblemet för konjunktiva frågor är också likvärdigt med problemet med begränsningstillfredsställelse .

En viktig klass av konjunktiva frågor som har polynom-tid kombinerad komplexitet är de acykliska konjunktiva frågorna. Frågeutvärderingen, och därmed frågeinneslutning, är LOGCFL -komplett och därmed i polynomtid . Acyklicitet för konjunktiva frågor är en strukturell egenskap hos frågor som definieras med avseende på frågans hypergraf : en konjunktiv fråga är acyklisk om och endast om den har hypertree-width 1. För specialfallet med konjunktiva frågor där alla relationer som används är binära , motsvarar detta begrepp trädbredden på beroendegrafen för variablerna i frågan (dvs grafen som har variablerna för frågan som noder och en oriktad kant { $\displaystyle \{x,y\}}$ mellan två variabler om och endast om det finns en atomformel $R(x,y)$ eller $R(y,x)$ i frågan) och konjunktivfrågan är acyklisk om och endast om dess beroendegraf är acyklisk .

En viktig generalisering av acyklicitet är begreppet bounded hypertree-width , som är ett mått på hur nära acyklisk en hypergraf är, analogt med bounded treewidth i grafer . Konjunktiva frågor med avgränsad trädbredd har LOGCFL kombinerad komplexitet.

Obegränsade konjunktiva frågor över träddata (dvs. en relationsdatabas som består av en binär underordnad relation till ett träd såväl som unära relationer för märkning av trädnoderna) har polynomisk tidskomplexitet.

externa länkar