Alla rättigheter förbehållna. Ingen del av denna publikation får reproduceras, lagras i ett återvinningssystem eller överföras, i någon form eller på något sätt, elektroniskt, mekaniskt, fotokopiering, inspelning eller på annat sätt, utan föregående skriftligt tillstånd från förlaget. Tryckt i USA.  Förord Atabase teori är en relativ nykomling till området datavetenskap. Tidiga datahanteringssystem baserades på tekniker från flera klassiska områden inom datavetenskap, allt från hårdvara och operativsystem till datastrukturer och programmeringsspråk. I början av sjuttiotalet producerade ett språng av abstraktion från filsystem relationsdatabaser och dess tillhörande teori, med logik som katalysator. Vi tror att databasteorin har mognat – att den har framträtt som en elegant och robust del av vetenskapen med sin egen identitet. Som sådan, förkroppsligar det sitt eget säregna kännemärke av visdom som förtjänar att förmedlas inte bara till insiders, utan till datavetenskapen i stort. I ett nötskal är ett databashanteringssystem ett programvarusystem som möjliggör skapande, underhåll och användning av stora mängder data. I motsats till många programprogram är den logiska datastrukturen – "databasschemat" – som används för att strukturera en viss datamängd vanligtvis mycket mindre än volymen på den uppsättningen. Dessutom, data är ihållande, utvecklas över tid och överlevande flera anrop av databashantering programvara. För att öka användbarheten stöds samtidig åtkomst till data vanligtvis med specialiserade protokoll som garanterar en form av icke-interferens mellan interleaded transaktioner. Det är viktigt att det finns en distinktion mellan den logiska nivån och den fysiska nivån i moderna databashanteringssystem. Den logiska nivån fokuserar på en abstrakt representation av data, tillsammans med språk för att skapa, fråga och ändra det; den fysiska nivån fokuserar på det underliggande genomförandet, inklusive den fysiska layouten som används för att lagra data, indexering och klustersystem, och konvergens- och återhämtningsprotokoll. Databasteorin har i första hand utvecklats kring den logiska nivån på databaserna. (Ett anmärkningsvärt undantag är konvergenskontroll, som inte behandlas i denna volym.) En kärna av grundläggande material om relationsmodellen har blivit väl etablerad. Den består främst av tre paradigmer för frågespråk (algebraiska, kalkylbaserade och avdragsgilla) och teorin om beroenden. Teorin om frågespråk, inklusive frågor om expressivitet och komplexitet som är specifika för databaser, är väl utvecklad. Äktenskapet mellan databaser och logik programmering producerade avdragsdatabaser, med huvudfokus på de avdragsgilla frågespråk. Beroendeteorin fokuserade inledningsvis på att formalisera och tillämpa de olikartade integritetsbegränsningar som vanligen uppstår i praktiken, och det gick vii viii Förord om att relatera begränsningar med frågeoptimering och att utveckla ett enande perspektiv för dem. Som ett fält bygger databasteorin på flera områden, bland annat matematisk logik, komplexitet och programmeringsspråk. Men databassammanhanget för med sig olika antaganden, perspektiv och undertoner. Relations kan ses som predikat i logikens bemärkelse, och relationskalkylen som en specialisering av den första ordningens predikatkalkyl. Databasområdet betonar dock ändliga strukturer och har utvecklat begreppen "domänoberoende" och "säkerhet" för att fånga intuitiva egenskaper relaterade till denna finitud. Frågorna och teknikerna i beroendeteorin lånar mycket från logiken, med fokus på praktiskt taget motiverade, relativt svaga klasser av meningar. Frågespråk ger en intressant kontrast till konventionella, tvingande programmeringsspråk. Fråga språk normalt förkroppsligar en set-at-a-time fokus i motsats till en objekt-at-a-time fokus. De är också till stor del förklarande till sin natur, och om man inte gör det, är de mer tillämpbara än tvingande. På grund av betoningen på dragbarhet inför stora datavolymer finns det ett stort intresse för frågespråk som inte har full beräkningskraft, vilket ger upphov till ett rikt samspel mellan frågespråk och komplexitetsteori. Specialiserade begrepp av komplexitet har uppstått, som härrör från den praktiska verkligheten av stora volymer av data och det teoretiska intresset för olika frågespråk. Den viktiga uppfattningen om "genericitet", som fångar en form av abstraktion som härrör från separationen av de logiska och fysiska nivåerna, har också lett till nya perspektiv på komplexitetsteorin, som inbegriper formalismer som kringgår beställningen av ingångsdata implicit i traditionella Turingmaskiner. Spännande nya forskningsinriktningar har fortsatt att framträda i databasteorin, främst från obesvarade frågor om frågespråk och från ett intresse av att expandera bortom den relationella modellens begränsningar. I aktuell forskning ingår undersökningar som motiveras av samband med objektorientering, artificiell intelligens och grafiska gränssnitt. Och när databasfältet mognar påverkar det i sin tur angränsande områden inom datavetenskapen, särskilt ändlig modellteori, programmeringsspråk och logikprogrammering. Denna bok handlar om den teori som har utvecklats kring den logiska nivån av databaser. Den har två huvudmål: att ge en fokuserad presentation av kärnmaterialet och att presentera kärnan i det avancerade materialet inom en enhetlig ram. En del av det avancerade materialet har aldrig tidigare presenterats i bokform. Presentationsstilen är ganska rigorös, i att exakta definitioner och uttalanden av resultat ges. Men vårt övergripande intresse var att göra saker och ting enkla för läsaren, att komma över intuitionen och elegansen i begreppen och bevisen, snarare än att följa mycket strikta kriterier för stelbenthet. Ett stort antal exempel, siffror och övningar bör bidra till att klargöra utvecklingen. Några av bevisen betonar intuition och utelämnar mycket av detaljerna; vi kallade ett sådant bevis för en "crux". På så sätt har vi försökt uppnå en balans mellan formalism och intuition. När vi gick vidare, en två-tier stil uppstod, med en tendens till mer rigor i utställningen av kärnmaterialet och mer intuition i presentationen av avancerade och tangerande ämnen. Boken riktar sig till en eklektisk publik. Mer allmänt bör det vara en användbar resurs för alla datavetare eller matematiker som vill ta reda på vad databasteori handlar om. Databasforskare och praktiker bör finna det användbart som en hänvisning till både klassiskt material och avancerade ämnen, annars utspridda i ibland svårlästa tidningar. Som lärobok riktar sig det till doktorander och seniorer som använder boken som huvudtext i en databasteorikurs eller som kompletterande material i en databassystemkurs. Boken är ganska fristående. En viss behövlig bakgrund ges koncis i preliminariet, och läsaren får veta var mer kan hittas. Vi har försökt göra livet lättare för databasen aficionado genom att konsekvent anpassa materialet till databasramen. Detta sparar läsaren arbetet med att översätta till databasramverket, en uppgift som i bästa fall är distraherande och i värsta fall tråkig och förvirrande. Kanske den mest betydande skillnaden från den konventionella presentationen uppstår i fallet med logisk programmering, där den avdragsgilla databas synvinkeln har dramatiska effekter. För det mesta blir saker och ting mycket enklare eftersom det inte finns några funktionssymboler. För vissa frågor, såsom uttryckskraft och komplexitet, är det konventionella tillvägagångssättet emellertid helt enkelt inte tillämpligt. Boken håller också ett starkt fokus på databasteori-tangential material från angränsande områden har hållits till ett absolut minimum. Resultaten hänför sig till källorna i bibliografiska noter, som ingår i slutet av varje kapitel. Konturen i denna bok är som följer. Del A innehåller preliminärer och en kort introduktion till databaser och relationsmodellen. Grundmaterialet om relationsspråk utvecklas i del B. Genom hela presentationen av frågespråk utvecklar vi parallellt de tre frågespråksparadigmerna: algebraisk, kalkylbaserad och deduktiv. Presentationen börjar med konjunktiva frågor, som ligger i kärnan av praktiskt taget alla frågespråk, både formella och kommersiella, och har särskilt fina egenskaper som gör dem till den prototypiska väluppfostrade klassen av frågor. Vi använder konjunktiva frågor som ett verktyg för att introducera många av de viktigaste frågorna i frågespråk, som kommer att återkomma genom hela boken. Mer kraftfulla språk erhålls sedan genom att gradvis berika konjunktiva frågor genom att lägga negation, recursion, och slutligen negation och recursion kombineras. I varje steg undersöker vi de grundläggande egenskaperna hos de nyligen erhållna klasserna av frågor och kontrasterar dem med frågor som övervägts tidigare. Att lägga till union och negation ger tre likvärdiga språk: relationskalkyl (första ordningens logik utan funktionssymboler), relationsal algebra och icke-rekursiv datalogg ¬. Språken med rekursion studeras i del D. Lägga till rekursion till konjunktiva frågor ger datalogg. Recursion i kombination med negation producerar datalogg ¬ (med de olika tillhörande semantik för negation), och andra språk, hela vägen till fixpoint och medan frågor. Här ingår en presentation av det logiska programmeringsparadigmet inom ramen för databaser, med implementeringstekniker, inklusive topdown, bottom-up och heuristik för optimering. Beroendeteorin presenteras i del C. Tyngdpunkten ligger på funktionella, gemensamma och inkluderande beroenden, som är allmänt förekommande i praktiken. Vi använder dessa klasser av x Preface beroenden för att illustrera de viktigaste frågorna. Ett större perspektiv på mer allmänna beroenden ges också. Användningar av beroenden i frågeoptimering och schema design presenteras. Mer avancerat material om hur uttrycksfulla och komplexa frågespråk är presenteras i del E. Målet är att belysa de aspekter av beräkningsbarhet och komplexitet som är specifika för databaser. Detta inkluderar komplexa åtgärder för frågor och resultat om sambandet mellan språk och komplexitetsklasser. I synnerhet, begreppet fråga formaliseras noggrant, och språk som uttrycker alla frågor visas. Vissa avancerade tekniker som 0-1 lagar och spel, presenteras på ett informellt och fristående sätt, i syfte att göra dem lättillgängliga för läsare med en begränsad bakgrund i logik. Slutligen kartläggs flera avancerade ämnen kortfattat i del F. De omfattar ofullständig information, komplexa objekt och objektorienterade databaser samt dynamiska aspekter. Dessa delar egenskapen att de är mindre etablerade, och möjligen mer kontroversiella än de andra ämnen som behandlas. Vårt mål är att identifiera de viktigaste begreppen och frågeställningarna inom vart och ett av dessa områden, som sannolikt kommer att generera en betydande del av databasteoriforskningen under de kommande åren. Stilen är mer informell, i form av en undersökning, med de flesta bevis utelämnas och pekare ges till aktuell forskning.
För att beskriva en spårningsfråga på ett användarvänligt sätt använder vi dataloggspråket, som är ett välkänt frågespråk för avdragsdatabaser REF.