Matematika | Felsőoktatás » Tichler Krisztián - Kombinatorikus problémák az adatbázisok elméletében

SZAKDOLGOZAT Kombinatorikus problemak az adatbazisok elmeleteben 1998 Irta: Tichler Krisztian Temavezet}o: Katona Gyula Tartalomjegyzek 1. Bevezetes : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3 2. Alaptulajdonsagok : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5 3. Direkt szorzatok reprezentacioja : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11 4. s(Lnk ) nagysagrendje : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16 5. s(Lnk ) meghatarozasa k nehany ertekere : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 20 6. Egy kulcsrendszer reprezentacioja : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 23 Hivatkozasi jegyzek : : : : : : : : : : : : : : : : :

: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 33 2 1.Bevezetes Egy adatbazis legegyszer}ubb modellje egy matrix. Egy-egy oszlopban azonos fajta adatok szerepelnek (peldaul nev, szuletes ideje, szuletes helye, stb.), mg a kulonboz}o sorokban a kulonboz}o egyenek adatai. Egy bizonyos fajta adatokat (az irodalomban hasznalatos elnevezessel) attributumnak nevezunk, mely azonosthato a fenti matrix egy oszlopaval. Az attributumok halmazat  = fa1  a2  : : :  an g-nel fogjuk jelolni. A lehetseges ertekek halmazat az i-edik oszlopban ai ertekkeszletenek nevezzuk, es D(ai )-vel jeloljuk. Igy tehat egy egyen adatait (a matrix egy sorat) tekinthetjuk a D(a1 )  D(a2 )  : : :  D(an ) direkt szorzat egy elemenek (n-esenek). Ezert az egesz adatbazis (vagy matrix) lerhato az r  D(a1 )  D(a2 )  : : :  D(an ) relacioval, azaz az n-esek halmazaval. Ennek a modellnek a neve relacios adatbazis modell.

Az adatok kozott fennallhatnak bizonyos logikai osszefuggesek. Peldaul a szuletes datuma meghatarozza a kort (egy adott evben), vagy a vezeteknev es a keresztnev meghatarozza a monogramot. Azt mondjuk, hogy egy attributum (funkcionalisan) fugg attributumok egy halmazatol, ha az azokban felvett ertekek egyuttesen egyertelm}uen meghatarozzak az ottani erteket. A funkcionalis fugg}oseg fogalmat W.W ARMSTRONG es EF CODD vezettek be Formalisan: 1.1 Denicio 1],5] Legyen A B   Azt mondjuk, hogy B funkcionalisan fugg A-tol, ha tetsz}oleges b 2 B eseten nem letezik r-nek 2 sora (n-ese), melyek A oszlopaiban (attributumaiban) megegyeznek, de b-ben kulonboznek. Ennek jelolese: A ! B. A funkcionalis fugg}osegek nagyon hasznosnak bizonyultak. Valamennyi adatbazist m}ukodtet}o rendszer ezen a koncepcion alapul Tekintsuk a kovetkez}o peldat Tegyuk fel, hogy  = fa1  a2 a3  a4 g es a1 ! a2 valamint a3 ! a4 . Ha a teljes matrixot

taroljuk a szamtogep memoriajaban, akkor a legrosszabb esetben 4N1 N3 regiszterre van szukseg, ahol Ni = jD(ai )j (i = 1 3). Valoban, a1 es a3 egymastol fuggetlenul vehetnek fel ertekeket, de ezek meghatarozzak a2 -t es a4 -et. Igy a kulonboz}o sorok szama legfeljebb N1N3 . Azonban az adott funkcionalis fugg}osegek hasznalataval szamottev}o memoriat takarthatunk meg. Valoban, elegend}o az a1 es a3 oszlopaibol allo matrixot (2N1N3 regiszter) valamint ket kis matrixot tarolni. Az egyik a1 es a2 ertekeib}ol all az els}o illetve masodik oszlopban. Az els}o osz3 lop tartalmazza a1 lehetseges ertekeit, mg a masodik az a1 ! a2 fugg}oseg altal meghatarozott ertekeket. A masik kis matrix a3 -bol es a4 -b}ol ugyangy epul fel A tarolt ertekek szama legfeljebb 2N1N3 + 2(N1 + N3), ami altalaban szignikansan kisebb 4N1N3 -nal. A szakdolgozat celja megvizsgalni a fukcionalis fugg}oseg tulajdonsagait. Ennek

soran szamos erdekes kombinatorikai problema merul fel. A 2 fejezet megismerteti az olvasot a temakor fogalmaival es problemaival. A 3 fejezet direkt szorzatok, a 4. es 5 fejezet a gyakran vizsgalt Lnk lezarascsalad minimalis reprezentaciojaval foglalkozik. A 6 fejezet uj eredmenye egy uj tpusu kulcsrendszercsalad minimalis reprezentaciojat vizsgalja. 4 2. Alaptulajdonsagok Ebben a fejezetben a legfontosabb deniciok es nehany egyszer}ubb, de alapvet}o tetel kerul targyalasra. Legyen  = fa1  a2  : : :  an g 2.1 Denicio 17] Az  halmaz reszhalmazaibol allo A ,! B parok egy D rendszeret determinacionak nevezzuk, ha  barmely A B C D reszhalmazara A ,! A (2:1) A ,! B B ,! C ) A ,! C (2:2) A  C D  BA ,! B ) C ,! D (2:3) A ,! B C ,! D ) A  B ,! C  D: (2:4) Konnyen lathato, hogy egy r relacio (adatbazis) osszes A ! B funkcionalis fugg}osegei determinaciot alkotnak  reszhalmazain. 2.2 Denicio 1] Egy

r relacio osszes funkcionalis fugg}oseget teljes csaladnak nevezzuk. 2.3 Tetel 1] Az A ,! B parok egy rendszere teljes csalad akkor es csak akkor ha determinacio. 2.4 Denicio Egy L halmazfuggvenyt lezarasi operacionak vagy roviden lezarasnak nevezunk  reszhalmazain, ha minden A B  -ra A  L(A) (2:5) A  B )L(A)  L(B) (2:6) L(L(A)) = L(A): (2:7) 2.5 A lltas 17] Egy adott  halmazon letezik bijekcio a determinaciok halmaza es a lezarasok halmaza kozott. Bizonytas: Ha adott egy D determinacio -n, akkor denialjuk az L(D) halmazfuggvenyt: L(A) = faj A ,! ag minden A  -ra. Konnyen lathato hogy L(D) lezaras, valamint hogy D ;! L(D) injekcio. 5 Fordtva, ha adott egy L lezaras, akkor D(L) alljon azon A ,! B parokbol, melyre B  L(A). Konnyen lathato, hogy D(L) determinacio, es most is L ;! D(L) injekcio. Mivel  veges halmaz, ezert mindket injekcio valojaban bijekcio. Tovabbi bijekciok is megadhatok

a determinaciok halmazaval (peldaul a metszet-felhalokkal vagy a metszetmentes halmazcsaladokkal) 4],9],12],17]. 2.6 Denicio K   kulcs, ha K ,!  minimalis kulcs, ha minimalis a tartalmazasra, mint reszbenrendezesre nezve a kulcsok kozott A   antikulcs, ha nem kulcs maximalis antikulcs, ha maximalis a tartalmazasra, mint reszbenrendezesre nezve az antikulcsok kozott. Azaz egy r relacio eseten K kulcs, ha a K -beli ertekek meghataroznak minden mas erteket is. Egy L lezaras (vagy D determinacio, stb.) meghatarozza a minimalis kulcsok K = K(L) (vagy K = K(D)) csaladjat. Ez nyilvan egy nem-ures Sperner-rendszer (egy S halmazrendszer Sperner ha tartalmazasmentes, vagyis ha A B 2 S ) A 6 B) Fordtva, ha adott egy K nem-ures Sperner-rendszer, akkor nincs olyan K 2 K, melyre K  A L(A) = A ha ha van olyan K 2 K, melyre K  A lezaras, es a minimalis kulcsok halmaza eppen K. (2:8) 2.7 A lltas 17] Barmely nem-ures K

Sperner-rendszerhez letezik olyan r relacio, melyben a minimalis kulcsok halmaza K Bizonytas: Az alltas kovetkezik a 2.3 Tetelb}ol es a 25 A lltasbol valamint (2.8)-bol Termeszetesen K nem hatarozza meg L-et egyertelm}uen. 2.8 Denicio A Dkn determinacio alljon azon A ,! B parokbol melyekre B  A  , valamint azon A ,! B parokbol melyekre A B   es jAj k. Ennek megfelel az jAj < k, Lnk = L(Dkn ) = A ha ha jAj k, A   ; (2:9) lezaras. Kkn = K(Lnk ) = k pedig az  alaphalmaz k elem}u reszhalmazainak csaladja. 6 2.9 Tetel 6] A minimalis kulcsok szama legfeljebb ;bnn2 c, es ez eles Bizonytas: Az egyenl}otlenseg konnyen kovetkezik E. SPERNER ; teteleb}ol 21], mely szerint minden S tartalmazasmentes halmazrendszerre jSj bnn2 c . Most tekintsuk Dbnn=2c -et. A 23 Tetel szerint van olyan r relacio, melynek teljes n . Nyilvanvalo, hogy a minimalis kulcsok halmaza ebben a relacioban csaladja Dbn= 2c   n Kbn=2c ,

azaz  n2 elem}u reszhalmazai. Tehat az egyenl}otlenseg nem javthato 2.10 Lemma (YBLM-egyenl}otlenseg, 22],3],19],20]) Ha S Sperner-rendszer egy n elem}u alaphalmazon es fi az i elem}u tagok szama, akkor n f X ;ni 1: (2:10) i=0 i 2.11 Tetel 17] Tegyuk fel, hogy az A ! B funkcionalis fugg} ;nosegekre jB ; Aj k, ahol k n=2. Ekkor a minimalis kulcsok szama legfeljebb k Bizonytas: A feltetel miatt a kulcsok merete legalabb n ; k. Alkalmazzuk a 2.10 Lemmat, ahol a Sperner-rendszer a minimalis kulcsok halmaza Ekkor f0 = f1 = : : : = fn;k;1 = 0. Felhasznalva, hogy n  n  i n ; k ha k n=2 n ; k i n kapjuk (2.10)-b}ol, hogy 1 n f X ;ni i=n;k i n X ; fni  = ; n1  i=n;k n;k n X n;k i=n;k fi = ; jSj n  n;k amib}ol a tetel kovetkezik. A fentiekb}ol tudjuk, hogy barmely D determinaciohoz, L lezarashoz, vagy K minimalis kulcsok rendszerehez letezik olyan r relacio, hogy r eppen az adott D-t, L-t, illetve K-t generalja. Ekkor azt

mondjuk, hogy r (vagy a neki megfelel}o M matrix) reprezentalja }oket. Nem vilagos azonban, hogy mekkora a fentieket reprezentalo relaciok kozul jrj minimuma, mas szoval hany sora van a fentieket generalo legkevesebb sorral rendelkez}o matrixnak. Jelolje ezeket a minimumokat s(D), s(L), illetve s(K). 7 2.12 Tetel 6],8] Egy adott  n-elem}u alaphalmazon     1 n < maxfs(K)j K 6= Sperner -ng 1 + n : n K n2 n2 2 (2:11) Az els}o egyenl}otlenseg bizonytasa nem konstruktv, mivel nem ismerjuk a (kozel) legrosszabb Sperner-rendszereket. Egy lehetseges jelolt Kbnn=2c Ez az egyik motivacioja s(Lnk ) vizsgalatanak. Ugyanis a kovetkez}o lemma miatt ez ekvivalens s(Kkn ) vizsgalataval, mivel a ket szam megegyezik. 2.13 Lemma 7] Legyen L az n-elem}u  alaphalmaz egy tetsz}oleges lezarasa Ekkor K(L) = Kkn , L = Lnk : (2:12) Bizonytas: Nyilvan K(Lnk ) = Kkn. A masik iranyhoz eleg belatni, hogy L(A) = A, ha A   jAj < k,

ugyanis ekkor L(A) =  jAj k konnyen kovetkezik K(L) = Kkn -b}ol es (2.6)-bol Legyen tehat a 2 L(A)nA Ekkor letezik egy olyan B halmaz melyre jBj = k B  A  fag. (25) miatt L(Bnfag)  Bnfag, mg (2.6) miatt L(Bnfag)  L(A) 3 a Ezert L(Bnfag)  B Most (26)-bol es (27)-b}ol L(Bnfag) = L(L(Bnfag))  L(B) = . Igy talaltunk egy k-nal kisebb szamossagu halmazt, aminek a lezartja . Ez az ellentmondas mutatja (25) felhasznalasaval, hogy L(A) = A. Tehat L = Lnk: A kovetkez}o lemma egyszer}usege ellenere meglep}oen er}osnek bizonyult. 2.14 Lemma 10],7] s(Ln )  n  k 2 k ; 1 (0 k n): (2:13) Bizonytas: Tegyuk fel, hogy M reprezentalja Lnk -et es legyen jAj = k ; 1  egy reszhalmaza, tovabba b 62 A. Ekkor Lnk dencioja miatt A 6! b, azaz letezik ket olyan sor (i es j ), hogy ezek megegyeznek A-n, de kulonbozik a b-beli ertekuk. Ha lenne -nak egy masik (k ; 1)-elem}u B reszhalmaza, hogy i es j megegyeznek B-n, akkor A  B 6! b allna, de

mivel jABj k, ezert Lnk denicioja miatt ez lehetetlen. Igy a kulonboz}o sorparokhoz kulonboz}o oszlop-(k ; 1)-eseket rendelhetunk. 8 Azonban lesz amikor az el}oz}o lemma nem elegend}o. A kovetkez}o lemma matrixok egy egyszer}u tulajdonsagat mutatja be Legyen M egy m  n-es matrix es G(M) jelolje a kovetkez}o grafot: a graf csucsai feleljenek meg M sorainak, es ket csucs pontosan akkor legyen osszekotve, ha azon oszlopok A halmaza, ahol a ket sor megegyezik nem-ures. Az elet cimkezzuk meg A-val 2.15 Lemma 7] Legyen M egy matrix es legyenek A1 : : :  Ar a G(M) graf egy korenek cimkei. Ekkor  Tr  Ai nAj = (1 j r): i=1 i6=j (2:14) Bizonytas: A tindexeles utan feltehet}o, hogy j = r. Indirekt tegyuk fel, hogy az u-adik oszlop eleme minden Ai -nek (1 i < r), de nem eleme Ar -nek. Legyenek a kor pontjai k1 : : :  kr ugy, hogy a (ki  ki+1) el cimkeje legyen Ai (1 i < r) es (kr  k1 ) cimkeje Ar . u 2 A1 -b}ol

kovetkezik, hogy az u-adik oszlop k1-edik es k2-edik eleme megegyezik. Hasonloan kapjuk, hogy az u-adik oszlop k2-edik es a k3-adik, : : :  a kr;1 -edik es a kr -edik eleme megegyezik. Ezert gy a k1-edik es a kr -edik elem megegyezik, tehat u 2 Ar , ami ellentmond az indirekt feltevesunknek. Ha adott a minimalis kulcsok K halmaza, akkor jelolje K;1 a maximalis antikulcsok halmazat. 2.16 Lemma 7] M reprezentalja a K Sperner-rendszert akkor es csak akkor, ha egyreszt barmely A 2 K;1-hez letezik M-nek ket kulonboz}o sora, hogy ezekben A oszlopaiban ugyanaz az ertek szerepel, masreszt ha barmely ket olyan sor, ami megegyezik K 2 K-n, megegyezik mindenutt. Bizonytas: Ha M reprezentalja K-t, akkor K = K(LM ). Ha K 2 K, akkor LM (K ) = , es a masodik feltetel nyilvan teljesul. Hasonloan, ha A 2 K;1, akkor LM (K ) 6= , es gy a masodik feltetel is kovetkezik. Fordtva, ha mindket feltetel teljesul M-re es K-ra, akkor (i) LM (A) 6= 

minden A 2 K;1-re es (ii) LM (K ) =  minden K 2 K-ra. (ii) es (2.6) szerint LM (C ) =  ha C  K valamely K 2 K-ra Tegyuk fel most, hogy C nem tartalmazza K semelyik tagjat sem. Ekkor denicio szerint letezik olyan A 2 K;1, hogy C  A. (i) es (26) miatt LM (C ) 6=  Tehat a minimalis kulcsok halmaza eppen K: 9 2.17 Lemma 7] s(K) 2 jK;1j s(K) ; 1: (2:15) Bizonytas: A masodik egyenl}otlenseget a kovetkez}o egyszer}u konstrukcio mutatja: A nulladik sor alljon csupa 0-bol, mg az i-edik sor (1 i jK;1j) 0-kbol es i-kb}ol. A nullak alljanak K;1 i-edik tagjanak oszlopaiban A masik iranyhoz legyen A 2 K;1, ekkor a 2.16 Lemma szerint van ket kulonboz}o i j sor, hogy ezek A-ban megegyeznek. Most legyen B K;1 egy masik eleme. Ha ehhez ugyanaz az (i j ) par tartozna, akkor ezek a sorok megegyeznenek A  B-n. Kovetkezeskepp L(A  B) 6=  es letezik C 2 K;1, hogy C  A  B K;1 denicioja miatt ez csak ugy lehetseges, ha C = A es C = B, ami

ellentmond az A 6= B feltetelnek. Tehat K;1 kulonboz}o elemeihez kulonboz}o sorparok rendelhet}ok, ami bizonytja az els}o egyenl}otlenseget. 10 3. Direkt szorzatok reprezentacioja Keveset tudunk s(L)-r}ol az Lnk-t}ol kulonboz}o lezarasokra. Egy eredmeny azonban ismert direkt szorzatok s-fuggvenyere 3.1 Denicio Legyen  = 1  2 az  alaphalmaz egy particioja, es legyenek L1 es L2 ket lezaras 1-n illetve 2-n. Ekkor az L1  L2 direkt szorzat de nicioja (L1  L2 )(A) = L1(A 1 )  L2(A 2 ): (3:1) s(L1  L2 ) = s(L1 ) + s(L2 ) ; 1: (3:2) 3.2 Tetel 7] Bizonytas: El}oszor egy konstrukcioval bizonytjuk az s(L1  L2 ) s(L1 ) + s(L2 ) ; 1: (3:3) egyenl}otlenseget. Reprezentaljak az s(L1 )  n1 -es M1 es az s(L2 )  n2 -es M2 matrixok az L1 illetve L2 lezarasokat. Jelolje  az M1 matrix utolso sorat, mg  az M2 matrix els}o sorat. Denialjuk az (s(L1 ) + s(L2 ) ; 1)  (n1 + n2)-es M matrixot a kovetkez}okeppen: 1 2  .

M1 .     . . M2  11 Megmutatjuk, hogy ez a matrix reprezentalja L1  L2 -t, azaz a 2 LM (A) , a 2 L1(A 1 )  L2 (A 2): (3:4) A szimmetria miatt feltehetjuk, hogy a 2 1. Ekkor a (34) feltetel ket implikaciora bonthato: a 2 L1 (A 1) ) ha M ket sora megegyezik A-ban, akkor a-ban is, (3:5) a 62 L1 (A 1) ) M ket sora megegyezik A-ban, de kulonbozik a-ban: (3:6) (3.5) bizonytasahoz tegyuk fel, hogy a 2 L1 (A 1), es valasszuk ki M ket olyan sorat, melyek megegyeznek A-ban. Ha mindkett}o -val kezd}odik, akkor termeszetesen megegyeznek a-ban. Ha legalabb az egyik nem -val kezd}odik, akkor ezeknek a soroknak az els}o fele M1 -nek ket kulonboz}o sora, gy tehat ha megegyeznek A 1-ben, akkor megegyeznek a-ban is. (3.6) bizonytasahoz tegyuk fel, hogy a 62 L1 (A 1) M1 tartalmaz ket sort, melyek megegyeznek A 1-ben, de kulonboznek a-ban. Ezek a sorok ugyanugy folytatodnak, tehat megegyeznek A-ban. Tehat M reprezentalja L1  L2

-t, gy (3.3)-t bebizonytottuk Most ket lemma segtsegevel bebizonytjuk a s(L1  L2 ) s(L1 ) + s(L2 ) ; 1: (3:7) egyenl}otlenseget. Reprezentalja az M matrix L1  L2-t es tegyuk fel, hogy az els}o n1 oszlop felel meg L1 1 alaphalmazanak, mg a masodik n2 oszlop L2 2 alaphalmazanak. Azt szeretnenk bizonytani, hogy M-nek legalabb s(L1 )+s(L1 );1 sora van. Jelolje az els}o n1 oszlop altal meghatarozott reszmatrixot M1, mg a maradekot M2 . 3.3 Lemma LM2 = L2: Bizonytas: Tegyuk fel, hogy A  2 a 2 2 es a 2 L2 (A). Ekkor a 2 (L1  L2 )(A). Ha M ket sora megegyezik A-ban, akkor M denicioja miatt a-ban is, es ez igaz marad akkor is, ha csak az M2 reszmatrixot tekintjuk. Azaz bebizonytottuk, hogy a 2 LM2 (A). Fordtva, most tegyuk fel, hogy A  2 a 2 2 es a 62 L2(A). Mivel gy a 62 (L1 L2)(A), ezert M-nek van ket olyan sora, hogy ezek megegyeznek A-ban, de kulonboznek a-ban. Ezeknek a soroknak M2 -be es}o resze mutatja, hogy a 62

LM2 (A). Analog modon LM1 = L1: Azonban M1 -re egy valamivel er}osebb alltasra van szukseg: 12 3.4 Lemma Tegyuk fel, hogy az N matrix sorai k osztalyba sorolhatok ugy, hogy ha a 62 LN (A), akkor letezik egy osztalyban ket olyan sor, melyek megegyeznek A-ban, de kulonboznek a-ban. Ekkor (N sorainak szama) s(LN ) + k ; 1: (3:8) Bizonytas: k-ra vonatkozo indukcioval bizonytunk. k = 1-re (38) s(LN ) denicioja miatt igaz. Tegyuk fel, hogy N mar particionalva van k 2, a lemma felteteleit teljest}o osztalyra, es hogy az alltas igaz kisebb ertekekre. LN csak attol fugg, hogy N mely elemei egyenl}ok, illetve melyek nem. Ezert feltehet}o, hogy a matrix csak pozitv egesz ertekeket tartalmaz. Toroljuk N azon oszlopait, melyekben csak egyfajta ertek all, es jeloljuk az uj matrixot N1 -nel. N sorainak particioja N1 -nek is egy jo" particiojat adja Masfel}ol nyilvan s(LN1 ) = s(LN ): (3:9) Tovabba LN1 ( ) = .

Legyenek p1 p2  : : :  pk N1 minden elemenel nagyobb prmszamok. Szorozzuk be az i-edik sorosztaly minden elemet pi -vel (1 i k). Jelolje az uj matrixot N2 Konnyen lathato, hogy LN2 = LN1  (3:10) mivel LN1 ( ) = es kulonboz}o sorosztalyokban N2 nem tartalmaz egyforma elemeket. Legyen  = (1  : : :  u) illetve = ( 1  : : :  u ) az N2 els}o illetve masodik osztalyanak egy-egy sora. Most toroljuk a  sort es csereljunk ki minden i-t i -re az i-edik oszlopban (minden 1 i u -ra). Jelolje az uj matrixot N3 Ennek eggyel kevesebb sora van, mint N2-nek. Most bizonytsuk be, hogy LN3 = LN2 : (3:11) Tegyuk fel el}oszor, hogy a 2 LN2 (A) es valasszuk ki N3 ket sorat, 3 -t es 3-t, melyek megegyeznek A-ban. A megfelel}o sorokat N2-ben jelolje 2 illetve 2 Ha N2- ben 2 es 2 azonos osztalyban van, de nem az els}oben, akkor 2 = 3  2 = 3. Ezert 2 es 2 megegyeznek A-ban es gy a 2 LN2 (A) miatt a-ban is. Ugyanez all es 3-ra, tehat a 2 LN3 (A).

Ha 2 es 2 egyarant az els}o osztalyban van, akkor 3 -ra  ulonbozik 2-t}ol, hogy i helyett i all mindenutt. Ugyanez igaz 3 csak annyiban k -re  e s -ra. K o vetkez eskepp 2 es 2 megegyezik A-ban, es gy a-ban is. Kapjuk 2 3 tehat, hogy 3 es 3 is megegyezik a-ban es gy a 2 LN3 (A). Az utolso esetben 2 13 es 2 kulonboz}o osztalyban vannak. Mivel a felteves szerint 3 es 3 megegyezik A-ban, ezert vagy A = , vagy 2 es 2 az els}o es a masodik sorosztalybol valo. LN2 ( ) = miatt az els}o esetet kizarhatjuk. Tehat 2 6=  az els}o osztalyban van, mg 2 a masodikban. Nyilvan 2 = 3 Mivel 3 es 3 megegyezik A-ban, ezert mindkett}oben az i-edik helyen i 2 A-ra i-nek kell allnia. Ekkor 2 = 3 es megegyeznek A-ban, kovetkezeskepp a-ban is. Jelolje a kozos erteket itt a Ha all i 2 A-ra, akkor 2 ott i-t tartalmaz. Tehat 2 es 3 -ban az i-edik helyen i   megegyezik A-ban es gy a-ban is. A kozos ertekuk itt a Ebb}ol azt kapjuk erteke

ebben az oszlopban. Ezert 3 es 3 megegyezik a-ban, es gy 3 -nak is a az  a 2 LN3 (A). Tegyuk most fel, hogy a 62 LN2 (A). Ekkor van N2-nek ket sora, hogy ezek megegyeznek A-ban, de kulonboznek a-ban Ha A 6= , akkor ez a ket sor ugyanabban az osztalyban van, kovetkezeskepp a megfelel}o sorok N3-ban szinten megegyeznek Aban es kulonboznek a-ban ( -nak felel meg). Tehat ebben az esetben a 62 LN3 (A) A =  a 2 LN3 ( ) azt jelen tene, hogy van egy olyan oszlop, amiben ugyanazok az ertekek szerepelnek. Ez k 3-ra lehetetlen k = 2-re ez csak ugy lehetseges, ha N2 csak a-t es a-t tartalmaz az a-nak megfelel}o oszlopban. Azonban ebben az esetben nem tudnank talalni ket sort ugyanabban az osztalyban, melyek teljestik a lemma feltetelet a 62 LN2 ( )-ra. Ez az ellentmondas mutatja, hogy a 62 LN3 (A), es gy (3.11) -t bebizonytottuk S}ot N3-ra teljesul a lemma feltetele (legalabb) k ; 1 osztallyal. Igy az indukcios felteves alapjan: (N3 sorainak

szama) s(LN3 ) + k ; 2: Ebb}ol es (3.9)-(311)-b}ol kapjuk: (N sorainak szama) s(LN ) + k ; 1 amivel a lemmat bebizonytottuk. Terjunk most vissza a tetel bizonytasahoz, pontosabban (3.7)-hez Particionaljuk M1 sorait aszerint, hogy a folytatasuk M2 -ben megegyezik-e Celunk a 34 Lemmat alkalmazni M1 -re. A 33 Lemma alapjan LM1 = L1 Tegyuk fel, hogy valamely A  1-re es a 2 1-re a 62 LM1 (A) = L1 (A). Ekkor a 62 L1 (A)  2 = (L1  L2 )(A  2) teljesul es ezert M-nek van olyan ket sora, melyek megegyeznek A  2-n, de kulonboznek a-ban. Masszoval van M1-nek ket sora, melyek megegyeznek A-ban, kulonboznek a-ban, es ugyanabban a particioosztalyban vannak Alkalmazzuk a 3.3 Lemmat M1-re: (M1 sorainak szama) s(L1 ) + (M2 kulonboz}o sorainak szama) ; 1: 14 (3:12) Ismet felhasznalva a 3.3 Lemmat kapjuk (M2 kulonboz}o sorainak szama) s(L2 ): (3.12)-b}ol es (313)-bol: (3:13) (M sorainak szama) s(L1 ) + s(L2 ) ; 1 ami bizonytja

(3.7)-t es gy a tetelt is Analog modon denialhatjuk Sperner-rendszerek direkt szorzatat. 3.5 Denicio Legyen  = 1  2 az  alaphalmaz egy particioja, es legyenek K1 es K2 Sperner-rendszerek 1-n illetve 2 -n. Ekkor a direkt szorzat de nicioja K1  K2 = fA  Bj A 2 K1  B 2 K2g Az el}oz}o tetel bizonytasaban szerepl}o konstrukcio mutatja, hogy s(K1 K2) s(K1 ) + s(K2 ) ; 1: Bar szamos esetben fennall az egyenl}oseg, a 3.2 Tetel alltasa nem igaz kulcsrendszerekre. 3.6 Pelda 7] Legyen 1 = f1 2 3 4 5g 2 = f6 7 8 9 10g K1 = ff1 2g, f3 4g, f1 5g, f2 5g, f3 5g, f4 5gg K2 = ff6 7g f8 9g f6 10g f7 10g f8 10g f9 10gg: Konnyen lathato, hogy K1;1 = ff5g f1 3g f1 4g f2 3g f2 4gg: A 2.14 Lemma szerint s(K1 ) 4 Tegyuk fel, hogy s(K1 ) = 4 es ezt az M matrix realizalja. Ekkor a 215 Lemmaban szerepl}o G(M) grafnak 4 csucsa van es 5 ele K;1 elemeivel cimkezve. Nehany eset megkulonboztetesevel lathato, hogy a

215 Lemma miatt a hatodik el cimkeje f1 2g f1 2 5g f3 4g vagy f3 4 5g lehet. Ezek azonban mind kulcsok, ami ellentmondas. Tehat s(K1 ) = s(K2 ) 5 Masfel}ol a kovetkez}o matrix mutatja, hogy s(K1  K2) 8: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 0 0 1 2 0 1 0 1 1 0 0 0 0 0 1 0 0 1 2 1 1 1 1 0 (nem trivialis, (K1  K2 );1 bonyolult strukturaja miatt). 15 4. s(Lnk) nagysagrendje Ebben a fejezetben rogztett k mellett n ! 1-re vizsgaljuk s(Lnk ) es s(Lnn;k ) erteket. 4.1 Tetel 7] p ; 1 (k;1)=2 (k;1)=2 2 k;1 n < s(Lnk ) < 23k=2n(k;1)=2 (2 k < n): (4:1) Bizonytas: (4.1) els}o egyenl}otlensege a 214 Lemma egyszer}u kovetkezmenye Most mutatunk egy konstrukciot, mely bizonytja a masodik egyenl} otlenseget. Legyen p egy prmszam. Megmutatjuk, hogy letezik egy 2bppc szamossagu D halmaz, hogy minden i egesz szamhoz leteznek d1 d2 2 D, hogy i  d1 ; d2 (mod p):

Egy ilyen D halmaz denicioja peldaul: (4:2) D = f0 1 2 : : :  a ; 1 2a 3a : : :  (a ; 1)ag p ahol a = d pe. Tegyuk fel, hogy valamely i-re 0 i < p es i = al + r (0 r < a) Ha 1 l a ; 2 es 0 < r < a, akkor d1 = (l + 1)a es d2 = a ; r teljesti (4.2)-t Ha i = al (2 l a ; 1), akkor d1 = al es d2 = 0 megfelel}o. a = 3a ; 2a, mg a tobbi kifejezhet}o 0 es az 1 2 : : :  a ; 1 szamok kulonbsegekent (p = 2-re vagy p = 3-ra D = f0 1g jo). Ekkor D szamossaga: jDj = 2a ; 2 = 2(dppe ; 1) = 2bppc: Most denialjuk polinomok egy 2k bppck;1 szamossagu P halmazat: P = fck;1xk;1 + ck;2xk;2 + : : : + c1x + c0j c0 c1 : : :  ck;1 2 D ck;1 = 0 vagy 1g: Legyen M egy jPj  p-es matrix. A sorok feleljenek meg P tagjainak A z(x) 2 P -nek megfelel}o sor j: eleme legyen z(j ) (mod p) (0 j p ; 1 16 0 z(j ) p ; 1). Belatjuk, hogy M reprezentalja Lpk -t A 213 Lemma alapjan elegend}o belatni, hogy M; reprezent alja Kkp-t. Eleg azonban csak a 216

Lemma  ; felteteleit ellen}orizni K = k  K;1 = k;1 -re (ahol jj = p). Tegyuk fel, hogy a z1(x)-nek es z2(x)-nek megfelel}o sorok k helyen megegyeznek: z1 (ti )  z2(ti ) (mod p) (0 t1 < t2 < : : : < tk < p): A z1(x) ; z2(x) legfeljebb (k ; 1)-edfoku polinomnak k kulonboz}o gyoke van. Ez az ellentmondas mutatja, hogy z1 es z2 ugyanaz, es a ket" sor valojaban egy. Valasszuk most a 0 t1 < t2 < : : : < tk;1 < p egesz szamokat tetsz}olegesen. Talalnunk kell ket sort, melyek megegyeznek a t1-edik, t2-edik,: : :,tk;1 -edik helyen. Tekintsuk a w(x) = (x ; t1)(x ; t2) : : : (x ; tk;1 ) = xk;1 + ak;2 xk;2 + : : : + a1 x + a0 polinomot. ai -hez (0 i k ; 1) talalhato D-nek ket ci es c0i eleme, hogy ai  ci ; c0i (mod p). Ekkor w(x) = z(x) ; z0 (x), ahol z(x) = xk;1 + ck;2xk;2 + : : : + c1x + c0 es z0 (x) = c0k;2xk;2 + : : : + c01x + c00: z(x) es z0 (x) nyilvan ket kulonboz}o eleme P -nek. Masfel}ol valoban z(ti )  z0 (ti ) (mod

p). A 216 Lemma mindket feltetelet ellen}oriztuk,gy M tenyleg reprezentalja Lpk -t. Tehat: s(Lpk ) 2k p(k;1)=2: Tetsz}oleges n-re valasszunk egy p prmet, melyre n p 2n. Ilyen PL CSEBISEV tetele (peld aul 13]-ban) szerint letezik. Most kesztsunk egy matrixot, p mely reprezentalja Lk -t, es hagyjuk el p ; n oszlopat. Ez a matrix reprezentalja Lnk-t, ezert s(Lnk ) 2k p(k;1)=2 2k (2n)(k;1)=2 23k=2n(k;1)=2 tehat a tetelt bebizonytottuk. Azt mondjuk, hogy egy n oszlopbol allo M matrix egy tokeletes k-hibajavto adatbazis, ha tetsz}oleges k oszlopat torolve a megmaradt matrix barmely ket sora 17 kulonbozik, de barmelyik k + 1 sorat torolve lesz ket sor, melyek megegyeznek. Egy n attributumu tokeletes k-hibajavto adatbazis lehetseges sorai szamanak meghatarozasa nyilvan ekvivalens s(Lnn;k ) meghatarozasaval. A kovetkez}o tetel els}o egyenl}otlensege megjavtja erre az esetre a 214 Lemmat 4.2 Tetel 14] n > n0

(k) k 1-re 1 (2k+1)=3 (k+1)! n < s(Lnn;k ) < k1! nk : (4:3) Bizonytas: A masodik egyenl}otlenseget egy egyszer}u konstrukcio mutatja. Legyenek  k-elem}u reszhalmazai E1  E2 : : :  E(nk). Az i-edik sor j -edik helyen alljon 0 ha j 62 Ei, ha pedig j 2 Ei , akkor i. Az gy kapott matrix k 1-re reprezentalja Lnn;k -t. A masik irany bizonytasahoz tegyuk fel, hogy M reprezentalja Lnn;k -t. Felhasznaljuk KO} VA RI-SO S-TURA N egy extremalis grafelmeleti eredmenyet 4.3 Lemma 18] Tegyuk fel, hogy a G (V E ) graf nem tartalmazza reszgrafkent a K(2 p) teljes paros grafot. Ekkor r jE j < p ;2 1 jV j3=2 + jV2 j : (4:4) Szuksegunk van meg nehany jelolesre. Jelolje V az adatbazis sorainak a halmazat Legyenek   2 V ,ekkor D(  ) = fij (i) 6=  (i)g Jelolje H (  ) = jD(  )j az  es  sorok Hamming-tavolsagat. Denialjuk az M-hez tartozo G minimalis tavolsaggrafot a V csucshalmazon ugy, -t es  -t pontosan

akkor kossuk ossze ellel, ha H (  ) = k + 1. (  ) 2 G szne legyen D (ahol D   jDj = k + 1), ha D = D(  ). Jelolje szokasos modon deg()  fokat, ;() pedig  szomszedainak halmaz ; n  at. Minden k + 1 elem}u D  -hoz valasszuk ki G egy D szn}u elet. Ez az k+1 par alkotja a G0 redukalt minimalis tavolsaggrafot. Ebben deg0-lal illetve ;0-lal jeloljuk egy pont fokat illetve szomszedai halmazat. 4.4 Lemma (i) amennyiben (  ) 62 G , akkor j;() ;( )j < 32k+2, (ii) n > n0 (k) eseten tetsz}oleges   2 V -re j;0() ;0 ( )j < n3k . Bizonytas: Legyen C = fx 2 j (x) 6=  (x)g, ekkor jC j = H (  ). Feltehet}o, hogy jC j 2k +2, ugyanis kulonben a lemma trivialisan igaz, mert ekkor nem letezik  2 V , hogy f  g 2 G  f  g 2 G . Vegyuk eszre, hogy minden x 2 C -re  (x) kulonbozik (x)-t}ol vagy  (x)-t}ol, ezert 18 C  D(  )  D(  ): (4:5) Tovabba D(  )nC = D(  )nC . Szuksegunk van egy

alltasra, mely szerint  -t (majdnem) meghatarozza D(  ) es D(  ) C -beli nyoma. 4.5 A lltas Tegyuk fel, hogy   0 2 ;() ;( )  6=  0, valamint azt, hogy D(  ) C = D(  0 ) C es D(  ) C = D(  0 ) C . Ekkor jC j = k + 1 es (D(  )nC ) = (D(  0 )nC ) = : Bizonytas: (4.5) szerint D(  0 )  D(  )  D(  0 )  es  0 megegyezik C n(D(  ) D(  ))-n, ezert (4:6) H (  0 ) jD(  ) D(  ) C j + jD(  )nC j + jD(  0 )nC j: Mivel jD(  0 )nC j = jD(  )nC j, azert (4.6) jobb oldala egyenl}o 2(k + 1) ; jC j-kel. Ha jC j > k + 1, akkor ez a H (  0 ) < k + 1 ellentmondashoz vezet Igy jC j = k + 1, es (4.6)-ban egyenl}oseg all fenn Ezert a D(  )nC es D(  0 )nC halmazok diszjunktak. Most terjunk vissza 4.4 Lemma bizonytasahoz Az (i) esetben a 45 A lltas szerint j;() ;( )j legfeljebb annyi, mint azon A B  C = D(  ) halmazparok szama, melyekre jAj = jBj A B = es jAj jC j; k ; 1.

(Itt A = D(  )nD(  ) es B = D(  )nD(  ).) Ezert X jC j2i jCj 2k+2 j;() ;( )j <3 3 : 2 i i ijC j;k;1 (ii) bizonytasahoz most mar feltehet}o, hogy jC j = k +1. Valasszunk A B  C halmazokat, melyekre jAj = jBj = i A B = , es tekintsuk az osszes  2 ;0() ;0( )-t, hogy A = D(  )nD(  ) es B = D(  )nD(  ). Ekkor G0 denicioja miatt tetsz}oleges  2 ;0 ()-ra jD(  )nC j = i > 0. Igy a 45 A lltas szerint az ilyen  -k szama legfeljebb (n ; jC j)=i. Ezert X jC j2i n ; k ; 1 X k + 12i 1 k: j;0() ;0 ( )j < n < n 3 i i i i i1 2i i1 2i A 4.2 tetel bizonytasahoz tekintsuk a G0 M-hez tartozo redukalt minimalis tavolsaggrafot. A 44 Lemma szerint G0 nem tartalmazza reszgrafkent a K(2 n3k ) teljes paros grafot. Ekkor a 43 Lemma szerint r k  n  n3 jV j3=2 + jV j  = jG 0j k+1 2 2 amib}ol a tetel kovetkezik. 19 5. s(Lnk) meghatarozasa k nehany ertekere Ebben a fejezetben s(Lnk ) nehany

konkret erteket hatarozzuk meg. 5.1 Tetel 10],7] p s(Ln1 ) = 2 s(Ln2 ) = d(1 + 1 + 8n)=2e s(Lnn;1 ) = n s(Lnn ) = n + 1: Bizonytas: Az els}o harom esetben a tetel azt alltja, hogy a 2.14 Lemmabol szarmazo becsles (termeszetesen ha nem egesz, akkor a fels}o egeszresze) eles. Tehat eleg 3 konstrukciot mutatni. Hogy ezek tenyleg jok, a 216 Lemma alapjan konnyen ellen}orizhet}o. k = 1 eseten: 0 0 ::: 0 1 1 ::: 1 k = 2 eseten: (minden oszlopban pontosan 2 darab nulla all ugy, hogy kulonboz}o oszlopokhoz tartozo nullak kulonboz}o sorparokhoz tartoznak) 0 0 0 ::: 0 1 1 ::: 1 0 2 2 ::: 2 0 0 ::: 2 3 0 3 ::: 3 0 3 ::: 3 4 4 0 ::: 4 4 0 ::: 4 . . . . . . . . . . . . s; 1 s ;1 s ;1 ::: s ;1 s; 1 s ;1 ::: s ; 1 s s s ::: 0 s s ::: s k = n ; 1 eseten: 1 0 . . 0 ::: ::: . ::: 0 1 . . 0 20 0 0 . . 1 A k = n esetben a 2.15 Lemma van segtsegunkre Tegyuk fel, hogy egy M matrix reprezentalja Knn = fg-t. Ekkor  barmely (n ;

1)-elem}u A reszhalmazahoz letezik egy el G(M)-ben, melynek cimkeje A. Ezen elekb}ol alkotott reszgraf a lemma szerint kormentes. Igy G(M)-nek legalabb n + 1 csucsa van, tehat s(Lnn ) n + 1 Az egyenl}oseget a kovetkez}o pelda mutatja: 0 0 ::: 0 1 0 ::: 0 0 1 ::: 0 . . . . . 0 0 ::: 1 Ezzel a tetel bizonytasat befejeztuk. Meg ket k ertekre ismertek tetelek. Ezeket bizonytas nelkul megemltjuk s(Lnn;2 )-re ad jobb becslest a 4.2 Tetel els}o egyenl}otlensegenel a kovetkez}o tetel, mely egyben megmondja a pontos nagysagrendet is. 5.2 Tetel 14] n < s(Lnn;2 ) < 21 n2: 1 2 12 (5:1) A 2.14 Lemmabol eppen s(Ln3 ) n adodik, egyenl}oseg akkor all, ha tudunk konstrualni egy n  n-es M matrixot, melyre: 1) barmely kulonboz}o a b c 2 -hoz letezik ket sor, melyek megegyeznek a-ban es b-ben, de kulonboznek c-ben, 2) barmely kulonboz}o a b c 2 -hoz nem letezik ket sor, melyek mindharomban megegyeznek. Tekintsuk a

dualis problemat. Egy oszlop termeszetes modon meghatarozza a sorok V halmazanak egy particiojat az elemek egyenl}osege alapjan. Azt mondjuk, hogy egy particio lefedi az (  ) part (  2 V  6=  ) akkor es csak akkor, ha  es  a particionak ugyanabban az osztalyaban van. Ekkor a fenti ket feltetel a kovetkez}okeppen fogalmazhato: Talaljunk n particiojat V -nek (jV j = n), melyekre: 1') barmely ket particiohoz letezik egy (  ) par, melyet mindkett}o lefed, 2') semelyik (  ) part nem fedi le harom partici ;n o. Azonban a particioparok szama szinten 2 es 2') miatt kulonboz}o particioparok nem fedhetik le ugyanazt a part. Tehat 1') es 2') ekvivalens a kovetkez}okkel: (i) barmely ket particiohoz pontosan egy par letezik, melyet mindkett}o lefed, (ii) barmelyik part pontosan ket particio fedi le. 21 5.3 Denicio 15] Az (i)-t es (ii)-t teljest}o particiok egy osztalyat ortogonalis

dupla fedesnek nevezzuk. A mi szempontunkbol a kovetkez}o eredmeny a leglenyegesebb. 5.4 Tetel 2] 16] n 7 n 6= 8-ra letezik az n-elem}u halmaznak n particioval torten}o ortogonalis dupla fedese. Az ortogonalis dupla fedesek elmelete szerteagazo, altalaban design-tpusu problemakra vezet. Rovid osszefoglalok talalhatok peldaul 17]-ben es 11]-ben a legujabb eredmenyekr}ol, ugyanitt tovabbi hivatkozasok is talalhatok. 22 6. Egy kulcsrendszer reprezentacioja Ebben a fejezetben egy, az eddigiekt}ol elter}o Kn kulcsrendszer minimalis reprezentacioja kerul targyalasra. El}oszor egy, a bizonytas lenyeget ado kombinatorikai segedteq telt (6.5 Tetel) bizonytok Majd ez alapjan a 66 Tetelben belatom, hogy s(Kn ) jKn;1j es jKn;1j kozul (2.17 Lemma) az utobbihoz van kozelebb Vegul a 6.7 tetelben jKn;1j nagysagrendjenek meghatarozasa teszi teljesse a bizonytast 6.1 Denicio Egy F fat nevezzunk iranytott

fanak, ha fa, es ha van az eleknek egy olyan iranytasa, hogy pontosan egy csucsbol (gyoker) erhet}o el a tobbi az iranytas szerint. Jeloljuk egy v csucs kimen}o szomszedai halmazat N (v)-vel, mg (a gyoker kivetelevel) az egyertelm}uen letez}o bemen}o szomszedot n(v)-vel. A fa levelei halmazat jelolje l(F ). 6.2 Denicio Legyen adva egy U (veges) halmaz Egy F = F (U ) fat nevezzunk cimkezett fanak, ha F minden v csucsahoz hozza van rendelve U -nak egy A(v) reszhalmaza. Legyen U egy tetsz}oleges m elem}u halmaz, mondjuk U = f1 2 ::: mg (m 2): Tekintsuk iranytott cimkezett faknak azt az F = F (m) csaladjat, amely csalad F fainak csucsai a kovetkez}okeppen vannak cimkezve. A g gyoker cimkeje A(g) = U Tetsz}oleges gyokert}ol kulonboz}o v csucsra pedig valamely N (v) = N0(v) N1(v) diszjunkt felbontas mellett: A(v)  A(n(v)) (6:1) jA(v)j 2 (6:2) w1 w2 2 Ni (v) ) A(w1 ) A(w2) = (i = 0 1) (6:3) w1 2 Ni(v) w2 2 N1;i

(v) )jA(w1) A(w2 )j 1 (i = 0 1): (6:4) Jelolje T (m) = max(m) jl(F )j. T (m) becslese el}ott szuksegunk van ket egyszer}u F 2F technikai lemmara. 6.3 Lemma T (m1 ) + T (m2 ) + : : : + T (mk ) T (m1 + m2 + : : : mk ): 23 (6:5) Bizonytas: Eleg belatni, hogy T (m1) + T (m2 ) T (m1 + m2). Ha adott ket iranytott cimkezett fa az U1 illetve U2 m1 illetve m2 elem}u diszjunkt halmazokkal cimkezve a gyokeruknel, melyek rendelkeznek a (6.1)-(64) tulajdonsagokkal, akkor az a fa, amelyiknek a gyokerenek a cimkeje U1  U2 es a gyoker ossze van kotve a ket kisebb fa gyokerevel szinten rendelkezik a (6.1)-(64) tulajdonsagokkal A kovetkez}o lemmaban a 6.5 Tetelben hasznalt fuggvenyek nehany tulajdonsagat emltem meg Most, es a fejezet tovabbi reszeben is az e alapu logaritmust log jeloli. 6.4 Lemma Rogztett 0 < " < 1-re x > 1 eseten: f (x) = elog1; x szigoruan monoton nov}o g(x) = x"+log; x szigoruan monoton

nov}o h(x) = x1+"+log; x szigoruan monoton nov}o h(x1 )+h(x2 ) + : : : + h(xk ) h(x1 + x2 + : : : xk ): (6:6) (6:7) (6:8) (6:9) Bizonytas: f 0 (x) = x 1log; x elog1; x > 0 bizonytja (6.6)-t g(x) illetve h(x) ket szigoruan monoton fuggveny szorzata. (67) alapjan ; ; ; (x1 +x2) "+log x1 + x1+"+log x2 x (x + x )"+log h(x1 ) + h(x2 ) = x1+ 1 1 2 1 2 ;  + x2 (x1 + x2 )"+log (x1+x2) = h(x1 + x2 ) + ami bizonytja (6.9)-t Tehat belattuk a lemma osszes alltasat 6.5 Tetel Minden ("0 )" > 0-hoz letezik csak "-tol fugg}o , hogy minden m 2 egeszre T (m) m1+"+log; m : (6:10) Bizonytas: Legyen " rogztett. m-re vonatkozo indukcioval bizonytunk Mivel a jobb oldalon ;m m kitev}oje x m-re ! 0 eseten (2 + ")-hoz tart es nyilvan T (m) ert ha M csak " -tol fugg}o (eleg nagy) konstans (amit kes}obb 2 , ez valasztunk meg), akkor feltehet}o hogy m M eseten igaz az alltas.

Tegyuk most fel, hogy minden m(> M )-nel kisebbre igaz az alltas. Tekintsuk azt az F fat, amelyre jl(F )j maximalis. Legyen N (g) = fv1 v2  : : :  vs  vs+1 : : :  vt g valamint N1(g) = fv1 v2  : : :  vsg es N2 (g) = fvs+1 vs+2 : : :  vtg az F deniciojaban szerepl}o felbontas. Jelolje mi = jA(vi )j valamint Fi a vi -b}ol mint gyokerb}ol 24 indulo reszfat 1 i t-re. Ez csak ugy lehetseges, ha T (mi) = jl(F )j minden 1 i t -re. Tehat azt eleg belatni, hogy t X i=1 T (mi ) m1+"+log; m : ; (6:11) " 1 ; 1c es 2 < c" valamint Legyen c = c(") olyan nagy, hogy (1 ; 61 1=" ) " 2 M = M (") olyan nagy, hogy M > 4c 2max T (h) Most 4 reszre bontjuk az hc2 1 i t indexhalmazt: P = fij mi c2g Q = fij c2 < mi mc g R = fij mc < mi m(1 ; 1c )1="g S = fij m(1 ; 1c )1=" < mig: Vegyuk eszre, hogy c valasztasa miatt  ; S  fij m;mmi " < 16 g: (6:12) 1. Eset: S 6= Legyen j 2 S

F deniciojanak szimmetriaja miatt feltehet}o, hogy 1 j s. Ekkor t X i=1 T (mi ) = T (mj ) + t X i=1 i6=j T (mi ) T (mj ) + T (m ; mj ) + T (2m ; 2mj ) (6:13) felhasznalva (6.5)-t, valamint hogy (63) miatt Pt Ps m i=1 i6=j i m ; mj es hogy (6.2)-(64) miatt mi m ; mj + (t ; s) 2(m ; mj ). Az indukcios feltevest, valamint i=s+1 (6.7)-t felhasznalva: T (mj ) m1+"+log; m ; (m ; mj )m"+log; m  ; T (m ; mj ) (m ; mj )1+"+log (m;mj ) ; T (2m ; 2mj ) (2m ; 2mj )1+"+log (2m;2mj ): 25 (6:14) (6:15) (6:16) Vegyuk eszre, hogy ; (2m ; 2mj )1+"+log (2m;2mj ) ; 21+"+log; (m;mj )  (m ; mj )1+"+log (m;mj ) ; 5  (m ; mj )1+"+log (m;mj ) (6:17) felhasznalva, hogy mj m;3 eseten 2 kitev}ojeben a harmadik tag 1-gyel becsulhet}o felulr}ol. Az mj = m ; 1 vagy mj = m ; 2 esetek kulon ellen}orizhet}ok (peldaul ekkor Pt T (m ) T (m ; 1) + 3, ami eleg nagy m eseten az indukciot felhasznalva kisebb i i=1 mint a tetel

jobboldalan lev}o fuggveny). A fentiek alapjan ; ; (m ; mj )1+"+log (m;mj ) + (2m ; 2mj )1+"+log (2m;2mj ) ; 6  (m ; mj )1+"+log (m;mj ) =  1; ;  ; 1; = (m ; mj )m"+log m 6  m;mmj "elog (m;mj );log m : (6:18) Most (6.12)-(618)-t osszevetve es felhasznalva (66)-t kapjuk a (611) egyenl}otlenseget 2. Eset: S = R = Ekkor az 1-t}ol t-ig men}o osszegzes P  Q -n megy Az indukcios felteves szerint t X X 1+"+log; mi T (mi ) mi = i=1 i2P Q X ;mi " "+log; m log1; mi ;log1; m = mi m m e : i2P Q (6:19) ;  Q denicioja es a c-re tett masodik felteves miatt minden 1 i t-re mmi " (6.6) felhasznalasaval: X i2P Q ;  mi mmi "m"+log; m elog1; mi ;log1; m Pt Ps Pt 1 X m m"+log; m: 2 i2P Q i 1 2 . (6:20) A nyilvanvalo mi = mi + mi m + m = 2m egyenl}otlensegb}ol (ali=1 i=1 i=s+1 kalmaztuk (6.3)-t) (619) es (620) felhasznalasaval adodik a (611) egyenl}otlenseg 26 Pt P P P

3. Eset: S =  R 6= Ekkor T (mi) = T (mi ) + T (mi) + T (mi ) i=1 i2P i2Q i2R Tovabba az indukcios felteves szerint: X X 1+"+log; mi T (mi ) mi = i2R i2R X 1; 1; ;  ;  = 12 mi m"+log m 2  mmi "elog mi ;log m : i2R (6:21) Felhasznalva (6.6)-t es R deniciojat: 1 X m m"+log; m 2  ;mi "elog1; mi ;log1; m m 2 i2R i 1 X 2m ;1 ; 1 m"+log; m = c 2 i2R i X;  "+log; m 1 X mi "+log; m 1 m i mi + mi ; c m =2 ;2 : c m i2R i2R R denicioja miatt es mivel R 6= 1 X mi m"+log; m 2 i2R c M valasztasa miatt 2c2 X i2P (6:22) 1 m1+"+log; m : 2c2 (6:23) T (mi ) < m  M " m1+"+log; m : (6:24) A Q-ra torten}o osszegzest hasonloan becsulhetjuk, mint a 2. esetben: X i2Q T (mi ) X ;mi " "+log; m log1; mi ;log1; m mi m m e i2Q 1 X m m"+log; m: i 2 i2Q 27 (6:25) Azonban vegyuk eszre, hogy X i2Q mi + X; i2R  mi + (mi ; mci ) 2m: (6:26) Ugyanis egy

tetsz}oleges i 2 R-hez (feltehet}o, hogy 1 i s) tartozo A(vi ) halmazba (6.3) miatt csak az s + 1 j t-hez tartozo A(vj ) diszjunkt halmazok metszhetnek bele Mivel minden j 2 Q  R-re mj > c2, ezert legfeljebb m c2 darab A(vj ) jm2 Q  R metszhet bele A(vi )-be, mivel azonban R valasztasa miatt jA(vi )j > c ezert (6.4) miatt A(vi ) elemeinek legfeljebb c-edresze lehet valamelyik A(vj ) j 2 Q  R eleme, masszoval legalabb mi ; mci elem nem lehet s + 1 j t j 2 Q  R-hez tartozo A(vj )-vel lefedve. Ezert t X i=s+1 i2QR mi + t ; X i=s+1 i2R  mi ; mci m es s X i=1 i2QR mi m: Igy ebben az esetben is (6.21)-(626) alapjan fennall a (611) egyenl}otlenseg Ezzel tehat a tetel bizonytasat befejeztuk. 6.6 Tetel Legyen Kn = ff1 2g f2 3g : : :  fn ; 2 n ; 1g fn ;1;1" ng fn 1gg Ekkor minden ("0 )" > 0 letezik n0, hogy n > n0 eseten jKn;1 j s(Kn ) ; 1 jKn j + 1. Bizonytas: Legyen " tetsz}oleges (eleg kis) pozitv

szam. A masodik egyenl}otlenseg a 217 Lemma miatt igaz Hatarozzuk meg most Kn;1-t. Azt alltom, hogy Kn;1 = ffa1 : : :  ak gj a1 < ::: < ak  2 ai+1 ; ai 3 es n ; 3 ak ; a1 n ; 2g: (6:27) Valoban, ezek nyilvan antikulcsok, hiszen nem tartalmazzak Kn egyetlen elemet sem, maximalis antikulcsok, hiszen egy ilyennel b}ovebb mar tartalmazna szomszedos elemet. Mas nem tartozik hozzajuk, hiszen aminek van ket (ciklikusan) szomszedos eleme az kulcs, ami pedig legalabb harmat kihagy, az nem lehet maximalis, hiszen valamelyik kozeps}ot hozzaveve meg mindig antikulcsot kapunk. A 2.16 Lemma szerint egy M matrix reprezentalja Kn -et pontosan akkor, ha minden A 2 Kn;1 -hez letezik ket sor, hogy A-ban azonos elemek allnak, es ha K 2 Kn es ket sor megegyezik K -ban, akkor mindenutt. Az utobbi viszont minimalis sorszamu reprezentacio eseten nem lehetseges, hiszen a ket egyforma sor kozul az egyik elhagyasaval egy kevesebb sorral rendelkez}o

matrixot kapunk, ami 28 szinten reprezentalja Kn -et. Igy tehat feltehet}o, hogy semelyik K 2 Kn-re nem letezik M-nek ket sora melyek megegyeznek K -ban. Nezzuk meg, hogy milyen s}ur}un" lehetnek a Kn;1 -beli elemekhez tartozo sorparok. Ezek a parok persze kulonboz}o antikulcsra kulonboz}oek, mert ha nem, akkor lenne ket sor, mely ket Kn;1-beli uniojan megegyezne, ami viszont egy kulcs. Legyen M egy olyan matrix ami reprezentalja Kn -et es s(Kn ) sora van. Rogztsuk M egy oszlopat, mondjuk az els}ot. Most feleptunk Fi cimkezett iranytott fakat (annyit, ahanyfele elemb}ol legalabb 2 szerepel az els}o oszlopban). S Legyen U = f1 : : :  s(Kn )g a sorok egy sorszamozasa es U  Ui  jUi j 2, ahol Ui az els}o oszlopban szerepl}o azon i-edik fajta elemhez tartozo sorok sorszamainak halmaza, amely elemb}ol legalabb 2 van. Legyen jUi j = mi Az Fi fa g gyokerenek cimkeje legyen A(g) = Ui . Tegyuk fel, hogy mar denialtuk a fa egy v

csucsat es A(v) cimkejet, es hogy A(v) ugy volt denialva, hogy valamely j -edik oszlopbans bizonyos egyenl}o elemekhez tartozo sorok sorszamainak halmaza. Legyen S A(v)  Ai , ahol Ai a (ciklikusan) (j + 2)-edik oszlopban szerepl}o azon A(v)i=1 beli i-edik fajta elemekhez tartozo sorok sorszamainak halmaza, amib}ol legalabb 2 St van, mg A(v)  Ai , ahol Ai a (ciklikusan) (j + 3)-adik oszlopban szerepl}o i=s+1 azon A(v)-beli i-edik fajta elemekhez tartozo sorok sorszamainak halmaza, amib}ol legalabb 2 van. Legyen N (v) = fv1 : : :  vt g es A(vi ) = Ai (1 i t) Vegyuk eszre meg azt, hogy jAk Al j 1 (1 k s 1 l t), ugyanis ha legalabb ketelem}u lenne a metszet, akkor lenne ket sor mely a fj +2 j +3g kulcs oszlopaiban megegyezne, ami viszont a fentiek szerint nem lehet. Igy tehat azt is latjuk, hogy az Fi fak rendelkeznek a (6.1)-(64) tulajdonsagokkal A 6.5 Tetelt alkalmazva: jl(Fi )j T (mi) mi1+"+log; mi : Ebb}ol (6.9) alapjan X i ; jl(Fi )j

s(Kn )1+"+log s(Kn): (6:28) (6:29) s(Kn ) ! +1 miatt (ami peldaul a korabbi alltasokat nem hasznalo (6.36) es (632) alltasok, valamint a 2.17 Lemma miatt igaz) s(Kn ) > m0-ra (ami n > n0 eseten igaz): ; s(Kn ) s(Kn )1+"+log 29 s(Kn )1+2": (6:30) Vegyuk eszre, hogy X i jl(Fi )j jfK 2 Kn;1 melyre 1 2 K gj: (6:31) Ugyanis az Fi fak denicioja miatt a jobboldalon szerepl}o halmaz egy tetsz}oleges elemehez (azaz egy 1-et tartalmazo antikulcshoz) tartozo azon sorok (legalabb 2) halmaza, melyek megegyeznek ebben az antikulcsban reszhalmaza valamely A(v)S S nek (v 2 l(Fi )), masreszt egy l(Fi )-beli elemhez nem tartozhat ket fK 2 Kn;1 melyre 1 2 K g-beli elem, ugyanis akkor lenne ket sor, mely egy Kn;1 -belinel b}ovebb halmazon, azaz egy kulcson megegyezne. Konnyen lathatoan legalabb minden harmadik Kn;1 -beli antikulcs athalad 1-n, es gy: jKn;1 j jfK 2 Kn;1 melyre 1 2 K gj 13 jKn;1 j: (6:32) Mivel s(Kn ) ! +1, ezert

(6.29)-(632) alapjan n > n0 eseten tenyleg jKn;1 j s(Kn )1+3" amib}ol a tetel kovetkezik. 6.7 Tetel Legyen  a 23x3 ; 23x2 + 9x ; 1 = 0 egyenlet egyetlen valos megoldasa, azaz  = 13 ; p32 3 46  rq 3 27 23 +1; rq 3 (6:33) 27 23  ;1 : (6:34) Ekkor log2 s(Kn ) ;!  log 1 ;  + 1 ; 3 log 1 ;  : 2 2 n 2 2 1 ; 3 (6:35) Jegyezzuk meg, hogy   0:1770088227 : : :, es ha  jeloli a fenti hatarerteket, akkor   0:4056852313 : : : 30 Bizonytas: Becsuljuk meg jKn;1j-t: b3 c  n;t  X ; 1 2 jfK 2 Kn melyre 1 2 K gj = t : t=0 n (6:36) t n(2) Ugyanis legyen K1 = f1 a1  : : :  ak g a baloldalon szerepl}o halmaz egy eleme, ekkor K1 -hez egyertelm}uen hozzarendelhet}o az  = f1 : : :  ng alaphalmaz egy f1 : : :  a1 ; 1g fa1 : : :  a2 ; 1g : : :  fak  : : :  ng 2 es 3 nagysagu blokkokra torten}o felbontasa. Fordtva, ha adott egy ilyen egymast kovet}o 2-es, 3-as blokkokra bontas, akkor a blokkok els}o elemei meghataroznak

egy kvant antikulcsot. (636) jobboldalan eppen az ilyen felbontasok szama szerepel (ha t a harmas blokkok szama, akkor n;2 t az osszes blokkok szama). jKn;1j becslesehez tehat eleg (6.36) jobboldalan a legnagyobb tag nagysagrendjet megbecsulni, ugyanis ekkor (632) alapjan ez ad egy also becslest, ennek 3(n+2) -szorosa pedig fels}o becslest. 6 Ehhez rjuk fel az osszeg ket egymast kovet}o tagjanak hanyadosat es nezzuk meg, mikor lesz ez 1. Egyszer}ustesek utan: ( n;2 t ; t + 3)( n;2 t ; t + 2)( n;2 t ; t + 1) = 1: ( n;2 t + 1)t(t ; 1) Ezt rendezve es az x = nt valtozot bevezetve: 12 44 48 23x3 ; (23 + 96n )x2 + (9 + 68n + 112 n2 )x ; (1 + n + n2 + n3 ) = 0: (6:37) Mivel a (6.37) baloldalan allo polinomok fuggvenysorozata minden veges intervallumban egyenletesen tart a (633) baloldalan allo polinomhoz, ezert (637)-nek eleg nagy n eseten, ugy mint (6.33)-nak, egyetlen valos n megoldasa van, es minden " > 0 -hoz letezik

n0 , hogy n > n0 eseten  ; " n  + ". Most a fentiek alapjan t = nn-et helyettestve (6.36)-ba  1; ; ")n ( 1; + ")n n + 2 ( 2 ; 1 2 jK j n ( ; ")n 2 ( + ")n : 31 (6:38) A Stirling-formulat alkalmazva  n p n n! = ne 2n e 12n (0 < n < 1) cn cdn c (c;d)nq 1 1 n 1 c 12n ( c ; d ; c;d ) = e = 2nd(c;d) d; c ; d dn c + (c ; d) log c + o(1) n d log 2 2 c;d d =2 (1 c d > 0): Ezt (6.38)-ba helyettestve 1; 1;3 1; 0 2n( log2 2 + 2 log2 1;3 ; " ) jKn;1 j 1;3 1; 1; 0 2n( log2 2 + 2 log2 1;3 + " )  amib}ol a 6.6 Tetel alapjan a tetel kovetkezik 32 Hivatkozasi jegyzek 1] W.W ARMSTRONG, Dependency structures of database relationship, Information Processing 74 (North Holland, Amsterdam, 1974) 580-583 2] F.E BENETT, LISHENG WU, On minimum matrix representation of closure operations, Discrete Appl. Math 26 (1990) 25-40 3] B. BOLLOBA S, On generalized graphs, Acta Math Hungar 16 (1965)

447-452 4] G. BUROSCH, J DEMETROVICS, GOH KATONA, The poset of closures as a model of changing databases, Order 4 (1987) 127-142. 5] E.F CODD, A relational model of data for large shared data banks, Comm ACM 13 (1970) 377-387. 6] J. DEMETROVICS, On the equivalence of candidate kays with Sperner systems, Acta Cybernet. 4 (1979) 247-252 7] J. DEMETROVICS, ZFU REDI, GOH KATONA, Minimum matrix representation of closure operations, Discrete Appl Math 11 (1985) 115-128 8] J. DEMETROVICS, GY GYEPESI, A note on minimal matrix representation of closure operations, Combinatorica 3 (1983) 177-180. 9] J. DEMETROVICS, G HENCSEY, LO LIBKIN, IB MUCHNIK, On the interaction between closure operations and choice functions with applications to relational databases, Acta Cybernetica 10 (1992) 129-140. 10] J. DEMETROVICS, GOH KATONA, Extremal combinatorial problems in relational database, in Fundamentals of Computation Theory 81, Proc of the 1981 International FCT-Conference, Szeged, Hungary, 1981,

Lecture Notes in Computer Science 117 (Springer, Berlin 1981) 110-119. 11] J. DEMETROVICS, GOH KATONA, ASALI, Design Type Problems Motivated by Database Theory, preprint 12] J. DEMETROVICS, SON HUA NAM, Closures and Sperner families, Bolyai Society Mathematical Studies, 3 Extremal Problems for Finite Sets (Ed P Frankl, Z. Furedi, Gy Katona, D Miklos) (Visegrad, Hungary, 1991) 199-204 33 13] P. ERDO} S, J SURA NYI Valogatott fejezetek a szamelmeletb}ol, Polygon Konyvtar 193-195 14] Z. FU REDI, Perfect error-correcting databases, Discrete Appl Math 28 (1990) 171-176. 15] B. GANTER, H-DOF GRONAU, RC MULLIN, On orthogonal double covers of Kn , Ars Combinatorica 37 (1994) 209-221. 16] H.-DOF GRONAU, RC MULLIN, preprint 17] G.OH KATONA, Combinatorial and algebraic results for database relations, Database Theory - ICDT '92, Berlin, 1992, Lecture Notes in Comput Science, 646 (Ed. J Biskup, R Hull) (Springer Verlag, Berlin, 1992) 1-20 18] T. KO} VA RI, VT SO S, P

TURA N, On a prblem of K Zarankiewicz, Colloq Math. 3 (1959) 50-57 19] D. LUBELL, A short proof of Sperner's lemma, J Combinat Theory 1 (1966) 299. 20] L.D MESHALKIN, A generalization of Sperner's theorem on the number of subsets of a nite set (in Russian), Teor. Veroyatnost i Primenen 8 (1963) 219-220. 21] E. SPERNER, Ein Satz uber Untermengen einer endlichen Menge, Math Z 27 (1928) 544-548. 22] K. YAMAMOTO, Logarithmic order of free distributive lattices, J Math Soc Japan 6 (1954) 347-357. 34