Imieliński–Lipski algebra

I databasteorin är Imieliński–Lipski-algebra en förlängning av relationalgebra till tabeller med olika typer av nollvärden . Det används för att arbeta på relationer med ofullständig information.

Imieliński–Lipski algebror definieras för att uppfylla exakta villkor för semantiskt meningsfull utvidgning av de vanliga relationsoperatorerna, såsom projektion, urval, förening och sammanfogning, från operatorer på relationer till operatorer på relationer med olika typer av "nollvärden".

Dessa villkor kräver att systemet är säkert i den meningen att ingen felaktig slutsats kan härledas genom att använda en specificerad delmängd F av relationsoperatorerna; och att det är fullständigt i den meningen att alla giltiga slutsatser som kan uttryckas av relationsuttryck som använder operatorer i F faktiskt är härledbara i detta system. Till exempel är det välkänt att den trevärdiga logiska metoden för att hantera nollvärden, stödd behandling av nollvärden av SQL inte är komplett, se Ullman bok. För att visa detta, låt T vara:

T=

NAMN	KLASS	KVALITET	TERMIN
Rohit	Databaser	B	Vår
Igor	Nätverk	A	NULL

Ta SQL-fråga Q

 
   
                 VÄLJ  NAMN  FRÅN  VAR  (  KLASS  =  'Nätverk'  OCH  SEMESTER  =  'Vår'  )  ELLER  (  GRADE  =  'A'  OCH  SEMESTER  <>  '  Vår'  ) 

SQL-fråga Q kommer att returnera tom uppsättning (inga resultat) under semantik med 3 värden som för närvarande används av alla varianter av SQL. Detta är fallet eftersom NULL i SQL aldrig är lika med någon konstant – i det här fallet varken "Vår" eller "Höst" eller "Vinter" (om det finns vintertermin i den här skolan). NULL='Spring' kommer att utvärderas till MAYBE och så kommer NULL='Fall' att utvärderas . Disjunktionen KANSKE ELLER KANSKE evalueras till KANSKE (inte SANT). Igor kommer alltså inte att vara en del av svaret (och naturligtvis inte Rohit heller). Men Igor bör lämnas tillbaka som svaret.

Oavsett vilken termin Igor tog Networks-klassen (oavsett vad som var det okända värdet på NULL), kommer urvalsvillkoret att vara sant. Denna "Igor" kommer att saknas av SQL och SQL-svaret kommer inte att vara fullständigt enligt fullständighetskraven specificerade i Tomasz Imieliński , Witold Lipski , 'Incomplete Information in Relational Databases'. Det hävdas också där att 3-värdig logik (TRUE, FALSE, KANSKE) aldrig kan ge garanti för fullständigt svar för tabeller med ofullständig information.

Tre algebror som uppfyller villkoren för säkerhet och fullständighet definieras som Imielinski–Lipski algebror: Codd-tabellalgebra , V-tabellalgebra och villkorstabellalgebra (C-tabeller).

Codd-tabeller algebra

Codd-tabellalgebra är baserad på de vanliga Codds singe NULL-värden. Tabellen T ovan är ett exempel på Codd-tabell. Codd-tabellalgebra stöder endast projektion och positiva urval. Det visas också i [IL84 att det inte är möjligt att korrekt utöka fler relationsoperatorer över Codd-tabeller. Till exempel kan en sådan grundläggande operation som join inte utökas över Codd-tabeller. Det är inte möjligt att definiera urval med booleska villkor som involverar negation och bevara fullständighet. Till exempel kan frågor som ovanstående fråga Q inte stöds. För att kunna utöka fler relationsoperatorer behövs en mer uttrycksfull form av nollvärdesrepresentation i tabeller som kallas V-tabell.

V-tabeller algebra

V-tabellalgebra är baserad på många olika ("markerade") nollvärden eller variabler som tillåts visas i en tabell. V-tabeller tillåter att visa att ett värde kan vara okänt men detsamma för olika tupler. Till exempel, i tabellen nedan beställer Gaurav och Igor samma (men okända) öl i två okända barer (som kan, eller kanske inte är olika – men förbli okända). Gaurav och Jane besöker samma okända bar (Y1). Därför använder vi istället ett NULL-värde, vi använder indexerade variabler eller Skolem-konstanter .

DRYCKARE	ÖL	BAR
Zhihan	Heineken	Cabana
Gaurav	X1	Y1
Igor	X1	Y2
Jane	Knopp	Y1
John	X2	Y3

V-tabellalgebra har visat sig stödja projektion, positivt urval (utan att ingen negation förekommer i urvalsvillkoret), förening och byte av attribut, vilket möjliggör bearbetning av godtyckliga konjunktiva frågor. En mycket önskvärd egenskap som V-tabellalgebra åtnjuter är att alla relationsoperatorer på tabeller utförs på exakt samma sätt som i fallet med de vanliga relationerna.

Villkorstabeller (c-tabeller) algebra

Exempel på villkorstabell (c-tabell) visas nedan.

NAMN	KLASS	KVALITET	TERMIN	lura
Rohit	Databaser	B	Vår	Sann
Igor	Nätverk	A	x	x = 'vår'
Igor	Nätverk	A	x	x <> 'Vår'

Den har ytterligare kolumn "con" som är ett booleskt tillstånd som involverar variabler, nollvärden - samma som i V-tabeller.

 
   
                 VÄLJ  *  VARifrån  (  KLASS  =  'Nätverk'  OCH  SEMESTER  =  'Vår'  )  ELLER  (  BETYG  =  'A'  OCH  SEMESTER  <>  '  Vår  '  ) 

över följande tabell c-tabell

T1=

NAMN	KLASS	KVALITET	TERMIN	lura
Rohit	Databaser	B	Vår	Sann
Igor	Nätverk	A	x	Sann

Villkorstabellalgebra, huvudsakligen av teoretiskt intresse, stödjer projektion, urval, förening, sammanfogning och byte av namn. Under antagande om en sluten värld kan den också hantera skillnadsoperatören, så den kan stödja alla relationsoperatörer.

Historia

Imieliński–Lipski algebror introducerades av Tomasz Imieliński och Witold Lipski Jr. i Incomplete Information in Relational Databases .

Vidare läsning

• Abiteboul, S .; Kanellakis, P.; Grahne, G. (1991). "Om representation och sökning av uppsättningar av möjliga världar" (PDF) . Teoretisk datavetenskap . 78 (1): 159–187. doi : 10.1016/0304-3975(51)90007-2 .
•   Abiteboul, S.; Duschka, OM (1998). "Komplexiteten i att svara på frågor med materialiserade vyer". Proc. ACM SIGMOD-SIGACT-SIGART, PODS : 254–263. CiteSeerX 10.1.1.92.2956 .
• Green, TJ; Karvounarakis, G.; Tannen, Val (2007). "Proveniens Semiring" . Proc. ACM SIGMOD-SIGACT-SIGART, PODS : 31–40.
•   Karvounarakis, G.; Green, TJ (2012). "Semiring-kommentarerade data: frågor och härkomst" (PDF) . ACM SIGMOD . 41 (3): 5–14. doi : 10.1145/2380776.2380778 . S2CID 11600847 .
• TJ Green (2009). Modeller för ofullständig och probabilistisk information; Kapitel 2, i Hantera och bryta osäkra data . Springer Link.
• Grahne, G.; Kiricenko, V. (november 2004). "Mot en algebraisk teori om informationsintegration" (PDF) . Information och beräkning . 194 (2): 79–100. doi : 10.1016/j.ic.2004.07.003 .