METODE DE AGREGARE IN BAZE DE DATE NOSQL [601393]

METODE DE AGREGARE IN BAZE DE DATE NOSQL 

  UNIVERSITATEA POLITEHNICA BUCUREȘTI FACULTATEA 
DE AUTOMATICĂ Ș​I​ CALCULATOAR​E 
DEPARTAMENTUL CALCULATOARE 

Modele de agregare în baze de date NoSQL 
Oana Maria STAN 1
Cele mai mari companii din lume, Google, Yahoo, Facebook folosesc pe lângă bazele 
de date relationale și baze de date de tip NoSQL (HBase, Riak etc) pentru a stoca un volum 
mare de date (Big Data). Acestă lucrare științifică prezintă o comparație între bazele de date 
relaționale, PostgreSQL și cele NoSQL, CouchDB, din punct de vedere al metodele de 
agregare. 

Cuvinte cheie​: PostgreSQL, CouchDB, NLP, agregare, Twitter 

3. Studii de caz 
1FacultateadeAutomaticășiCalculatoare,MasterABDanul2​,UniversitateaPOLITEHNICAdinBucurești,                    
România, e‐mail: [anonimizat]

METODE DE AGREGARE IN BAZE DE DATE NOSQL 

Standardizarea textelor crește din ce în ce mai mult în popularitate deoarece 
numărul blog‐urilor, site‐urilor de socializare ce permit utilizatorul să introducă texte care să 
nu respecte, în totalitate, structura unei limbi, este din ce în ce mai pregnant. La început, 
mesajele de tip SMS erau cea mai bună sursă pentru aplicarea algoritmilor de procesare 
naturală, dar în prezent, postările de pe Twitter au devenit calup de date mai potrivit. 
Unul dintre cele mai interesante proiecte realizate folosind postările de pe 
Twitter.com este cel de​ analizare​ a sentimentelor[​10]​.​ Cercetarea celor doi profesori universitari avea ca 
principal scop determinarea polarității unui tweet: pozitiv și negativ. Lucrarea prezintă algoritmul de lemantizare 
folosit pentru a atinge țelul, dar și o comparație a două metode de determinare. 
Prima strategie folosită determina polaritatea unei postări (pozitivă, negativă sau neutră) fără să 
proceseze conținutul tweet‐ului. A două metodă, și cea cu acuratețea cea mai mare, simplifica textul până când 
rămâneau doar cele pozitive sau negative. Pentru a elimina postările neutre se verifica ca fiecare cuvânt să nu 
facă parte dintr‐o listă de elemente ce puteau stabiliti paritatea. După acestă etapă, textele rămase erau 
lematizate. Algoritmul pus la dispoziție este folosit de către compania Cilenis S.L, o companie ce se ocupă cu 
procesarea naturală​ și a fost aplicat pe limba engleză, spaniolă, portugheză și galiciană. 
În lucrarea[11] este prezentat algoritmul de căutare în timp real pe un volum mare 
de date. Pornind de la un topic, principalul scop este de a determina cele mai interesante și 
relevante informații din corpus. Sistemul folosește framework‐ul​ topic modeling​[12] pentru 
a face căutari pe tot documentul. Fiecare document este împărțit în liste de cuvinte fără a se 
ține seamă de ordinea acestora (​supertweet generation).​ Toate căutările se fac pe lista de 
supertweet‐uri generate în ultima oră. 

4. Implementare 
 
Lucrarea de față își propune să prezinte metode de agregare în bazele de date de tip NoSQL, dar și o 
comparație cu bazele de date relaționale, lucrând pe un volum mare de date din care să rezulte parametrii de 
performanță. 
Necesitatea unui volum mare de date a apărut din dorința de a observa comportamentul metodelor de 
agregare pe un număr de rânduri ce depășește 2 milioane de înregistrări. Pentru a satisface această cerință s‐a 
utilizat un dump de date colectate de pe Twitter.com[13], exclusiv în limba engleză. Fiecare dintre cele două 
tipuri de baze de date conțin aceleași informații, cu aceeiași strucutură. Datele furnizate au fost​ ​procesate 
înaintea aplicării metodelor de agregare. În următoarele secțiuni vor fi prezentate mediul de lucru, algoritmul de 
lematizare, structura bazelor de date și rezultatele observate atât pe baza de date PostgreSQL, dar și în CouchDB. 
 
 
4.1. Mediu de implementare 
 
În acestă secțiune va fi prezentat mediul de implementare și anume limbajele de 
programare folosite, structura proiectului, bibliotecile folosite, versiunile bazelor de date și 
utilitarele pentru managementul acestora. Întreg proiectul este dezvoltat pe sistemul de 
operare Linux, iar codul este versionat folosind BitBucket. 
Pentru editarea codului sursă a fost utilizat programul Eclipse, iar limbajul de 
programare ales a fost Java, alegerea lui nefiind una pur aleatoare deoarcere au fost 
utilizate biblioteci pentru lematizare dezvoltate în acest limbaj.

METODE DE AGREGARE IN BAZE DE DATE NOSQL 
 
Structura proiectul este bazată pe pachete pentru a putea separa fiecare acțiune 
desfășurată pe cele două tipuri de baze de date. În figura de mai jos este prezentată 
structura proiectului. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
După cum se observă în imaginea de mai sus au fost create 5 pachete ce vor fi 
explicate în continuare. Primul pachet este cel default ce conține clasa principală ce 
apelează restul funcțiilor. Poate fi considerată asemenea unui dispatcher ce coordonează 
toată aplicația. Următorul pachet cuprinde toate funcționalitățile sistemului de gestiune al 
bazei de date CouchDB, incluzând conectarea la baza de date, inserarea datelor, funcții 
pentru interogări. 
Pachetul ce conține parsarea fișierului cu toate posturile de pe Twitter.com, 
expandarea contracțiilor și eliminarea caracterelor speciale​ ​este denumit generic​ parser​. 
Pentru că este folosită și o bază de date relațională pentru a putea compara timpii de 
răspuns și performanța, toate clasele aferente acesteia sunt localizate în pachetul​ postgre​. 
Ultimul pachet, dar cel mai important pentru acest proiect este​ lemmantization​ și 
cuprinde toate clasele aferente lematizării datelor. Algoritmul implementat în acest pachet 
va fi detaliat în următoarele subcapitole. 
Versiunea de Postgres folosită pe parcursul întregului proiect este 9.5.0, iar pentru a 
facilita utilizarea acesteia au fost instalat pgAdmin III, iar pentru CouchDB a fost instalată 
versiunea 1.5.0, iar managemetul view‐urilor se facea din aplicația pusă la dispoziție de către 
Apache, numită Futon.

METODE DE AGREGARE IN BAZE DE DATE NOSQL 
 
 
Din punct de vedere al bibliotecilor folosite, numărul acestor este destul de mare 
având în vedere importanța proiectului. Pentru conectarea la baza de date PostgreSQL, a 
fost inclusă în proiect biblioteca „postgresql‐9.3‐1103.jdbc3” ce permite o conectare rapidă 
la baza de date, oferă posibilitatea scrierii de interogării, iar pentru conectarea la baza de 
date CouchDB a fost folosită „couchdb4j‐0.1.2”. 
În ceea ce privește lematizarea datelor, tokenizarea și extragerea părtilor de vorbire, 
biblioteca pusă la dispoziție de către Universitatea Standford[14] acoperă toate cerințele. 
Toate librăriile folosite pot fi observate în figura de mai jos.

METODE DE AGREGARE IN BAZE DE DATE NOSQL 
 
 
 
 
 
 
 
 
 
  
 
 
 
 
 
 
 
 
4.2 Structura bazelor de date 
 
Acest capitol cuprinde structura bazelor de date atât pentru PostgreSQL cât și pentru 
CouchDB. Prima data se vor prezenta tabele bazei de date PostgreSQL, legăturile dintre 
acestea și informații despre fiecare coloană în parte. 
În figura de mai jos este prezentată schema bazei de date PostgreSQL, generata cu 
ajutorul aplicației MySQL Workbench. Este de menționat faptul că, pe viitor, structura 
acestor se mai poate schimba pe măsură ce proiectul se dezvoltă.

METODE DE AGREGARE IN BAZE DE DATE NOSQL 
 
 
 
 
 
 
Primul tabel prezentat este​ twitterData​ ce conține toate posturile de pe site‐ul 
Twitter.com. Acesta este format din următoarele coloane: 
1.id – de tipul BIGINT – conține id‐ul documentului 
2.originalText – de tipul TEXT – conține textul așa cum apare pe Twitter.com 
3.cleanText – de tipul TEXT – conține textul format după expandarea contracțiilor și 
eliminarea caracterelor speciale 
4.lemmatizeText – de tipul TEXT – conține textul rezultat în urmă aplicarii lematizării și 
tokenizării 
5.publishDate – de tipul DATE – data la care a fost publicat textul 
 
După fiecare lematizare, cuvintele rezultate în urma acestui algoritm sunt  stocate în 
tabelul​ words​. Structura acestui tabel este una simplă pentru a păstra toate datele 
normalizate. 
Al treilea tabel este cel de legătură între datele stocate în​ twitterData​ și cuvintele 
aflate în tabelul​ words​. Acest tabel este format din coloanele: 
1.idWord – cheie străină

METODE DE AGREGARE IN BAZE DE DATE NOSQL 
 
 2.idTwitterData – cheie străină 
3.count – de câte ori apare în postul de pe Twitter.com 
4.t​f​ – frecvența cuvintelor 
Ultimul tabel folosit în prezent este​ tags​ și cuprinde toate elemente de tip 
hashtag[​14] și​ response people​. Aceste informații sunt utile când se dorește o clasificare a 
acestor tipuri de elemente sau când se va căuta după o anumită persoană. 
Pentru CouchDB, tabelele au aceiași structura ca cele din sistemul de gestiune 
Postgres, cu mențiunea că nu există implementat conceptul de cheie străină ceea ce 
înseamnă că aceste constrângeri trebuie respectate din cod pentru a păstra consistența 
datelor. Documentele stocate sunt de forma: 
 
{ 
   "_id": "aa0aa2d9b25e124f3414d4ea2d00098b", 
   "originalText": "I know, but I can only hope.", 
   "cleanText": "I know but I can only hope", 
   "lemmatizeText": "but=CC , can=MD , only=RB , I=PRP , know=VB , hope=NN", 
   "publishDate": "2015­10­25" 
} 
 
 
 
4.3 Algoritm de implementare 
 
În continuare vor fi descriși, în detaliu, pașii algoritmului care a stat la baza acestui 
proiect. 
Pentru a putea dezvolta noi metode de agregare pentru bazele de date NoSQL, care 
să ofere scalabilitate și timpi de răspuns mici, este nevoie de un volum mare de date. Acest 
lucru a fost posibil prin accesarea unor posturi de pe site‐ul Twitter.com. Fișierul cu aceste 
informații a fost procesat implementând o clasa numita generic​ Parser​ ce returneaza o list 
de obiecte​ TwitterData​. În timp ce fiecare rând este citit din fișier, se aplică și următorii pași: 
1.expandarea contracțiilor cu ajutorul unui vocabular întrucât biblioteca NLP nu 
operează pe cuvinte scrise în forma scurtă. A fost implementată o nouă clasă în Java 
ce returnează, pornind de la valoarea prescurtată, valoarea expandată. Un exemplu 
de cuvânt în forma scurtă este „aren't” ce se va transforma în „are not”. 
2.eliminarea caracterelor speciale precum punctele de suspensie, semnele de 
întrebare, exclamare etc. 
 
După ce acești pași au fost executați urmează extragerea tagurilor principale: 
hashtag și response to person. În ultima periodă de timp aceste metode de postare a 
informațiilor au devenit din ce în ce mai folosite, inclusiv pe marile bloguri de pe internet. Cu 
ajutorul hashtag‐urilor se pot grupa toate mesajele postate într‐o categorie asemanătoare 
cu arborii, iar tag‐ul „@” permite utilizatorului să ii atragă atenția altuia. În ciuda faptului că 
fișierul principal ce cuprindea toate mesajele postate nu stoca și numele utilizatorului, se 
pot face interogări pentru a afla în câte posturi au fost folosite anumite hashtag‐uri sau de 
câte ori o anumită persoană a comentat la un post.

METODE DE AGREGARE IN BAZE DE DATE NOSQL 
 
Partea cea mai interesantă din tot algorimul este cea de lematizare. Pentru a 
implementa acest lucru trebuie să înțelegem ce reprezintă acest proces. 
Universitatea Stanford oferă un software open‐source, dezvoltat în limbajul Java, 
pentru prelucrarea limbajului natural[15]. Prima etapă pentru lematizare este 
tokenizarea​[16]. Procesul acesta implică împărțirea unui text în mai multe secvențe. Acestă 
listă de cuvinte rezultate reprezintă datele de intrare pentru parsare. Un exemplu de 
tokenizare este: 
 
Input text: Michael is eating the cake. 
Output: Michael, is, eating, the, cake (5 tokens) 
 
Aceste token‐uri sunt des folosite sub denumirea de termeni sau cuvinte, dar este 
important să se facă diferența între token și cuvânt. Un​ token​ este o instanță de secvențe de 
caractere care sunt grupate astfel încât să poată reprezenta o unitate de procesare. Este 
necesar să se efectueze expandarea contracțiilor pentru că pot exista situații în care, în urma 
tokenizării, verbul „aren't” să aibă diferite forme. 
În limba Engleză, despărțirea în silabe este folosită pentru diferite scopuri precum 
alăturarea de substantive ca nume, divizarea cuvintelor până la vocale (co‐education) etc. 
Este ușor de observat că la prima vedere o structură de forma​ co‐education​ poate să fie 
formată dintr‐un singur token​ coeducation,​ dar structurile de forma​ San Francisco,​ în mod 
normal ar reprezenta două token‐uri ceea ce este greșit deoacere cuvintele luat separat nu 
reprezintă nimic. Este important să se facă un algoritm prin care aceste structuri să nu fie 
tokenizate în mod greșit. 
Următoarea etapă constă în extragerea părții de vorbire din token‐urile obțiune la 
pasul anterior.​ Part‐of‐speech​ sau cunoscut sub numele de  clasificarea din punct de vedere 
gramatical al cuvintelor este utilă pentru că oferă informații despre cuvânt, de exemplu 
entități sau oameni, dar și​ ​despre cuvintele învecinate (substantivele sunt precedate, în 
general, de către adjective sau verbe). 
În general acest algoritm pentru determinarea părții de vorbire este 
folosit pentru a diferenția verbele de substantive, dar poate să determine 
fiecare parte de propoziție în parte: adjective, adverbe, conjuncții etc. Se 
poate face clasificare a acestor părți de vorbire în două mari grupuri: grup 
fix și grup deschis[17]. Din primul grup fac parte prepozițiile, în timp ce 
verbele și substantivele din a doua parte. Grupul de cuvinte deschise este 
împărțit în două clase: substantive proprii (ex: IBM, Colorado etc). În 
limba Engleză acestea, în general, nu sunt precedate de articol și au prima 
literă  mare. A doua clasă este cea a substantivelor comune (ex: car, 
word, home etc). 
Există definite o listă mare de părți de propoziție, dar cea mai 
folosită listă este cea care cuprinde cele 45 de tag­uri Penn Treebank 
(figura de mai jos). Acestă listă este folosită de către seturi mari de date 
dintre care menționăm Wall Street Journal sau Switchboard.

METODE DE AGREGARE IN BAZE DE DATE NOSQL 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Ultima etapă din acest algoritm îl reprezintă eliminarea cuvintelor de oprire, numite 
în limba Engleză​ stop words.​ În general cuvintele cele mai comune, extrem de folosite, 
îngreunează căutările la nivelul unui text și trebuie eliminate. 
În cele mai multe dintre proiectele care au aceelași scop ca cel de față,​ stop 
words‐urile​ sunt determinate prin alcătuirea unor liste cu cele mai frecvente cuvinte care 
apar în document sau se implementează o listă cu toate cuvintele ce se doresc eliminate. 
De‐a lungul timpului s‐a observat că în unele sistemele de tipul IR[18] s‐a folosit o 
lista mare de cuvinte de tipul​ stop words​ (200‐300), iar​ ​în altele o lista mică de maxim 12 
termeni. În motoarele de căutare web nu s‐au folosit aceste liste. Cele mai moderne sistem 
de tipul IR s‐au axat în principal pe folosirea unui pattern care să știe să folosească cât mai 
eficient cele mai comune cuvinte. 
În cazul proiectului prezentat în acestă lucrare științifică, eliminarea cuvintelor 
comune s‐a realizat urmând pașii următorului algoritm 
1.alcătuirea unei liste ce cuprinde cuvintele ce vor fi eliminate (ex: him, none, 
the etc) 
2.verificarea dacă propoziția primită ca input conține elemente pentru 
eliminare (au fost marcate pentru ștergere toate structurile cu o lungime mai 
mica ca 2, toate care reprezintă cifre (ex: 25th) și cele care făceau parte din 
lista mai sus definită) 
3.eliminare folosind funcțiile specifice String‐urilor din Java 
 
În următoarele paragrafe se va prezenta o scurtă descriere a modului în care 
variabila​ tf‐idf(term frequency‐inverse document frequency).​ O definiție generală spune că 
reprezintă o statistică numerică menită să reflecte cât de important este un cuvânt într‐un 
document. Pentru a putea calcula​ tf‐idf​ trebuie cunoscut numărul aparițiilor a unui cuvânt în 
document. Un exemplu faimos pentru determinarea acestuia o reprezintă schema 
BM25‐Okapi[19]

METODE DE AGREGARE IN BAZE DE DATE NOSQL 
 
Există mai multe metode prin care aceste statistici pot fi determinate, dar cel mai 
simplu este cel care atributie lui​ tf​ numărul de apariții a lui​ t​ în documentul​ d,​ iar​ idf 
reprezintă logartim numărul total de documente împărțit la numărul de documente în care 
apare. Acestă metodă este folosită și în proiectul prezentat. 
În tabelul de mai jos sunt prezentate două documente și este calculată acestă 
statistică. 
 
 
Termen  Număr apariții (doc1)  Număr apariții (doc2) 
eat  2  0 
car  1  2 
women  5  0 
home  0  6 
apple  10  4 
 
 
 
tf(eat, d1) = 2 
idf(eat, d1) = log​ 2/1 = 0.30 
tf*idf = 2 * 0.30 = 0.60 
 
 
 
5. Concluzii 
 
Proiectul prezentat de‐a lungul acestui document folosește o ramură a inteligenței 
artificiale și anume NLP pentru a putea obține metode noi de agregare în bazele de date 
NoSQL. În prezent proiectul nu este finalizat, urmând să se construiască o serie de interogări 
pentru a putea analiza performanțele celor două tipuri de sisteme de gestiune a bazelor 
date, urmând să se implementeze metode de agregare noi în CouchDB. Totodată, se vor 
implementa algoritmi pentru optimizarea căutărilor, din dorintă de a avea timpi de răspuns 
mici.

METODE DE AGREGARE IN BAZE DE DATE NOSQL 
 
 
  
 
 
 
 
 
 
 
 
 
 
BIBliografie 
 
 
[1]   NoSQL, Wikipedia, Last modified 8 January 2015 
[2]   Survey on NoSQL Database, Jian Han, Haihong E, Guan Le, Jian Du 
[3]  ACID vs. BASE: The Shifting pH of Database Transaction Processing, Charles Roe, 1 March 2012 
[4]   PostgreSQL, Wikipedia, Last modified 17 January 2016 
[5]   ​"SQL Conformance"​. postgresql.org. 2013‐04‐04. Retrieved 2013‐08‐28. 
[6]   http://www.postgresql.org/docs/9.1/static/ddl‐inherit.html 
[7]   Seven Databases În Seven Weeks, Eric Redmond, Jim R. Wilson 
[8]   http://couchdb.apache.org/ 
[9]   ​http://www.corpora.heliohost 
[10] Citius: A Naive‐Bayes Strategy for Sentiment Analyst on English Tweets, Pablo Gamallo, Marcos Garcia 
[11]OnlineTopicModelingforReal‐timeTwitterSearch,ChristianGrant,ClintP.George,ChrisJenneischand                        
Joseph N. Wilson 
[12] Topic model, Wikipedia 
[13] ​http://nlp.stanford.edu/software/tokenizer.shtml 
[14] Hashtag, Wikipedia, 
[15] ​http://nlp.stanford.edu/software/#projects 
[16] ​http://nlp.stanford.edu/software/tokenizer.shtml 
[17] ​https://web.stanford.edu/~jurafsky/slp3/9.pdf 
[18] Information retrieval, Wikipedia, Last modified 22 December 2015 
[19] Okapi BM25, Wikipedia