Algebra Imielińskiego-Lipskiego

W teorii baz danych algebra Imielińskiego – Lipskiego jest rozszerzeniem algebry relacyjnej na tablice z różnymi typami wartości pustych . Służy do operowania na relacjach z niepełnymi informacjami.

Algebry Imielińskiego – Lipskiego są definiowane tak, aby spełniały precyzyjne warunki semantycznie znaczącego rozszerzenia zwykłych operatorów relacji, takich jak rzutowanie, selekcja, suma i łączenie, od operatorów relacji do operatorów relacji z różnymi rodzajami „wartości zerowych”.

Warunki te wymagają, aby system był bezpieczny w tym sensie, że nie można wyprowadzić błędnego wniosku przy użyciu określonego podzbioru F operatorów relacji; i aby był kompletny w tym sensie, że wszystkie ważne wnioski, które można wyrazić za pomocą wyrażeń relacyjnych za pomocą operatorów w F, są w rzeczywistości wyprowadzalne w tym systemie. Na przykład dobrze wiadomo, że trójwartościowe podejście logiczne do radzenia sobie z wartościami pustymi, obsługiwane traktowanie wartości pustych przez SQL nie jest kompletne, patrz książka Ullmana . Aby to pokazać, niech T będzie:

T=

NAZWA	KLASA	STOPIEŃ	SEMESTR
Rohit	Bazy danych	B	Wiosna
Igor	Sieci	A	ZERO

Weź zapytanie SQL Q

 
   
                 WYBIERZ  NAZWĘ  Z  T  GDZIE  (  KLASA  =  'Sieci'  I  SEMESTR  =  'Wiosna'  )  LUB  (  KLASA  =  'A'  I  SEMESTR  <>  'Wiosna'  ) 

Zapytanie SQL Q zwróci pusty zestaw (brak wyników) zgodnie z semantyką 3-wartościową obecnie przyjętą przez wszystkie warianty SQL. Dzieje się tak, ponieważ w SQL NULL nigdy nie jest równe żadnej stałej – w tym przypadku ani „wiosnie”, ani „jesieni”, ani „zimie” (jeśli w tej szkole jest semestr zimowy). NULL='Spring' oceni na MOŻE, podobnie jak NULL='Fall' . Alternatywa MOŻE LUB MOŻE daje w wyniku MOŻE (nie PRAWDA). Tak więc Igor nie będzie częścią odpowiedzi (i oczywiście nie będzie też Rohit). Ale Igor powinien zostać zwrócony jako odpowiedź.

Rzeczywiście, niezależnie od tego, w którym semestrze Igor miał zajęcia z sieci (bez względu na to, jaka była nieznana wartość NULL), warunek wyboru będzie prawdziwy. Ten „Igor” zostanie pominięty przez SQL i odpowiedź SQL nie będzie kompletna zgodnie z wymaganiami kompletności określonymi w Tomasz Imieliński , Witold Lipski , „Incomplete Information in Relational Databases”. Argumentuje się tam również, że logika trójwartościowa (PRAWDA, FAŁSZ, MOŻE) nigdy nie daje gwarancji pełnej odpowiedzi dla tabel z niepełnymi informacjami.

Trzy algebry, które spełniają warunki bezpieczeństwa i zupełności, określa się jako algebry Imielińskiego-Lipskiego: algebra Codda-Tables , algebra V-tablic i algebra tablic warunkowych (C-tabel).

Algebra tablic Codda

Algebra tablic Codda jest oparta na zwykłych wartościach NULL Codda . Powyższa tabela T jest przykładem tabeli Codda. Algebra tablicowa Codda obsługuje tylko projekcje i selekcje pozytywne. W [IL84 wykazano również, że nie jest możliwe prawidłowe rozszerzenie większej liczby operatorów relacyjnych na Codd-Tables. Na przykład taka podstawowa operacja, jak łączenie, nie może zostać rozszerzona na tabele Codda. Nie jest możliwe zdefiniowanie selekcji z warunkami boolowskimi obejmującymi negację i zachowanie kompletności. Na przykład zapytania takie jak powyższe zapytanie Q nie mogą być obsługiwane. Aby móc rozszerzyć więcej operatorów relacyjnych, potrzebna jest bardziej wyrazista forma reprezentacji wartości zerowej w tablicach zwanych V-tabelami.

Algebra tablic V

Algebra tabel V jest oparta na wielu różnych („oznaczonych”) wartościach zerowych lub zmiennych, które mogą pojawiać się w tabeli. V-tabele pozwalają pokazać, że wartość może być nieznana, ale taka sama dla różnych krotek. Na przykład w poniższej tabeli Gaurav i Igor zamawiają to samo (ale nieznane) piwo w dwóch nieznanych barach (które mogą, ale nie muszą być różne – ale pozostają nieznane). Gaurav i Jane często odwiedzają ten sam nieznany bar (Y1). Dlatego zamiast jednej wartości NULL używamy zmiennych indeksowanych, czyli stałych Skolema .

PIJĄCY	PIWO	BAR
Zhihan	Heinekena	Kabina
Gaurav	X1	Y1
Igor	X1	Y2
Jane	Pączek	Y1
Jan	X2	Y3

Pokazano, że algebra tabel V poprawnie obsługuje projekcję, selekcję pozytywną (bez negacji występującej w warunku selekcji), łączenie i zmianę nazw atrybutów, co pozwala na przetwarzanie dowolnych zapytań koniunkcyjnych. Bardzo pożądaną właściwością algebry V-tablicowej jest to, że wszystkie operatory relacyjne na tablicach są wykonywane dokładnie tak samo, jak w przypadku zwykłych relacji.

Tablice warunkowe (c-tablice) algebra

Przykład tabeli warunkowej (c-table) pokazano poniżej.

NAZWA	KLASA	STOPIEŃ	SEMESTR	kon
Rohit	Bazy danych	B	Wiosna	PRAWDA
Igor	Sieci	A	X	x = „Wiosna”
Igor	Sieci	A	X	x <> „Wiosna”

Posiada dodatkową kolumnę „con”, która jest warunkiem boolowskim obejmującym zmienne, wartości null – tak samo jak w V-tabelach.

 
   
                 WYBIERZ  *  Z  T  GDZIE  (  KLASA  =  „Sieci”  I  SEMESTR  =  „Wiosna”  )  LUB  (  KLASA  =  „A”  I  SEMESTR  <>  „Wiosna”  ) 

w poniższej tabeli c-table

T1=

NAZWA	KLASA	STOPIEŃ	SEMESTR	kon
Rohit	Bazy danych	B	Wiosna	PRAWDA
Igor	Sieci	A	X	PRAWDA

Algebra tablic warunkowych, głównie o znaczeniu teoretycznym, obsługuje projekcję, selekcję, łączenie, łączenie i zmianę nazwy. Przy założeniu świata zamkniętego może również obsługiwać operatora różnicy, a zatem może obsługiwać wszystkie operatory relacyjne.

Historia

Algebry Imielińskiego – Lipskiego zostały wprowadzone przez Tomasza Imielińskiego i Witolda Lipskiego Jr. w Incomplete Information in Relational Databases .

Dalsza lektura

• Abiteboul, S .; Kanellakis, P.; Grahne, G. (1991). „O reprezentacji i zapytaniu o zbiory możliwych światów” (PDF) . Informatyka teoretyczna . 78 (1): 159–187. doi : 10.1016/0304-3975(51)90007-2 .
•   Abiteboul, S.; Duschka, OM (1998). „Złożoność odpowiadania na zapytania przy użyciu zmaterializowanych widoków”. proc. ACM SIGMOD-SIGACT-SIGART, PODS : 254–263. CiteSeerX 10.1.1.92.2956 .
• Zielony, TJ; Karvounarakis, G.; Tannen, Val (2007). „Semiring pochodzenia” . proc. ACM SIGMOD-SIGACT-SIGART, PODS : 31–40.
•   Karvounarakis, G.; Zielony, TJ (2012). „Dane z adnotacjami Semiring: zapytania i pochodzenie” (PDF) . SIGMOD ACM . 41 (3): 5–14. doi : 10.1145/2380776.2380778 . S2CID 11600847 .
• TJ Zielony (2009). Modele informacji niekompletnych i probabilistycznych; Rozdział 2, w Zarządzanie i eksploracja niepewnych danych . Link Springera.
• Grahne, G.; Kiricenko, V. (listopad 2004). „Ku algebraicznej teorii integracji informacji” (PDF) . Informacja i obliczenia . 194 (2): 79–100. doi : 10.1016/j.ic.2004.07.003 .