Anali PAZU - Letnik 1, leto 2011, številka 1 
 
1 
 
L-relacijska algebra 
L-relational algebra 
Melita Hajdinjak 
 
Univerza v Ljubljani, Fakulteta za elektrotehniko / Tržaška cesta 25, 1000 Ljubljana 
E-Mail: melita.hajdinjak@fe.uni-lj.si 
* Avtor za korespondenco; Tel.: +386-1-4768-385; Fax: + 386-1-4768-316 
 
Povzetek: V članku se osredotočimo na pozitivni K-relacijski model za označene relacije, v katerem U-
tericam prirejamo elemente izbranega komutativnega polkolobarja K. Predlagamo uvedbo nove operacije v K, 
imenovane negacija, ki omogoča definicijo razlike K-relacij, tj. edine osnovne relacijske operacije, ki v 
pozitivni K-relacijski algebri manjka. Obstoj negacije zagotavljajo posebne mreže, imenovane De Morganovi 
okvirji. Zahteva, da naj bo K De Morganov okvir, ima še en pozitiven učinek   ̶ v dobljeni L-relacijski algebri 
veljajo vse (pozitivne) relacijske identitete, ki jih poznamo iz klasične relacijske algebre, tudi tiste, ki v K-
relacijski algebri ne veljajo.  
Ključne besede: K-relacija; L-relacija; negacija; De Morganov okvir; relacijska algebra 
Abstract: In this article we focus on the positive K-relation model for annotated relations in which each U-
tuple is mapped to an element of a commutative semiring, K. We propose a new operation in K, called 
negation, which induces a difference operation on K-relations, i.e., the only basic relational operation not 
interpreted in the positive K-relational algebra. Because we cannot define negation in all semirings, we move 
from the commutative semirings to the De Morgan frames, a lattice structure with negation. This has another 
positive consequence – the obtained L-relational algebra satisfies all the classical relational identities, 
including those that are not satisfied by the positive K-relational algebra. 
Keywords: K-relation; L-relation; negation; De Morgan frame; relational algebra 
 
1. Uvod 
Predpostavimo, da imamo na razpolago neke osnovne 
domene oziroma množice elementov, ki jih bomo 
označevali s τ. Primera sta množica naravnih števil in 
množica nizov. Naj bo shema  
{ }
1 1
: , , :
n n
U a a τ τ = … 
preslikava, ki atributu a
i
 priredi domeno 
i
τ , torej 
( )
i i
U a τ =
 
za 1, , i n = … . Naj bo U-terica 
{ }
1 1
: , , :
n n
t a v a v = … 
preslikava, ki atributu 
i
a priredi element 
i i
v τ ∈ , torej 
( )
i i
t a v = za n i , , 1… = . Množico vseh U-teric imenujmo 
Tup − U . Označena relacija nad U bomo imenovali 
preslikavo oblike : T up A U K − → , ki vsaki U-terici 
priredi nek element izbrane domene K. Klasična relacija, ki 
jo običajno pojmujemo kot množico U-teric in jo 
predstavimo s tabelo, je poseben primer označene relacije. 
Dobimo jo, če izberemo K = {0,1} in definiramo ( ) 1 A t = , 
če t A ∈ , ter ( ) 0 A t = sicer.  
Naj bo sedaj K poljuben polkolobar, torej algebrajska 
struktura ( ) , ,*,0,1 K K = + z dvema dvomestnima 
operacijama (+ in *) ter različnima elementoma 0 in 1, tako 
da velja naslednje: 

 ( ) , ,0 K + je komutativen monoid z enoto 0, 

 ( ) ,*,1 K je monoid z enoto 1, 

 produkt (*) je distributiven glede na vsoto (+) in  

 za vsak a K ∈ velja 0* *0 0. a a = =  

Anali PAZU - Letnik 1, leto 2011, številka 1 
 
2 
 
Polkolobar K imenujemo komutativen, če je 
komutativen monoid ( ) ,*,1 K .  
V članku se bomo osredotočili na tako imenovane K-
relacije in pozitivno K-relacijsko algebro [1], katerih 
namen je modelirati različne oblike označenih relacij.  
2.  Relacijska algebra na K-relacijah 
Green, Karvounarakis in Tannen [1] so predlagali 
naslednjo razširitev klasičnih relacij.  
Definicija 1. [K-relacija] Naj bo ( ) , ,*,0,1 K K = + 
komutativen polkolobar. K-relacija nad U, kjer je 
{ }
1 1
: , , :
n n
U a a τ τ = … relacijska shema, je označena 
relacija : T up A U K − → , ki ima končen nosilec, tj.  
{ } supp( ) : ( ) 0 A t A t = ≠ 
je končna množica. 
Definicija 2. [Pozitivna K-relacijska algebra] Naj bo 
( ) , ,*,0,1 K K = + komutativen polkolobar. Operacije 
pozitivne K-relacijske algebre so naslednje: 

 Prazna relacija: Za vsako shemo U imamo 
prazno K-relacijo Ø: Tup U K − → , za katero za 
vsak t velja  
 Ø(t) = 0. 

 Unija: Če sta , : Tup A B U K − → , potem je unija 
: Tup A B U K ∪ − → definirana kot  
( )( ) ( ) ( ). A B t A t B t ∪ = + 
• Projekcija: Če je : T up A U K − → in je V 
podmnožica množice U, je projekcija 
: Tup
V
A V K π − → definirana kot  
( )
' in ( ') 0
( )  ( '),
V
t V t A t
A t A t π
↓ = ≠
=
∑
 
 kjer je ' t V ↓ skrčitev U-terice t' na 
 domeno V. 

 Izbira: Če je : T up A U K − → in predikatna 
funkcija P slika U-terico v 0 ali 1, potem je izbira 
: Tup A U K σ − →
P
definirana kot  
( )
P
( ) ( )* ( ). A t A t t σ = P 

 Stik: Če sta 
1
: Tup A U K − → in 
2
: Tup B U K − → , potem je njun stik
1 2
: A B U U K ⊗ ∪ → definiran kot  
( )
1 2
( ) ( ) * ( ). A B t A t U B t U ⊗ = ↓ ↓ 

 Preimenovanje: Če je : T up A U K − → in je
: ' U U β → bijektivna preslikava, potem 
definiramo preimenovano K-relacijo
: ' Tup A U K
β
ρ − → kot  
( )( ) ( ). A t A t
β
ρ β =  
K-relacijska algebra posplošuje številne predloge 
modelov označenih relacij. Če za K izberemo Boolov 
(pol)kolobar, dobimo klasično relacijsko algebro, če 
izberemo polkolobar celih števil, dobimo algebro na vrečah 
[2], če izberemo ustrezni polkolobar na končni množici 
dogodkov, dobimo Fuhr-Rölleke-Zimányi verjetnostno 
algebro [3], če izberemo polkolobar c-tabel, dobimo 
Imielinksi-Lipski algebro [4], in če izberemo provenienčni 
polkolobar, dobimo provenienčno algebro [1].   
V Definiciji 2 manjka ena osnovna relacijska operacija 
‒ razlika.  Green, Karvounarakis in Tannen [1] so ta 
(negativni) del pustili odprt, saj v komutativnih 
polkolobarjih niso znali definirati ustrezne operacije, ki bi 
posplošila razliko, kot jo poznamo v klasični relacijski 
algebri [5].  Pozneje sta Geerts in Poggi [6] predlagala, da 
bi razliko definirali kot monus, zaradi česar bi bilo treba 
(komutativne) polkolobarje skrčiti na (komutativne) 
polkolobarje z monusom, imenovane m-polkolobarji. A ta 
definicija razlike označenih relacij se je izkazala za 
neustrezno v primeru mehkih polkolobarjev in mehkih 
relacijskih algeber [7].  
Izrek 1. [Identitete na K-relacijah] Pozitivna K-relacijska 
algebra ima naslednje lastnosti: 

 unija je asociativna in komutativna operacija z 
enoto Ø, 

 izbira je distributivna glede na unijo in stik, 

 stik je asociativna in komutativna operacija, ki je 
distributivna glede na unijo, 

 projekcija je distributivna glede na unijo in stik,  

 izbira in projekcija komutirata,  

 če je P(t) = 1 za vse t, je 
P
A A σ = , in če je  P(t) = 
0 za vse t, je 
P
A σ = Ø,  

 stik s prazno relacijo je prazna relacija,  

 projekcija prazne relacije je prazna relacija. 
V pozitivni K-relacijski algebri pa ne velja A A A ∪ =
in A A A ⊗ = . Unija in samostik sta sicer idempotenta v 

Anali PAZU - Letnik 1, leto 2011, številka 1 
 
3 
 
klasičnem modelu [5], ne pa tudi v provenienčni algebri [1] 
in algebri na vrečah [2].  
3.  Relacijska algebra na L-relacijah 
Najprej predlagamo manjšo posplošitev predikatne 
funkcije iz pozitivnega K-relacijskega modela, potem pa se 
osredotočimo na problem definicije razlike označenih 
relacij. S komutativnih polkolobarjev K preidemo na De 
Morganove okvirje L, ki vsebujejo negacijo, s pomočjo 
katere definiramo razliko dobljenih L-relacij. Na ta način 
dosežemo tudi veljavnost vseh (pozitivnih) relacijskih 
identitet, ki jih poznamo iz klasičnega relacijskega modela. 
3.1. Predikatna funkcija 
Namesto da bi se omejili le na 0 (neizpolnjevanje 
pogoja) in 1 (popolno izpolnjevanje pogoja), kot so to 
naredili Green, Karvounarakis in Tannen [1], bomo 
dovolili tudi druge vrednosti predikatne funkcije P, ki bodo 
odražale različne stopnje pripadnosti oziroma 
izpolnjevanja pogoja.  
Definicija 3. [Posplošena izbira]  Predikatna funkcija 
: Tup U K − → P naj U-terico slika v poljubni element 
komutativnega polkolobarja K.  

 Izbira: Če je : T up A U K − → in 
: Tup U K − → P , izbiro : Tup A U K σ − →
P
 
definiramo kot  
( )
P
( ) ( )* ( ). A t A t t σ = P 
V nadaljevanju, ko bomo govorili o pozitivni K-
relacijski algebri, bomo mislili to posplošitev.  
Naš cilj je v splošen model označenih relacij dodati 
tudi mehke relacije [7]. V mehkih relacijah so U-terice 
največkrat označene z Boolovima vrednostma (0 in 1), z 
vrednostmi z enotskega intervala [0,1] ali z vrednostmi s 
kompaktificiranega intervala [0,∞]. Vsaka izmed teh 
množic značk tvori komutativen polkolobar:    
 

  Boolov polkolobar je { } ( ) 0,1 , , ,0,1 , K= ∨∧ 

 mehki polkolobar je [ ] ( ) 0,1 ,max,min,0,1 , K= 

 polkolobar razdalj je  
[ ] ( ) 0, ,min,max, ,0 . K= ∞ ∞ 
Z elementi komutativnega polkolobarja lahko izražamo 
podobnost U-teric. Tako z največjim elementom 1 
izrazimo največjo podobnost (enakost), z najmanjšim 
elementom 0 pa najmanjšo podobnost (različnost). V 
polkolobarju razdalj smo interval [0, ∞] obrnili, tako da 0 
pomeni največjo podobnost oziroma najmanjšo razdaljo, ∞ 
pa najmanjšo podobnost oziroma največjo (nepremostljivo) 
razdaljo.    
3.2. Razlika 
Razliko označenih relacij bomo definirali s pomočjo 
negacije.  
Definicija 5. [Negacija] Operacijo : L L ¬ → na delno 
urejeni množici L, ki obrača urejenost ( x y y x ≤ ⇒¬ ≤¬ ) 
in je involutivna ( x x ¬¬ = ), imenujemo negacija. 
Komutativni polkolobar, ki je delno urejen in ima negacijo, 
imenujemo n-polkolobar.  
Definicija 6. [Razlika] Naj bo L = (L,+,*,0,1,¬) n-
polkolobar.  

 Razlika: Če sta , : Tup A B U L − → , potem je 
razlika : Tup A B U L − − → definirana kot  
( )( ) ( )* ( ). A B t A t B t − = ¬ 
Poglejmo, kakšno definicijo razlike dobimo v nekaterih 
primerih: 

 V Boolovem n-polkolobarju dobimo 
( )( ) 0, A B t − = če je ( ) 1, B t = in 
( )( ) ( ), A B t A t − = če je ( ) 0. B t =  

 V mehkem n-polkolobarju dobimo 
( ) { } ( ) min ( ),1 ( ) , A B t A t B t − = − kar se ujema s 
klasično definicijo razlike mehkih relacij [7].  

 V n-polkolobarju razdalj dobimo 
( )( ) ( ), A B t A t − = če je ( ) , B t =∞ 
( ) { } ( ) max ( ),1/ ( ) , A B t A t B t − = če je ( ) B t ≠∞ 
in ( ) 0 B t ≠ , in ( )( ) , A B t − =∞ če je ( ) 0 B t = .  

 V n-polkolobarju na končni množici dogodkov 
dobimo ( ) ( ) ( ) ( ) ( ) A B t A t B t − = ∩ Ω− , kar se 
ujema z definicijo razlike v Fuhr-Rölleke-
Zimányi verjetnostni algebri [3].  

 V n-polkolobarju c-tabel dobimo 
( )( ) ( ) ( ) A B t A t B t − = ∧¬ , kar se ujema z razliko 
v Imielinksi-Lipski algebri [4].                    
Z uvedbo negacije in prehodom na n-polkolobarje smo 
sicer zagotovili obstoj razlike na mehkih relacijah, na 
verjetnostnih relacijah in v Imielinksi-Lipski algebri, ne pa 
tudi v provenienčni algebri in algebri na vrečah.  

Anali PAZU - Letnik 1, leto 2011, številka 1 
 
4 
 
 
3.3. L-relacije 
Opazimo, da so Boolov polkolobar, mehki polkolobar, 
polkolobar razdalj, verjetnostni polkolobar in polkolobar 
na c-tabelah vsi polne mreže z operacijo supremum 
definirano kot + in operacijo infimum definirano kot *. 
Obe operaciji na mrežah sta idempotentni. Znan primer 
polnih mrež z negacijo so De Morganovi okvirji. Tako 
imenujemo polno mrežo ( ) , , ,0,1, L L = ∨∧ ¬ z negacijo, v 
kateri so končni infimumi distributivni glede na 
supremume. Vse prej omenjene polne mreže so tudi De 
Morganovi okvirji.   
Definicija 7. [L-relacija] Naj bo ( ) , , ,0,1, L L = ∨∧ ¬ De 
Morganov okvir. L-relacija nad U, kjer je 
{ }
1 1
: , , :
n n
U a a τ τ = … relacijska shema, je označena 
relacija : Tup A U L − → . 
Ker v polnih mrežah obstaja supremum poljubne množice, 
obstaja tudi projekcija L-relacij. Zaradi tega sedaj ne 
zahtevamo, da je nosilec L-relacij končen.  
Definicija 8. [L-relacijska algebra] Naj bo 
( ) , , ,0,1, L L = ∨∧ ¬ De Morganov okvir. Operacije L-
relacijske algebre so naslednje: 

 Prazna relacija: Za vsako shemo U imamo 
prazno L-relacijo Ø: Tup U L − → , za katero za 
vsak t velja  
 Ø(t) = 0. 

 Unija: Če sta , : Tup A B U L − → , potem je unija 
: Tup A B U L ∪ − → definirana kot  
( )( ) ( ) ( ). A B t A t B t ∪ = ∨ 
• Projekcija: Če je L U A → − Tup : in je V 
podmnožica množice U, je projekcija 
: Tup
V
A V L π − → definirana kot  
( )
' in ( ') 0
( ) ( '),
†
V
t V t A t
A t A t π
↓ = ≠
= 
 kjer je ' t V ↓ skrčitev U-terice t' na domeno V. 

 Izbira: Če je : Tup A U L − → → in predikatna 
funkcija : Tup U L − → P , potem je izbira 
: Tup A U L σ − →
P
definirana kot  
( )
P
( ) ( ) ( ). A t A t t σ = ∧P 

 Stik: Če sta 
1
: Tup A U L − → in 
2
: Tup B U L − → , potem je njun stik
1 2
: A B U U L ⊗ ∪ → definiran kot  
( )
1 2
( ) ( ) ( ). A B t A t U B t U ⊗ = ↓ ∧ ↓ 

 Preimenovanje: Če je : Tup A U L − → in je
: ' U U β → bijektivna preslikava, potem 
definiramo preimenovano L-relacijo
: ' Tup A U L
β
ρ − → kot  
( )( ) ( ). A t A t
β
ρ β =  

 Razlika: Če sta , : Tup A B U L − → , potem je 
razlika : Tup A B U L − − → definirana kot  
( )( ) ( ) ( ). A B t A t B t − = ∧¬ 
Ker sta infimum in supremum idempotentni operaciji v 
mrežah, sta idempotentna tudi unija in (samo)stik L-relacij. 
Spomnimo se, da to ni veljalo za K-relacije. Posledično v 
L-relacijski algebri veljajo vse (pozitivne) relacijske 
identitete.  
Izrek 2. [Identitete na L-relacijah] L-relacijska algebra ima 
naslednje lastnosti: 

 unija je asociativna, komutativna in idempotentna 
operacija z enoto Ø, 

 izbira je distributivna glede na unijo in stik, 

 stik je asociativna, komutativna in idempotentna 
operacija, ki je distributivna glede na unijo, 

 projekcija je distributivna glede na unijo in stik,  

 izbira in projekcija komutirata,  

 če je P(t) = 1 za vse t, je 
P
A A σ = , in če je  P(t) = 
0 za vse t, je 
P
A σ =  Ø,  

 stik s prazno relacijo je prazna relacija,  

 projekcija prazne relacije je prazna relacija. 
Identitete na L-relacijah, ki vključujejo tudi razliko, so 
podane in dokazane v [9]. 
4. Zaključki 
Z uvedbo negacije v komutativne polkolobarje smo 
znali definirati tudi razliko označenih relacij. Pokazali 
smo, da se tako definirana razlika ujema z razliko, kot jo 
poznamo v klasični relacijski algebri, v mehkih relacijskih 
algebrah, v verjetnostni relacijski algebri in v relacijski 
algebri na c-tabelah.  Pri tem smo komutativne 
polkolobarje K zamenjali z De Morganovi okvirji L in 

Anali PAZU - Letnik 1, leto 2011, številka 1 
 
5 
 
prešli s K-relacij na L-relacije. V dobljeni L-relacijski 
algebri veljajo vse (pozitivne) relacijske identitete, ki jih 
poznamo iz klasične relacijske algebre, tudi tiste, ki v K-
relacijski algebri niso veljale.  
Na žalost pa naša L-relacijska algebra ne posplošuje 
niti prevenienčne algebre niti relacijske algebre na vrečah; 
ta dva primera ne vsebujeta negacije. V nadaljnjem delu se 
zato nameravamo posvetiti temu problemu. Poiskali bi radi 
splošnejši pojem razlike označenih relacij ali pa poskušali 
provenienco obravnavati na drugačen način.    
Literatura 
1. Green, T.J.; Karvounarakis, G.; Tannen, V. 
Provenance semirings. Proceedings of the 26th ACM 
SIGMOD-SIGACT-SIGART Symposium on 
Principles of Database Systems, Peking, Kitajska. 
2007, 31-40.  
2. Montagna, F.; Sebastiani, V.  Equational Fragments 
of Systems for Arithmetic. Algebra Universalis 2001, 
46 (3), 417-441. 
3. Suciu, D.  Probabilistic databases. SIGACT News 
2008, 39 (2), 111-124. 
4. Imielinski, T.; Lipski, W. Incomplete information in 
relational databases. Journal of the ACM 1984, 31 
(4), 761-791. 
5. Ullman, J.D.  Principles of Database and Knowledge-
Base Systems, Volume I; Publisher: Computer 
Science Press, Inc., 1988.  
6. Geerts, F.; Poggi, A.  On Database Query Languages 
for K-relations. Journal of Applied Logic 2010, 8, 
173-185. 
7. Buckles, B.P.; Petry, F.  A fuzzy Representation of 
Data for Relational Databases. Fuzzy Sets and 
Systems 1982, 7, 213-226. 
8. Hajdinjak, M.; Bauer, A.  Similarity Measures for 
Relational Databases. Informatica 2009, 33 (2), 135-
141. 
9. Hajdinjak, M.; Bierman, G.  Extending the Relational 
Algebra with Similarities. Poslano v Mathematical 
Structures in Computer Science 2011.