[Vari] Sottospecie di contest: implementare un DBMS.

[Vincenzo1968]

Implementiamo un DBMS. Non è un contest vero e proprio. Potremo prenderci tutto il tempo che ci serve.

Per quale motivo? Non esistono già ottimi DBMS commerciali e freeware/open source?

Risposta: per pura e semplice curiosità. Per motivi didattici. Per cercare di capire gli algoritmi che stanno sotto le implementazioni dei DBMS più diffusi. etc, etc.

Che ne dite?

----------------------------------------------------------------------------------
Documentazione utile:

http://www.csd.uoc.gr/~hy460/pdf/000.pdf
http://infolab.stanford.edu/~ullman/dbsi.html

http://pages.cs.wisc.edu/~dbbook/

http://pi3.informatik.uni-mannheim.d...rycompiler.pdf
http://pi3.informatik.uni-mannheim.d...s04/folien.pdf
http://pi3.informatik.uni-mannheim.de/moerkotte.html

-----------------------------------------------------------------------------------

Questi i link ai contest precedenti:

Contest 1: Bitmap

Contest 2: Ricerca

Contest 3: La somma

Contest 4: DNA

Contest 5: Sottomatrici

Contest 6: Parsing

Contest 7: Il lotto

Proposta

Contest 8: Compattamento Barionico

Contest 9: Divisori dei numeri triangolari

Contest 10: Numeri palindormi (Semplice)

Contest 11: Change. NP-Hard.

Contest 12: Il muro

Contest 13: Date

Contest 14: Corsa delle macchine

Contest 15: sudoku

Contest 16: Intervalli

Contest 17: Compilatori e interpreti. Parte I: interpreti.

Contest 18: T9 lookalike

[gugoXX]

Vado via 2 settimane senza computer...
Pensero'.

Per intanto, iscritto.

[Vincenzo1968]

Non importa. Come detto sopra non c'è nessuna fretta. Possiamo impiegarci anche un anno(due, tre, la vita intera).

[Vincenzo1968]

Per la documentazione si può consultare anche "The Art of Computer Programming" Vol. III, 6.5.4 Multiway Trees:

http://www-cs-faculty.stanford.edu/~knuth/

http://www-cs-faculty.stanford.edu/~knuth/taocp.html

http://www-cs-faculty.stanford.edu/~knuth/books.html

[shinya]

Non ho capito: ognuno dovrebbe farsi il suo o è un progetto comune?

[Vincenzo1968]

Originariamente inviato da shinya

Non ho capito: ognuno dovrebbe farsi il suo o è un progetto comune?

Ognuno può fare come vuole. Ci si può associare con altri utenti o fare tutto da soli. La cosa importante è divertirci ed imparare.

Si può contribuire anche elencando semplicemente una serie di link utili(contenenti, per esempio, pdf o ps) sull'argomento.



Edit: per documentare il proprio DBMS sarebbe meglio fornire pdf o ps invece di scrivere post chilometrici. Potete creare i documenti con TeX Live:

http://www.tug.org/texlive/

o col vostro editor WYSIWYG(l'avrò scritto nel modo giusto?) preferito.

[nico159]

Secondo me, introdurre qualcosa di nuovo (come ha fatto CouchDB http://en.wikipedia.org/wiki/CouchDB) oppure creare qualcosa di specializzato (come VoltDB http://en.wikipedia.org/wiki/VoltDB che è nato per girare interamente in ram) darebbe una spinta in più al progetto, una ragione di esistere

[Vincenzo1968]

Ciao Nico,

come detto sopra sei libero d'implementare il sistema nel modo che preferisci. Puoi farlo interamente da solo o ti puoi associare con qualcuno.

Io il mio lo faccio in C per la parte Server e in C++/QT per la parte Client.

[Vincenzo1968]

Ah! dimenticavo: è chiaro che, oltre alla documentazione e ai binari, bisogna fornire il codice sorgente.

[Vincenzo1968]

Originariamente inviato da coffe_killer

scusate ma non ho capito lo scopo del contest...potreste spiegarvi meglio?

Originariamente inviato da Vincenzo1968

Implementiamo un DBMS. Non è un contest vero e proprio. Potremo prenderci tutto il tempo che ci serve.

Per quale motivo? Non esistono già ottimi DBMS commerciali e freeware/open source?

Risposta: per pura e semplice curiosità. Per motivi didattici. Per cercare di capire gli algoritmi che stanno sotto le implementazioni dei DBMS più diffusi. etc, etc.

...

http://www.hwupgrade.it/forum/showpo...1&postcount=27

Originariamente inviato da cionci

Data Base Management System

SQL Server, MySQL, Oracle...

E' molto istruttivo perchè impari a lavorare con i file, con le strutture, volendo ti devi fare anche l'interprete SQL...poi andando avanti ci puoi aggiungere ciò che ti pare... Connessione tramite socket (quindi internet)... E' davvero completo come percorso di apprendimento...

Ovviamanete ci dovresti lavorare molto e dovresti studiare molto...

[msangi]

Contest molto interessante

[Vincenzo1968]

Dunque, i moduli inizialiali in cui vorrei suddividere il programma sono i seguenti:

- File manager
- Buffer Manager

Il file manager tiene traccia dello spazio disponibile su disco e si occupa dell'organizzazione fisica di record e campi.
Il buffer manager si occupa di allocare e gestire le pagine di 4 KB quando il file manager deve leggere/memorizzare uno o più record.
Per gli indici utilizzerò i B+Tree.

http://en.wikipedia.org/wiki/B%2B_tree
http://www.cecs.csulb.edu/~monge/cla...eeIndexes.html

I documenti originali:

http://www.liacs.nl/~graaf/STUDENTENSEMINARIUM/OMLO.pdf

http://people.cs.aau.dk/~simas/aalg06/UbiquitBtree.pdf

[Vincenzo1968]

In Windows posso utilizzare la funzione api GetSystemInfo per sapere la dimensione di una pagina(tramite il campo dwPageSize della struct SYSTEM_INFO):

http://msdn.microsoft.com/it-it/libr...=vs.85%29.aspx

http://msdn.microsoft.com/it-it/libr...=vs.85%29.aspx

http://msdn.microsoft.com/it-it/libr...=vs.85%29.aspx

E Linux? Come faccio? E dove la trovo la documentazione della api? La trovo da qualche parte nel sistema o la devo scaricare? E da dove? Che libri devo comprare?

[The_ouroboros]

http://www.cyberciti.biz/faq/linux-c...e-of-pagesize/

[Vincenzo1968]

Grazie mille The_ouroboros!

Ho deciso di comprare questo libro:



http://my.safaribooksonline.com/book.../9780321638014

Ho trovato anche questo corso:

http://www.cs.stevens.edu/~jschauma/631/

[The_ouroboros]

Originariamente inviato da Vincenzo1968

Grazie mille The_ouroboros!

Ho deciso di comprare questo libro:



http://my.safaribooksonline.com/book.../9780321638014

nulla, nel mio piccolo voglio aiutare

p.s: libricino

[Vincenzo1968]

Aspetta, aspetta...

Nel link che mi hai segnalato c'è il comando da digitare nella shell. Nel mio sistema restituisce 4096.

Io cerco una funzione api in modo da ricevere l'informazione via codice C. Mo vedo nel corso online che ho trovato.

Grazie comunque

[The_ouroboros]

Originariamente inviato da Vincenzo1968

Aspetta, aspetta...

Nel link che mi hai segnalato c'è il comando da digitare nella shell. Nel mio sistema restituisce 4096.

Io cerco una funzione api in modo da ricevere l'informazione via codice C. Mo vedo nel corso online che ho trovato.

Grazie comunque

mmm... forse con sysctl o giu per quella strada

[Vincenzo1968]

Trovato "sysconf":

http://linux.die.net/man/3/sysconf
http://linux.die.net/man/2/getpagesize

http://www.kernel.org/doc/man-pages/...sysconf.3.html

http://nadeausoftware.com/articles/2...ry_size_system

[ingframin]

Io ho iniziato a scrivere questo:

class Node:
    def __init__(self):
        self.content = []
        self.left = None
        self.middle = None
        self.right = None
        
        
    def insert(self,v):
        if len(self.content) == 0:
            self.content.append(v)
            return
        
        if len(self.content) == 1:
            self.content.append(v)
            self.content.sort()
            return

        if len(self.content) == 2:
            if v>self.content[0] and v<self.content[1]:
                if self.middle is None:
                    self.middle = Node()
                    self.middle.insert(v)
                else:
                    self.middle.insert(v)
                
                return
            
            if v<self.content[0]:
                if self.left is None:
                    self.left = Node()

                self.left.insert(v)
                return

            if v>self.content[1]:
                if self.right is None:
                    self.right = Node()
                self.right.insert(v)
                return
            
    def search(self,v):
        try:
            if v in self.content:
                return (self.content,self.content.index(v))
            elif v<self.content[0]:
                return self.left.search(v)
            elif v>self.content[0] and v<self.content[1]:
                return self.middle.search(v)
            else:
                return self.right.search(v)
        except:
            raise KeyError

Che e' l'inizio di implementazione di un B-tree in Python.
Una volta che ho capito come funziona poi posso o passare a cose piu' sofisticate tipo B+tree o B*tree et similia oppure posso implementarlo in C e fare un modulo richiamabile da Python.
Ogni commento sul mio codice e' bene accetto