Konjunktiv forespørsel - Conjunctive query

I databaseteori er en konjunktivspørring en begrenset form for førsteordens spørringer ved hjelp av den logiske konjunksjonsoperatoren . Mange førsteordensforespørsler kan skrives som konjunktive spørringer. Spesielt kan en stor del av forespørsler fra relasjonsdatabaser uttrykkes på denne måten. Konjunktive forespørsler har også en rekke ønskelige teoretiske egenskaper som større klasser med forespørsler (f.eks. De relasjonelle algebra -spørringene) ikke deler.

Definisjon

De konjunktive forespørslene er ganske enkelt fragmentet av (domeneuavhengig) førsteordens logikk gitt av settet med formler som kan konstrueres fra atomformler ved hjelp av konjunksjon ∧ og eksistensiell kvantifisering ∃, men ikke ved bruk av disjunksjon ∨, negasjon ¬ eller universell kvantifisering ∀ . Hver slik formel kan omskrives (effektivt) til en ekvivalent formel i prenex normal form , og derfor antas denne formen vanligvis ganske enkelt.

Således har konjunktive forespørsler følgende generelle form:

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

,

med de frie variablene som kalles distinkte variabler, og de bundne variablene kalles ikke -distinguished variabler. er atomformler . ${\ displaystyle x_ {1}, \ ldots, x_ {k}}$ ${\ displaystyle x_ {k+1}, \ ldots, x_ {m}}$ ${\ displaystyle A_ {1}, \ ldots, A_ {r}}$

Som et eksempel på hvorfor begrensningen til domeneuavhengig førsteordens logikk er viktig, bør du vurdere , som ikke er domeneuavhengig; se Codds teorem . Denne formelen kan ikke implementeres i select-project-join-fragmentet av relasjonsalgebra, og bør derfor ikke betraktes som en konjunktiv spørring. ${\ displaystyle x_ {1}. \ eksisterer x_ {2} .R (x_ {2})}$

Konjunktive forespørsler kan uttrykke en stor andel av spørsmålene som ofte sendes ut på relasjonsdatabaser . For å gi et eksempel, tenk deg en relasjonsdatabase for lagring av informasjon om studenter, deres adresse, kursene de tar og kjønn. Å finne alle mannlige studenter og adressene deres som deltar på et kurs som også deltar av en kvinnelig student, uttrykkes ved følgende konjunktivspørring:

(student, address) . ∃ (student2, course) .
   attends(student, course) ∧ gender(student, 'male') ∧ 
   attends(student2, course) ∧
   gender(student2, 'female') ∧ lives(student, address)

Merk at siden det eneste foretaket av interesse er den mannlige studenten og hans adresse, disse er bare preget variablene, mens variablene course, student2bare eksistensielt kvantifiseres , dvs undistinguished.

Fragmenter

Konjunktivforespørsler uten utmerkede variabler kalles boolske konjunktive spørringer . Konjunktivspørringer der alle variablene skilles (og ingen variabler er bundet) kalles equi-join-spørringer , fordi de er likeverdige i relasjonsberegningen til equi-join- spørringene i relasjonsalgebraen (når du velger alle kolonner i resultatet ).

Forholdet til andre spørrespråk

Konjunktive spørringer tilsvarer også utvalgte-prosjekt-sammenføyningsforespørsler i relasjonsalgebra (dvs. relasjonsalgebra-spørringer som ikke bruker operasjonsforeningen eller differansen) og til valg-fra-der-søk i SQL der tilstanden utelukkende bruker konjunksjoner av atomiske likestillingsbetingelser, dvs. betingelser konstruert fra kolonnenavn og konstanter som ikke bruker andre sammenligningsoperatorer enn "=", kombinert med "og". Spesielt utelukker dette bruk av aggregering og undersøkelser. For eksempel kan spørringen ovenfor skrives som en SQL -spørring av det konjunktive spørringsfragmentet som

select l.student, l.address
from   attends a1, gender g1,
       attends a2, gender g2,
       lives l
where  a1.student = g1.student and
       a2.student = g2.student and
       l.student = g1.student and
       a1.course = a2.course and
       g1.gender = 'male' and
       g2.gender = 'female';

Datalog

I tillegg til den logiske notasjonen kan konjunktive forespørsler også skrives som Datalog -regler. Mange forfattere foretrekker faktisk følgende Datalog -notasjon for spørringen ovenfor:

 result(student, address) :- attends(student, course),  gender(student, male),
                             attends(student2, course), gender(student2, female),
                             lives(student, address).

Selv om det ikke er noen kvantifiserere i denne notasjonen, er variabler som vises i hodet på regelen fortsatt implisitt universelt kvantifisert , mens variabler som bare vises i hoveddelen av regelen fortsatt er implisitt eksistensielt kvantifisert.

Selv om enhver konjunktiv spørring kan skrives som en Datalog -regel, kan ikke alle Datalog -programmer skrives som en konjunktiv spørring. Faktisk kan bare enkle regler over utvidede predikatsymboler lett skrives om som en tilsvarende konjunktivsøk. Problemet med å avgjøre om det for et gitt Datalog-program er et tilsvarende ikke- rekursivt program (tilsvarende en positiv relasjonsalgebra-forespørsel, eller tilsvarende en formel for positiv eksistensiell førsteordens logikk , eller, som et spesielt tilfelle, en konjunktiv spørring) er kjent som Datalog boundedness -problemet og kan ikke avgjøres.

Utvidelser

Utvidelser av konjunktive forespørsler som fanger mer uttrykksfull kraft inkluderer:

fagforeninger av konjunktive forespørsler , som tilsvarer positiv (dvs. negasjonsfri ) relasjonsalgebra
konjunktive spørsmål utvidet med fagforening og negasjon , som etter Codds teorem tilsvarer relasjonsalgebra og førsteordens logikk
konjunktive spørsmål med innebygde predikater , f.eks. aritmetiske predikater
konjunktive forespørsler med samlede funksjoner .

Den formelle studien av alle disse utvidelsene er begrunnet med deres anvendelse i relasjonsdatabaser og er innen databaseteori .

Kompleksitet

For å studere beregningskompleksiteten ved evaluering av konjunktive spørsmål må to problemer skilles. Den første er problemet med å evaluere en konjunktiv spørring på en relasjonsdatabase der både spørringen og databasen regnes som en del av inngangen. Kompleksiteten til dette problemet blir vanligvis referert til som kombinert kompleksitet , mens kompleksiteten i problemet med å evaluere en spørring på en relasjonsdatabase, der spørringen antas å være løst, kalles datakompleksitet .

Konjunktive søk er NP-komplette med hensyn på kombinert kompleksitet, mens dataene kompleksiteten av konjunktive spørringer er meget lav, i det parallelle kompleksitet klasse AC0 , som er inneholdt i LOGSPACE og således i polynomisk tid . Den NP-hardhet av konjunktive spørringer kan virke overraskende, ettersom relasjons algebra og SQL strengt subsume den konjunktive spørsmål og er således minst like hardt (i virkeligheten er relasjons algebra PSPACE -komplett med hensyn til kombinert kompleksitet og er derfor enda vanskeligere under meget holdt kompleksitetsteoretiske forutsetninger). I det vanlige applikasjonsscenariet er imidlertid databaser store, mens forespørsler er svært små, og datakompleksitetsmodellen kan være passende for å studere og beskrive problemene deres.

Problemet med å liste opp alle svarene på en ikke-boolsk konjunktivforespørsel har blitt studert i sammenheng med oppregningsalgoritmer , med en karakterisering (under noen forutsetninger for beregningshårdhet ) av spørringene som oppregning kan utføres med lineær tidsprosessering og konstant forsinkelse mellom hver løsning. Spesielt er dette de asykliske konjunktive forespørslene som også tilfredsstiller en fri-konneksjonstilstand .

Formelle egenskaper

Konjunktive forespørsler er en av de store suksesshistoriene for databaseteori ved at mange interessante problemer som er beregningsmessig vanskelige eller ikke kan avgjøres for større klasser med spørsmål, er gjennomførbare for konjunktive spørsmål. Vurder for eksempel spørringsinneslutningsproblemet. Vi skriver for to databaseforhold i samme skjema hvis og bare hvis hver tupel som forekommer i også forekommer i . Gitt en spørring og en relasjonsdatabase eksempel , skriver vi resultatet forhold til å vurdere spørsmålet om forekomsten bare som . Gitt to spørringer og og et databaseskjema , er spørsmålet containment problem problemet med å avgjøre hvorvidt for alle mulige databaseforekomster enn inngangsdatabaseskjema, . Hovedapplikasjonen for spørreinneslutning er i spørringsoptimalisering: Å bestemme om to spørringer er likeverdige er mulig ved ganske enkelt å kontrollere gjensidig inneslutning. ${\ displaystyle R \ subseteq S}$ ${\ displaystyle R, S}$ ${\ displaystyle R}$ ${\ displaystyle S}$ ${\ displaystyle Q}$ ${\ displaystyle I}$ ${\ displaystyle Q (I)}$ ${\ displaystyle Q_ {1}}$ ${\ displaystyle Q_ {2}}$ ${\ displaystyle I}$ ${\ displaystyle Q_ {1} (I) \ subseteq Q_ {2} (I)}$

Spørringsinneslutningsproblemet er uavgjort for relasjonsalgebra og SQL, men kan avgjøres og NP-fullføres for konjunktive spørringer. Faktisk viser det seg at spørringsinneslutningsproblemet for konjunktive spørringer er nøyaktig det samme problemet som spørreevalueringsproblemet. Siden forespørsler har en tendens til å være små, anses NP-fullstendighet her vanligvis som akseptabelt. Søkeinneslutningsproblemet for konjunktive spørringer tilsvarer også problemet med tilfredsstillelse av begrensninger .

En viktig klasse med konjunktive forespørsler som har kombinert kompleksitet på polynom-tid, er de asykliske konjunktive spørringene. Spørringen evaluering, og dermed spør containment, er LOGCFL -complete og dermed i polynomisk tid . Acyclicity of conjunctive queries er en strukturell egenskap for forespørsler som er definert med hensyn til søkets hypergraf : en konjunktiv spørring er asyklisk hvis og bare hvis den har hypertree-bredde 1. For det spesielle tilfellet av konjunktive spørringer der alle brukte relasjoner er binære , denne oppfatningen tilsvarer trebredden til avhengighetsgrafen til variablene i spørringen (dvs. grafen som har variablene i spørringen som noder og en uorientert kant mellom to variabler hvis og bare hvis det er en atomformel eller i spørringen ) og den konjunktive spørringen er asyklisk hvis og bare hvis avhengighetsgrafen er asyklisk . ${\ displaystyle \ {x, y \}}$ ${\ displaystyle R (x, y)}$ ${\ displaystyle R (y, x)}$

En viktig generalisering av acyclicity er forestillingen om begrenset hypertree-bredde , som er et mål på hvor nær acyklisk et hypergraf er, analogt med begrenset trebredde i grafer . Konjunktive spørsmål om begrenset trebredde har LOGCFL kombinert kompleksitet.

Ubegrensede konjunktive forespørsler om tredata (dvs. en relasjonsdatabase bestående av en binær barnerelasjon av et tre samt unære relasjoner for merking av treknutene) har kombinert kompleksitet på polynomtid.

Languages

In other projects