Tree-Framework, oceńcie ... i używajcie Opcje

[Jabol]

Kiedyś dawno temu zrobiłem ładny system obsługi drzewek. Teraz leży u mnie na kompie i się marnuje a tutaj na forum conajmniej raz na tydzień ktoś o to pyta. Dlatego zamieszczam. Dodam tylko, że sama struktura nie jest moim pomysłem:
Struktura:

[SQL] pobierz, plaintext 
CREATE SEQUENCE contents_increment
  START 1
  INCREMENT 1
  MAXVALUE 9223372036854775807
  MINVALUE 1
  CACHE 1;
CREATE SEQUENCE nodes_increment
  START 1
  INCREMENT 1
  MAXVALUE 9223372036854775807
  MINVALUE 1
  CACHE 1;
CREATE TABLE contents (
  id bigint DEFAULT NEXTVAL('contents_increment'::text) NOT NULL,
  content text
);
CREATE TABLE nodes (
  id bigint DEFAULT NEXTVAL('nodes_increment'::text) NOT NULL,
  parent bigint,
  name character varying(100)
);
CREATE TABLE asociations (
  first_id bigint DEFAULT 0 NOT NULL,
  second_id bigint DEFAULT 0 NOT NULL,
  depth bigint DEFAULT 0 NOT NULL
);
CREATE TABLE binds (
  node_id bigint DEFAULT 0 NOT NULL,
  content_id bigint DEFAULT 0 NOT NULL
);
CREATE INDEX nodes_parent_ind ON nodes USING btree (parent);
CREATE INDEX asociations_second_id_depth_ind ON asociations USING btree (second_id, depth);
CREATE INDEX asociations_first_id_depth_ind ON asociations USING btree (first_id, depth);
CREATE INDEX asociations_first_id_ind ON asociations USING btree (first_id);
CREATE INDEX asociations_second_id_ind ON asociations USING btree (second_id);
ALTER TABLE ONLY nodes
  ADD CONSTRAINT nodes_parent_name_key UNIQUE (parent, name);
ALTER TABLE ONLY nodes
  ADD CONSTRAINT nodes_pkey PRIMARY KEY (id);
ALTER TABLE ONLY nodes
  ADD CONSTRAINT "$1" FOREIGN KEY (parent) REFERENCES nodes(id) ON UPDATE NO ACTION ON DELETE CASCADE;
ALTER TABLE ONLY contents
  ADD CONSTRAINT contents_pkey PRIMARY KEY (id);
ALTER TABLE ONLY binds
  ADD CONSTRAINT binds_node_id_content_id_key UNIQUE (node_id, content_id);
ALTER TABLE ONLY binds
  ADD CONSTRAINT binds_pkey PRIMARY KEY (node_id, content_id);
ALTER TABLE ONLY binds
  ADD CONSTRAINT "$1" FOREIGN KEY (content_id) REFERENCES contents(id) ON UPDATE CASCADE ON DELETE CASCADE;
ALTER TABLE ONLY binds
  ADD CONSTRAINT "$2" FOREIGN KEY (node_id) REFERENCES nodes(id) ON UPDATE CASCADE ON DELETE CASCADE;
ALTER TABLE ONLY asociations
  ADD CONSTRAINT asociations_pkey PRIMARY KEY (first_id, second_id);
ALTER TABLE ONLY asociations
  ADD CONSTRAINT "$1" FOREIGN KEY (second_id) REFERENCES nodes(id) ON UPDATE NO ACTION ON DELETE CASCADE;
ALTER TABLE ONLY asociations
  ADD CONSTRAINT "$2" FOREIGN KEY (first_id) REFERENCES nodes(id) ON UPDATE NO ACTION ON DELETE CASCADE;
SELECT pg_catalog.SETVAL ('nodes_increment', 1, true);
SELECT pg_catalog.SETVAL ('contents_increment', 1, true);
INSERT INTO nodes (id, parent, name) VALUES (1, NULL, 'main');
INSERT INTO asociations (first_id, second_id, depth) VALUES (1, 1, 0);
[SQL] pobierz, plaintext 

Api:

[SQL] pobierz, plaintext 
-- get_path
DROP FUNCTION get_path (bigint);
CREATE FUNCTION get_path (bigint) RETURNS text
  AS '
DECLARE
 
  nid ALIAS FOR $1;
  path TEXT;
  item RECORD;
 
BEGIN path := ''/''::TEXT;
 
  FOR item IN SELECT n.name FROM nodes n, asociations a WHERE n.id = a.first_id AND a.second_id = nid ORDER BY a.depth DESC LOOP
 
    path := path || item.name || ''/''::TEXT;
 
  END LOOP;
 
  RETURN path;
 
END;
'
  LANGUAGE plpgsql;
 
-- mkdir
DROP FUNCTION mkdir (character varying, bigint);
CREATE FUNCTION mkdir (character varying, bigint) RETURNS BOOLEAN
  AS '
DECLARE
 
  nn ALIAS FOR $1;
  np ALIAS FOR $2;
 
BEGIN INSERT INTO nodes (name, parent) VALUES (nn, np);
 
  INSERT INTO asociations (first_id, second_id, depth) SELECT first_id, (SELECT id FROM nodes WHERE name = nn AND parent = np), depth + 1 FROM asociations WHERE second_id = np;
 
  INSERT INTO asociations (first_id, second_id, depth) VALUES((SELECT id FROM nodes WHERE name = nn AND parent = np), (SELECT id FROM nodes WHERE name = nn AND parent = np), 0);
 
  RETURN true;
 
END;
'
  LANGUAGE plpgsql;
 
-- mv
DROP FUNCTION mv (bigint, bigint);
CREATE FUNCTION mv (bigint, bigint) RETURNS BOOLEAN
  AS '
 
DECLARE
 
  nid ALIAS FOR $1;
  np ALIAS FOR $2;
  temp1 RECORD;
  temp2 RECORD;
 
BEGIN FOR temp1 IN SELECT MAX(depth) AS max, second_id FROM asociations WHERE first_id = nid GROUP BY second_id LOOP
 
    DELETE FROM asociations WHERE second_id = temp1.second_id AND depth > temp1.max;
 
  END LOOP;
 
  UPDATE nodes SET parent = np WHERE id = nid;
 
  INSERT INTO asociations (first_id, second_id, depth) SELECT first_id, nid, depth + 1 FROM asociations WHERE second_id = np;
 
  FOR temp2 IN SELECT second_id, depth FROM asociations WHERE first_id = nid AND depth <> 0 LOOP
 
    INSERT INTO asociations (first_id, second_id, depth)
    SELECT first_id, temp2.second_id, depth + temp2.depth
    FROM asociations WHERE second_id = nid AND depth <> 0;
 
  END LOOP;
 
  RETURN true;
 
END;
'
  LANGUAGE plpgsql;
 
-- mknode
DROP FUNCTION mknode (character varying, bigint);
CREATE FUNCTION mknode (character varying, bigint) RETURNS BOOLEAN
  AS '
 
DECLARE
 
  nn ALIAS FOR $1;
  np ALIAS FOR $2;
 
BEGIN INSERT INTO nodes (name, parent) VALUES (nn, np);
 
  INSERT INTO asociations (first_id, second_id, depth) SELECT first_id, (SELECT id FROM nodes WHERE name = nn AND parent = np), depth + 1 FROM asociations WHERE second_id = np;
 
  INSERT INTO asociations (first_id, second_id, depth) VALUES((SELECT id FROM nodes WHERE name = nn AND parent = np), (SELECT id FROM nodes WHERE name = nn AND parent = np), 0);
 
  RETURN true;
 
END;
'
  LANGUAGE plpgsql;
 
-- mkcontent
DROP FUNCTION mkcontent (bigint);
CREATE FUNCTION mkcontent (bigint) RETURNS bigint
  AS '
 
DECLARE
 
  id ALIAS FOR $1;
  record RECORD;
 
BEGIN SELECT lastvalue AS id INTO record FROM contents_increment; INSERT INTO contents ( id, content ) VALUES ( record.id, cnt );
  INSERT INTO binds ( node_id, content_id ) VALUES ( id, record.id );
  RETURN true;
 
END;
'
  LANGUAGE plpgsql;
 
-- link
DROP FUNCTION link (bigint, bigint);
CREATE FUNCTION link (bigint, bigint) RETURNS BOOLEAN
  AS '
INSERT INTO binds (content_id, node_id) VALUES ($1, $2);
SELECT TRUE;
'
  LANGUAGE sql;
 
-- rm
DROP FUNCTION rm (bigint);
CREATE FUNCTION rm (bigint) RETURNS BOOLEAN
  AS '
DELETE FROM nodes WHERE id = $1;
SELECT TRUE;
'
  LANGUAGE sql;
[SQL] pobierz, plaintext 

Polecam wszystkim, bo mi naprawdę szkoda, że moja praca się marnuje a sam nie mam co z tym zrobić.

Jeżeli jest odpowiedniejsze forum to proszę o przeniesienie.

Ojojoj, wyszedłem poza limit długości posta.

Teraz jeszcze jakby jacyś linuksiarze z Was chcieli potestować i potrzebowali danych testowych to polecam:

Kod

#include<stdlib.h>
#include<errno.h>
#include<dirent.h>
#include<stdio.h>
#include<fcntl.h>
#include<sys/stat.h>
#include<sys/types.h>

#define FALSE 0
#define TRUE !FALSE

int id;
int fid;

void *xmalloc(size_t size)
{
  void *ptr;

  if((ptr=malloc(size))==NULL)
    syserr("malloc");
  memset(ptr, 0, size);
  return ptr;
}

void xfree(void *ptr)
{
  if(ptr)
  free(ptr);
}

void writeFile(const char *path)
{
  FILE *fp;
  int c;
  if((fp=fopen(path, "r"))==NULL)
    syserr("fopen");
  while((c=fgetc(fp))!=EOF)
  {
    if(c=='\\'||c=='\'')
      printf("%c", '\\');
    printf("%c", c);
  }
  if(fclose(fp)!=0)
    syserr("fclose");
}

int isRegular(const char *path)
{
  struct stat st;

  if( stat( path, &st ) == -1 )
    return FALSE;
  return ( S_ISREG( st.st_mode ) );
}

int isDir(const char *path)
{
  struct stat st;

  if( stat( path, &st ) == -1 )
    return FALSE;
  return ( S_ISDIR( st.st_mode ) );
}

unsigned long int insertDir(const char *name, const int pid)
{
  extern int id;

  id++;
  printf("INSERT INTO nodes ( id, name, parent) VALUES ( %d, '%s', %d);\n", id, name, pid);
  printf("INSERT INTO asociations ( first_id, second_id, depth ) SELECT first_id, %d, depth + 1 FROM asociations WHERE second_id = %d;\n", id, pid);
  printf("INSERT INTO asociations ( first_id, second_id, depth ) VALUES ( %d, %d, 0 );\n", id, id);
  return id;
}

void insertFile(const char *path, const char *name, const int pid)
{
  extern int id;
  extern int fid;

  id++;
  fid++;
  printf("INSERT INTO nodes ( id, name, parent) VALUES ( %d, '%s', %d );\n", id, name, pid);
  printf("INSERT INTO asociations ( first_id, second_id, depth ) SELECT first_id, %d, depth + 1 FROM asociations WHERE second_id = %d;\n", id, pid);
  printf("INSERT INTO asociations ( first_id, second_id, depth ) VALUES ( %d, %d, 0 );\n", id, id);
  printf("INSERT INTO contents ( id, content ) VALUES ( %d, '", fid);
  writeFile(path);
  printf("' );\n");
  printf("INSERT INTO binds (node_id, content_id) VALUES (%d, %d);", id, fid);
}

int insert(const char *path, const int pid)
{
  DIR *dir;
  struct dirent *dent;
  char *nodepath;
  unsigned long int npid;


  if((dir=opendir(path))==NULL)
    return TRUE;
  while((dent=readdir(dir))!=NULL)
  {
     if((strcmp(dent->d_name, ".")==0)||(strcmp(dent->d_name,"..")==0)||(strcmp(dent->d_name,"dev")==0)||(strcmp( dent->d_name,"proc")==0))
     {
      continue;
    }
    nodepath=(char *)xmalloc(strlen(path)+strlen(dent->d_name)+2);
    sprintf(nodepath, "%s/%s", path, dent->d_name);
    if(isDir(nodepath))
    {
      npid=insertDir(dent->d_name, pid);
      insert(nodepath, npid);
    }
    else if(isRegular(nodepath))
    {
      insertFile(nodepath, dent->d_name, pid);
    }
    xfree(nodepath);
  }
  if(closedir(dir)==-1)
    syserr("closedir");
  return TRUE;
}

int main(int argc, char *argv[])
{
  extern int id;
  extern int fid;

  id=1;
  fid=0;
  if(argc<2)
    syserr("argc");
  if(insert(argv[1], id)==FALSE)
    syserr("insert");

  return 0;
}

oraz error.c

Kod

#include<stdio.h>
#include<errno.h>
#include<fcntl.h>

void syserr(char *msg)
{
  fprintf(stderr, "ERROR: %s ( %d", msg, errno);
  if(errno>0 && errno<sys_nerr)
    fprintf(stderr, "; %s )\n", strerror(errno));
  else
    fprintf(stderr, " )\n");
  exit(1);
}

Mam nadzieję, że nie muszę dodawać, że framework jest na pgsql (choć łatwo go przerobić, bo pgsql jest prostym językiem).
I mam też nadzieję, że nie muszę dodawać, że program kompiluje się

Kod

gcc -o pgins pgins.c error.c

a używa

Kod

./pgins /katalog/do/insertowania | insert.sql

[mariuszn3]

Drzewek to znaczy masz na myśli coś takiego jak XML?
To może dorzucę swoje pare groszy.
Też ostatnio stałem przed problemem jak zapisywać to w bazie. W pierwszej fazie poszukiwań trafiłem na dedykowane rozwiązania tego problemu - istnieją systemy bazodanowe stworzone do przechowywania tego typu danych ('Native XML database')
Sprawdzałem exist'a i działa bardzo sprawnie. W php można się z tym łączyć przez SOAP czy REST, brakowało mi jedynie cache'owania zapytań.
Ostatecznie jednak jako, że nie potrzebowałem aż tak zaawansowanych możliwości przeszukiwania danego drzewa (w zasadzie chodziło mi tylko o to by móc to drzewo gdzieś zapisać i je później odczytać) pozostałem przy MySQL i po prostu ładowania drzewa XML w jedno pole tabeli.

Podejrzewam, że Twój pomysł dla kogoś kto nie za bardzo łapie XML i nie planuje bądź nie ma czasu się uczyć formułowania zapytań poprzez XQuery może być bardzo przydatny.

[LBO]

Jak dla mnie Zyx'owy sposób jest najlepszy...

[mariuszn3]

Jak dla mnie Zyx'owy sposób jest najlepszy...

Dziwi mnie, że w tym artykule w ogóle nie pada słowo XML czy może lepiej DOM przecież dokładnie o taką strukturę chodzi.
EDIT: angielski artykuł tam z linkowany już wspomina o XML

Ten post edytował mariuszn3 25.07.2006, 20:42:44

[Seth]

Drzewka to nie tylko XML (a raczej jego zagniezdzona struktura), ale to takze grafy czy inne struktury polaczonych list

Ten post edytował Seth 25.07.2006, 21:33:50

[mariuszn3]

Drzewka to nie tylko XML (a raczej jego zagniezdzona struktura), ale to takze grafy czy inne struktury polaczonych list

Nie bardzo rozumiem co masz na myśli, czym jest według Ciebie zagnieżdżona struktura XML? Co to są grafy i inne struktury połączonych list, które można zapisać w powyższej bazie a w XML'u już nie

[bela]

A na matmie w podstawówce spałeś? http://pl.wikipedia.org/wiki/Graf_%28matematyka%29
http://pl.wikipedia.org/wiki/Lista

[mariuszn3]

A na matmie w podstawówce spałeś? http://pl.wikipedia.org/wiki/Graf_%28matematyka%29
http://pl.wikipedia.org/wiki/Lista

Pytałem Setha co konkretnie miał na myśli, bo nie widzę tutaj niczego co można zapisać w tej bazie a nie można zapisać w XML.. moim zdaniem jest zupełnie odwrotnie.

[Jabol]

Że tak to nazwę. Dokładnie jak napisałeś - można zapisać w XML-u, można i w bazie. Nie negowałbym istnienia czegoś tylko dlatego, że można to zrobić w XML-u. Pamiętaj też, że XML to pliki które należy przetważać i nie wiem czy wszystkie parsery poradzą sobie z olbrzymimi plikami, które baza z taką strukturą obsługuje bez problemu. Osobiście też nie lubię XML'a.

A poza tym spójrz na to z innej strony - wiesz ile miałem zabawy jak to pisałem . Zauważ, że to są naprawdę fajne algorytmy.

[mariuszn3]

Absolutnie tego nie neguję.. nie o to mi chodziło..
Po prostu uważam, że przy podawaniu tego typu przykładów trzeba wspomnieć o XML'owych bazach danych - nie mówię tu o plikach XML ale o natywnych XML'owych bazach danych, które mogą przechowywać i terrabajty danych.. są to pełnowartościowe bazy danych z takim samym podejściem do wydajności jak MySQL czy inne tradycjne bazy z tą różnicą, że one są dedykowane strukturze węzłowej, po prostu do szybkich operacji na przechowywanych drzewach DOM. Link dla zainteresowanych

Jednak nie wszyscy mają możliwość postawienia sobie serwera eXist czy innej XML'owej bazy danych pomijając, że nie każdy miał do czynienia z XML'em i dlatego dla wielu to co napisałeś na pewno może się okazać bardzo przydatne.