Hierarkiske data

Mange af mine projekter håndterer data der har en eller anden form for hierarkisk struktur. Når jeg designer mine interne datastrukturer overvejer jeg først og fremmest om jeg har et hierarki eller ikke har et hierarki. Jeg genneløber mine data rekursivt, ikke iterativt. (Ja, jeg er miljøskadet...)

Men når jeg så skal gemme mine data på disken må jeg foretage et paradigmeskift: Hverken de relationelle databaser eller de nymoderne dokumentbaserede databaser virker særlig velegnede. Jeg kan selvfølgelig løse mit problem med SQL, men det ender oftest med en brede-først søgning hvor de enkelte forespørgsler bliver større og større. Det er måske effektivt nok, men det generer mig æstetisk.

De grundlæggende hierarkiske operationer jeg har behov for er at hente alle elementer i et hierarki, flytte et delhierarki (atomisk) og slette et delhierarki (helst atomisk). Og så selvfølgelig kunne oprette og slette elementer i hierarkiet.

Prototypen er selvfølgelig filsystemer, men er det virkelig det eneste system vi har til hirarkiske data? Jeg blev så glad da jeg i en Riak-tutorial kom til Link walking. Men ak, igen er skal jeg hardkode antallet af niveauer...

Kommentarer (49)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Karsten Nyblad

Hvis det er vigtigere at programmet er let at skrive og vedligeholde, end at performance er i top, så er XML og XSL en mulighed. XML er per hatur et hierarkisk opbygget dataformat. XSL er et programmeringssprog til transformation af XML til XML, HTML og text. XSL har gode faciliter til at søge i et XML document. XSL er et generelt programmeringssprog i den forstand, at der er alle de elementer, der skal til, for at kunne implementere et hvert program inklusive en Turing maskine.

Problemet er, at performance i hvertfald i nogen implementeringer sutter. Jeg har prøvet at skrive "rigtig" kode i XSL, til en gammel implementering fra Microsoft, og jeg måtte smide koden ud pga alt for stort resurseforbrug.

Man kan dog lave queries i XSL fra andre programmeringssprog, stort set som man laver queries i SQL.

En af de store fordele ved denne løsning er, at det er nemt at dokumnetere dokumentformetet, og der findes automatiske værktøjer, der kan tjekke, at man holder sig inden for det definerede. Samtidigt kan se sin XML fil i en god gammeldags teksteditor eller i en web browser.

  • 1
  • 0
Peter Makholm Blogger

Som du kan se har jeg konsekvent stavet det korrekt i brødteksten, men i overskriften har jeg ikke ramt e'et hårdt nok. Lige i øjeblikket kan jeg slet ikke finde en edit-knap, men jeg ville også væer lidt forsigtig med at rette overskrifter som indgår i url'en.

  • 1
  • 0
Troels Arvin

Du taler vel i virkeligheden om en form for "impedance mismatch"? Dette begreb støder man oftest på, når OO-programmører hævder, at den relationelle model er besværlig.

Har du overvejet, om Neo4j kan nedbryde noget af denne impedance mismatch?

Bemærk, også, at de fleste databasesystemer efterhånden er blevet ret gode til rekursiv SQL; eneste betydende undtagelse er efterhånden MySQL. Selv Oracle har fået understøttelse for ISO SQL's WITH RECURSIVE konstruktion. Se også http://vadimtropashko.wordpress.com/2008/08/09/one-more-nested-intervals... som dog er skrevet før Oracle fik understøttelse for ISO SQL's rekursive SQL features.

  • 1
  • 0
Martin Bøgelund

Jeg er rendt på et fænomen man kan kalde "hierarki-koder".

De går ud på at du i din datamodel tilføjer en kolonne som attribut til dine objekter.

Hierarki-koden kan tage sig ud som "A" for roden, "AA" som første element i rodens undertræ, så "AB" som første søskende til "AA", "AAA" til "AA"'s første barn, og så fremdeles.

Det er et hierarkisystem med en masse fordele.

  • Hvis du vil flytte "AAAAA" fra "AA"'s undertræ til "AB"'s undertræ, men beholde elementet på samme niveau, giver du den koden "ABAAA".
  • Niveauet i træet er den samme som længden af strengen (eller længden minus 1 hvis du insisterer på at tælle fra 0)
  • Find alle elementer på laveste niveau i "AB"'s undertræ: Længde af hierarki-koden skal være lig max-længde, og hierarki-koden skal starte med "AB".
  • Hvis du vil have en anden sorteringsrækkefølge end elementets navn eller ID, kan du lade hierarki-koden være sorteringsrækkefølgen.
  • Det er meget læsevenligt når du browser dine data, i modsætning til eksempelvis en parent-child relation.
  • Du kan også variere selve udformningen, f.eks. med delimeters og flere tegn pr niveau, f.eks. "/001/044/115"
  • ... og mange andre lavpraktiske fordele

Jeg har aldrig været begejstret for hierarki-koder på det teoretiske plan - vi kan sagtens opremse en masse ting vi kan rynke på næsen af ved den tilgang.

Men i de sammenhænge hvor jeg har skullet anvende data der er blevet skabt med hierarki-koder, har de gang på gang vist sig at være et fantastisk værktøj til at håndtere hierarki-operationer.

  • 1
  • 0
Troels Arvin

Martin: Jeg vil hævde, at mere gængse betegnelser for dét er "materialized path" eller "path enumeration". I MSSQL har man sågar introduceret en speciel datatype til formålet, "hierarchyid".

Men materialized path er blot én blandt flere modeller for at repræsentere hierarkier. Se link'et, som jeg nævnte ovenfor, hvor Vadim Tropashko gennemgår fordele/ulemper ved de forskellige modeller.

  • 2
  • 0
Lars Malmgren

Hej Peter

Du skulle tage og kikke på Intersystems Caché databasen.

Den er internt en ægte hierarkisk database baseret på dynamiske arrays og programmeringssproget MUMPS.
Ovenpå dette ligger et højniveau objektorienteret lag med SQL understøttelse.
Dvs. du kan bygge din database op omkring objekter med mulighed for integrere disse objekter direkte i et java-program samt at kunne tilgår de underliggende tabeller via SQL.
Dækker dette ikke dit behov, så har du mulighed for at arbejde på databasens underliggende strukturer vha MUMPS. Her arbejder du direkte med de dynamiske arrays.
Nå ja, som bonus er databasen utrolig hurtig - også med enorme datamængder.

Hent en gratis prøveversion her:
http://www.intersystems.com/cache/

PS. jeg hverken repræsenterer Intersystems eller er sælger af licenser el.
Jeg benytter Caché i mit arbejde med EPJ i DK.

  • 1
  • 0
Peter Lind

Nested sets performer ikke godt hvis du har mange ændringer i dine data - så vil du opleve mange kostbare updates (du vil i snit skulle opdatere halvdelen eller over af alle rækker i et table, hvis du tilføjer eller fjerner en node).

That said, så er det et spørgsmål om use-case: nested sets er gode til en ting, mens en løsning som materialized path klarer andre ting godt.

  • 0
  • 0
Peter Makholm Blogger

Som det klart fremgår af Wikipediasiden, så er 'nested sets' ikke velegnede til at flytte delhiererkier og til at oprette nye elementer i hierarkier. Det er for mig derfor en nogo.

Men jeg er igang med at læse nogle af referencerne Vadim Tropashko leder mig hen til.

  • 0
  • 0
Jørn Wildt

Ja, ændringer er, i gennemsnit, lineære i antallet af elementer. Til gengæld kan de udføres i ret simple og vel-performende updates (som selvfølgelig stadig er lineære i tid, men dog med ret små konstanter, da det er database-motoren der står for arbejdet (altså uden netværkstrafik)).

Og hvis man ved at man har mange updates i ét batch, så kan man udsætte beregningen af venstre/højre-værdier til sidst.

Anyways, ja, det er i sidste ende et spørgsmål om use-case.

  • 0
  • 0
Peter Nørregaard Blogger

Måske en off-topic kommentar, men fedt at se så mange bidrage med så god viden om emnet. Har selv arbejdet med hierarkier repræsenteret med AAA.AAB.AAA - det virkede ret fint, også med XSL-transformationer til brug for afhængige dropdown-lister i en GUI.

  • 1
  • 0
Carsten Sonne

Hierarkiske strukturer benævnes i datalogiske termer som træer eller træstrukturer.

Træstrukturer er bredt anvendt, både i algoritmer, i storage formater og som faglige værktøjer. De fleste kender vel til XML og beslægtede fil formater.

Træer anvendes også til klassificering i sundhedsvæsnet. SKS systemet er en hovednerverne sundhedsfaglig IT:
http://medinfo.dk/sks/brows.php

Og selv om det måske er uskik at referere til eget arbejde, vil jeg alligevel også nævne beslutningstræer i sygehusvæsnets afregningstakster:
http://visualdrg.sst.dk/Default.aspx

I byggeriet arbejder man i øjeblikket på DBK systemet, Dansk Bygge Klassifikation:
http://wikibyg.dk/Dansk_Bygge_Klassifikation

I kompilere arbejder man med syntakstræer og parsertræer:
http://en.wikipedia.org/wiki/Abstract_syntax_tree

Bl.a. hos Google vil jeg gætte på man arbejder med søgetræer:
http://en.wikipedia.org/wiki/Binary_search_tree

Listen og anvendelsen af træstrukturerer er tæt på uendelig lang.

  • 0
  • 0
Casper Bang

Når jeg designer mine interne datastrukturer overvejer jeg først og fremmest om jeg har et hierarki eller ikke har et hierarki.

Et hieraki er jo blot et subset af en graf der er nemmere at arbejde med (repræsentere, travasere, serialisere mv.). Jeg vil påstå at vi udviklere oftest arbejder med et hieraki, men at vi i virkeligheden har med en graf at gøre nedenunder.

En programbeskrivelse er jo bare én stor state machine, udtrykt som et AST i en fil. En database er også bare en graf, men vi kommunikerer med den via hierakiske projektioner hvilket ofte er problematisk (ORM problematikken). Et kørende program er ligeledes en graf, en stak frame har en reference til et objekt på heapen osv. osv.

Prototypen er selvfølgelig filsystemer, men er det virkelig det eneste system vi har til hirarkiske data?

Igen, jeg mener det er et problem at vi begrænser os til hierakier, for de tvinger os ud i et abstraktionsniveau hvor vi skal definere en rod og undgå cykluser. Selv om vi skriver 2011, gemmer vi stadig filer i et gammeldags naivt hieraki (B+ træ). Dette på trods af at når jeg gemmer en fil, tvinges jeg til at vælge én specifik placering, selv om jeg i princippet har brug for mere end én vej til den (krydsindeksere). Bevares, vi prøver at løse problemet med smarte indekseringsmekanismer og søgninger, men dén løsning skalerer bare ikke.

Så jeg vil påstå du kigger den forkerte vej. Vejen frem er ikke at reducere verden til hierakier sådan som vi har gjort de sidste 50 år, men istedet at finde på måder at arbejde naturligt med grafer. Måske vil hypermediesystemer vise vejen, men fri mig for hierakier tak!

  • 2
  • 3
Martin Bøgelund

Et hieraki er jo blot et subset af en graf der er nemmere at arbejde med (repræsentere, travasere, serialisere mv.). Jeg vil påstå at vi udviklere oftest arbejder med et hieraki, men at vi i virkeligheden har med en graf at gøre nedenunder.

Hierarkier er træstrukturer, og træer er en speciel gruppe/klasse/delmængde af grafer. Så ja, hierakier er træer, og træer er grafer. Det er ikke noget du behøver påstå - sådan er det.

Så jeg vil påstå du kigger den forkerte vej. Vejen frem er ikke at reducere verden til hierakier sådan som vi har gjort de sidste 50 år, men istedet at finde på måder at arbejde naturligt med grafer. Måske vil hypermediesystemer vise vejen, men fri mig for hierakier tak!

Personligt arbejder jeg ikke med hierarkier fordi jeg synes det er mere fantastisk end alt andet. Jeg gør det fordi mine kunder tænker i hierarkiske strukturer.

Hierarkier/træer er så simpel, og stadig så teoretisk stærk en struktur, at megen modellering af virkeligheden via hierarkier, er så god og dækkende en abstraktion, at det ikke er formålstjenligt at begrænse abstraktionen, med øget kompleksitet og deraf følgende mindre gennemskuelighed.

Den dag mine kunder kommer og siger at de ser deres produktportefølje som en 7-listefarvelig, orienteret multigraf, skal jeg gerne støbe en datamodel der understøtter det - men lige nu ville det være overkill.

Kan du nævne et konkret eksempel på et praktisk problemdomæne, der bør løses med mere generelle grafer, fremfor hierarkier/træer?

  • 1
  • 0
Carsten Sonne

Jeg vil nu give Casper ret. Ikke alle koncepter beskrives (modeleres) tættest på virkeligheden i træer. Typisk vil større data- og domænemodeller da nærmere kunne betragtes som en graf, med en eller flere cykliske referencer.

Klassifikationshierarkier er bedst egnet til at beskrive elementer af samme type/orden, hvor dybten i træet udtrykker større granulitet. Mod roden udtrykkes mere generelle karakteristika. Et godt eksempel er livets træ:
http://en.wikipedia.org/wiki/Biological_classification

Træet med elementer af forskellig natur vil oftest ikke have en entydig struktur, men derimod kunne opbygges ud fra forskelle perspektiver uden dermed at miste forbindelsen til det træet udtrykker. I de tilfælde bliver træet blot en bestemt projektion på sammenhængen mellem nogle koncepter. Det udtrykker mere konceptuelle kategoriseringer end egentlig hierarkisk klassifikation:
http://en.wikipedia.org/wiki/Categorization

  • 1
  • 0
Jacob Christian Munch-Andersen

Bevares, vi prøver at løse problemet med smarte indekseringsmekanismer og søgninger, men dén løsning skalerer bare ikke.

Det er sådan ca. sådan enhver SQL database virker, en super kompliceret optimerende kompiler som har det utaknemmelige job at få programstumper som i deres naive implementering ville performe absurd ringe til at køre hurtigere.

Så jeg vil påstå du kigger den forkerte vej. Vejen frem er ikke at reducere verden til hierakier sådan som vi har gjort de sidste 50 år, men istedet at finde på måder at arbejde naturligt med grafer. Måske vil hypermediesystemer vise vejen, men fri mig for hierakier tak!

Det naturlige er den computer som koden skal køre på. En træstruktur er let at implementere og giver rigtig god performance hvis den bruges rigtigt. Hvis det ikke er naturligt nok for dig kan du få et stykke fladt memory.

  • 0
  • 0
Nikolaj Brinch Jørgensen

Et hierarki er en graf uden cykler. Det giver fordele implementeringsmæssigt at vide noget om begrænsningerne, for det giver forudsætninger for at lave implementationer der er hurtigere, end skulle man tage det fulde graf perspektiv med.
Det giver ikke en fordel IMO, at anskue alle strukturer som grafer.

Desuden er det da fint at påstå at SQL/RDBMS strukturer er grafer, det holder bare ikke, når man skal benytte dette som sådan, da queries enten bliver sløve, eller ikke-atomiske.

Anyway! Bottom-line er at det efter min mening giver rigtig god mening at benytte sig af den data-struktur specialisering som simplest muligt løser problemet - det vil være forkert at benytte fulde graf implementering til simple arrays osv.

  • 0
  • 0
Casper Bang

Hierakier er træstrukturer, og træer er en speciel gruppe/klasse/delmængde af grafer. Så ja, hierakier er træer, og træer er grafer. Det er ikke noget du behøver påstå - sådan er det.


Jeg kan ikke se jeg påstår noget forkert, eller hvad du forsøger at korregere. Gider du uddybe hvad du mener? Ja et træ er en graf, men en graf er ikke nødvendigvis et træ!

Kan du nævne et konkret eksempel på et praktisk problemdomæne, der bør løses med mere generelle grafer, fremfor hierarkier/træer?


Altså en ganske alm. relationel database udtrykker en graf, det samme gør et mindmap, samt en indbakke med labels (GMail), og en wiki, for ikke at glemme serialisering af dine Java/C# klasser - der er masser at eksempler.

  • 0
  • 1
Casper Bang

Det er sådan ca. sådan enhver SQL database virker, en super kompliceret optimerende kompiler som har det utaknemmelige job at få programstumper som i deres naive implementering ville performe absurd ringe til at køre hurtigere.


Det er nu er rimelig godt forstået emne, SQL er ikke engang turing komplet så alt optimizeren skal gøre er at reducere i ét enkelt udtryk efter klassiske compiler strategier og sammenholde diverse kandidaters omkostninger med databasens fysiske opbygning (indeks, antal af rækker). Men pointen er dog en hel anden og har intet med relationelle databaser at gøre, det var noget du bragte på banen.

Hvis du har 1.000.000 filer på din harddisk, du ved der er en fil der hedder noget med "dinner", en billedfil fra 2008 taget på en ferie til Paris med din nye Canon D600. Hjælper nogen af disse infomationer dig til at finde filen hurtigt? Nej! Det foregår ved at travasere et B+ træ slavisk og kan tage flere timer.

  • 0
  • 0
Martin Bøgelund

Jeg vil nu give Casper ret. Ikke alle koncepter beskrives (modeleres) tættest på virkeligheden i træer. Typisk vil større data- og domænemodeller da nærmere kunne betragtes som en graf, med en eller flere cykliske referencer.

Trafiksystemer, kloaknetværk, familie- og vennerelationer, logistiske netværk etc. er naturligvis generelle grafer, som ikke bør modelleres som træer, enig.

Men produkthierarkier, områdehierarkier, kundehierarkier etc. betragtes bedst som sådan, altså som træer. Du ønsker feks. ikke at fakturere din kunde to gange, fordi han bor i Syrien, som betjenes af dit salgskontor i Tyrkiet, og du derfor har ham både i din Middle East og din Europe regioner.

Så igen: Hvis dit domæne har generel graf-struktur, skal du selvfølgelig ikke smide hierarkier/træer efter det.

Men især indenfor Business Intelligence og simpel salgsrapportering, ønsker du at rapportere på højeste niveau for at få et overblik over "hele butikken", og beslutningstagerne kan så bruge drilldown til at kigge på produkt- og kunde-segmenter, for til sidst at kunne gå i dybden med kunder eller produkter du mister penge på, bare som eksempel. Her har du meget lidt lyst til at en kreds i en generel graf gør sig gældende - her ønsker du et træ.

Så helt at afsværge hierarkier/træer er en unaturlig begrænsning at pålægge sig selv i sin datamodellering. Jeg forstår simpelhen ikke Caspers "Fri mig for hierarkier", samtidig med hans lovprisning af grafer. Træer er grafer, bare med en speciel struktur, hvor man kan høste diverse fordele fra grafteorien ud fra den viden, at det er et træ man har med at gøre. Fraværet af kredse er en stærk fordel at have i mange samme sammenhænge.

  • 1
  • 0
Martin Bøgelund

Altså en ganske alm. relationel database udtrykker en graf, det samme gør et mindmap, samt en indbakke med labels (GMail), og en wiki, for ikke at glemme serialisering af dine Java/C# klasser - der er masser at eksempler.

Når problemdomænet har en generel grafstruktur, skal du modellere generelle grafer, og ikke begrænse dig til hierarkier. Det siger sig selv.

Din overskrift "Fri mig for hierakier tak" lægger dog op til at nærmest alt hvad der i dag er implementeret vha hierarkier, også bør transformeres til generelle grafer.

Så det er sådanne eksempler du må komme med - noget man idag almindeligvis implementerer som hierarkier, og som du mener bør impelenteres som mere generelle grafstrukturer.

  • 0
  • 0
Casper Bang

Kan du ikke lige uddybe hvad du mener her? Det er en meget generel påstand.

De relationelle databaser bygger på set-teori (hvis du glemmer en join får du det kartesiske produkt) så derfor er det mere korrekt at sige at et RDBMS kan udtrykkes som en graf end at det kan udtrykkes som et træ. Et træ er en graf, men ikke omvendt! Vi laver ofte vores projektioner ovenover som et træ, men det ændrer ikke ved den underliggende sandhed.

  • 2
  • 1
Casper Bang

Når problemdomænet har en generel grafstruktur, skal du modellere generelle grafer, og ikke begrænse dig til hierarkier. Det siger sig selv.

OP'en Peter Makholm skriver nærmest nostalgisk om hierakier/træer. Jeg pointerer hvorfor jeg synes det er en gammeldags og problematisk tankegang, når stort set alt vi har med at gøre i virkeligheden havde langt bedre af at blive modelleret anderledes.

Hvorfor er det f.eks. at vi i en "Gem som..." dialog skal vælge ét sted på en disk? Det er gammel vane. Jeg vil vove den påstand, at i fremtidens filsystemer mounter vi blot buckets ind, og bruger labels og metadata på filerne. Det er en langt mere virkelighedstro repræsentation af verden.

  • 0
  • 1
Martin Bøgelund

De relationelle databaser bygger på set-teori (hvis du glemmer en join får du det kartesiske produkt) så derfor er det mere korrekt at sige at et RDBMS kan udtrykkes som en graf end at det kan udtrykkes som et træ.

Siger du at RDBMS'er er implementeret som træer? Eller at der er nogen der mener at alle relationer udtrykkes bedst som et træ? Kan du poste et link?

Jeg kan faktisk ikke forestille mig at RDBMS'er er implementeret under et skarpt træ-paradigme.

Alle de databasesystemer jeg har mødt, indeholder muligheden for at modellere "Flemming kender Grethe. Grethe kender Ib. Ib kender Flemming." Og så har du en kreds, og dit RDBMS kan således ikke have krævet en stringent træstruktur.

Derfor, igen: Kan du ikke komme med et eksempel på noget, som i dag er modelleret som træer/hierarkier, men som bedre kunne modelleres med generelle grafer?

  • 0
  • 0
Casper Bang

Siger du at RDBMS'er er implementeret som træer?

Nej! Jeg siger jo netop at RDBMS'er ikke er træer, på trods af at hver gang vi interagere med den, er det enten på flad form (én tabel's tupler) eller et hieraki (flere tabeller projekteret som tupler).

Derfor, igen: Kan du ikke komme med et eksempel på noget, som i dag er modelleret som træer/hierarkier, men som bedre kunne modelleres med generelle grafer?

Hver gang du spørger en RDBMS om data, er det som træ/hieraki du evt. sætter en ORM til at mappe til objekter. Hvis du har prøvet at arbejde med databaser der har mange mio. rækker, kæmpet med ineffektiv TopLink/Hibernate, prøvet alternativer (DB4O), vil du forstå hvad jeg mener.

  • 1
  • 0
Peter Makholm Blogger

Et hieraki er jo blot et subset af en graf der er nemmere at arbejde med (repræsentere, travasere, serialisere mv.).

Nej, hierarkier er en nyttig delmængde af graf-begrebet, som det giver god mening at behandle selvstændigt (muligvis er det mere interessant at anskue hierarkier som et specialtilfælde af DAG'er, men lad nu det ligge).

Jeg vil også godt uddybe at jeg ikke starter med at overveje hvordan jeg presser en hierarkisk tankegang ned over et problem, men om hvorvidt det er et hierarki. Hvis det er et hierarki få jeg to ting forærende: Jeg har en unik rod-knude og jeg slipper for en del bogholderi ved generelle gennemløb af min datastruktur.

Så er det selvfølgelig relevant at lave en afvejning og hvor meget man ønsker at presse sit problem ind i en kasse for at opnår disse to fordele. Men at gå derfra og så altid ignorere nytte egenskaber bare fordi man har en mere generel type strukturer er direkte dumt.

Jo, der er en lang række problemer hvor hierarkier er utilstrækkelige. Men det betyder ikke at vi ikke skal gøre nytte af de gode egenskaber der er netop ved at begrænse os til orienterede acykliske grafer når det giver mening!

Fri mig for unødige generaliseringer! KISS, tak!

  • 2
  • 1
Martin Bøgelund

Hvorfor er det f.eks. at vi i en "Gem som..." dialog skal vælge ét sted på en disk? Det er gammel vane. Jeg vil vove den påstand, at i fremtidens filsystemer mounter vi blot buckets ind, og bruger labels og metadata på filerne. Det er en langt mere virkelighedstro repræsentation af verden.

Nu tror jeg jeg begynder at forstå hvor du vil hen.

Når du skriver "virkelighedstro", må du måske bare erkende at det er din vinkel på "virkeligheden" du tager udgangspunkt i - du tænker måske i hardware og mere grundlæggende datastrukturer på OS og applikationsniveau(?)

Så ja, hvis disse elementer udviser en generel grafstruktur, skal det modelleres som generelle grafer, ikke som træer.

Men jeg tror ikke på det er lykkedes nogen at implementere dobbelt-lænkede lister som grafer uden kredse, eksempelvis...

De steder hvor hierarkier/træer er den bedste approksimation eller abstraktion til problemdomænet, skal vi fortsætte med at behandle som træer. En generalisering heraf til det overodnede graf-domæne, vil i slige tilfælde blot øge kompleksiteten uden at øge nytteværdien.

Desuden er træstrukturer så indgroet et fænomen hos brugere. Hvis jeg skal modellere mine kunders data på en måde, så de kan få de rapporter der giver mening for brugerne, så vil jeg blive mødt med et krav om noget træstruktur med mulighed for drill-down.

"Alle år" er roden, "2011" barn heraf, "Juni 2011" barn heraf, osv.

Mine kunder får aldrig nogensinde lyst til at betragte "December 1999" som barn af "4. august 2010". Det vil være fuldstændig overkill at vedligeholde en incidensmatrice eller lignende over en graf for at kunne styre drill-up og -down i det eksempel. Materialized path er tilstrækkeligt og det mest effeiciente ift. den virkelighed jeg skal modellere.

  • 0
  • 0
Casper Bang

Jo, der er en lang række problemer hvor hierarkier er utilstrækkelige. Men det betyder ikke at vi ikke skal gøre nytte af de gode egenskaber der er netop ved at begrænse os til orienterede acykliske grafer når det giver mening!

Fair nok. Det er bare en anden og simplere historie man får, når man læser de oprindelige 15 liniers blog-indlæg! Folk der ikke har haft graf-teori kunne nemt komme til at tro at hierakier/træer er det eneste værktøj. Du ved, "if all you have is a hammer, everything looks like a nail".

  • 2
  • 1
Peter Makholm Blogger

Jeg har for år tilbage set lidt på de såkaldte XML-databaser.

Generelt mener jeg at XML er fantastsik dårligt egnet til 90% af de ting det bliver brugt til (men det er bare Sturgeons lov). For mig virkede det dengang lidt som om XML-databaserne bare hoppede på XML-hypen uden i virkeligheden var brugbare. De use-cases jeg overvejede var i hvert fald lettere at bryde ned til flade relationelle databaser.

Nu når hypen om XML er kølnet noget af (bortset fra folk der skal forsvare at de har låst sig fast til XML) og RDBMS-tilhængernes Jedi-powers ("Dette er ikke en feature du leder efter") er faldet, så kunne det måske være relevant at se den vej igen. Er der nogen der har gode konkrete erfaringer.

  • 1
  • 1
Martin Bøgelund

Hvordan ser create statement ud for den relation? Hvordan laver du Flemming og Grethe atomisk, så de kender hinanden (de skal jo indeholde reference til hinanden)?

Nu har jeg ikke lige Korth & Silberschatz indenfor rækkevidde, men jeg mener de viser netop sådan et eksempel.

Du laver iirc en grundtabel med personer (rækkerne "Flemming" og "Grethe") og en relationstabel over hvem der kender hvem ("Person_A" og "Person_B" som kolonner med IC'er til grundtabellen). Det skulle være til at skrive sin SQL for det setup.

Traversering er afhængigt af hvilket sprog du har adgang til - det vil næppe lykkes dig at gøre det i klassisk SQL.

Og som fuldstændig off-topic, så anvendte jeg "kender"-relationen som en asymmetrisk operator. Jeg "kender" Naser Khader, men han "kender" sikkert ikke mig. Eller på Facebook, hvis jeg siger at jeg kender dig, men du bestemt ikke vil kendes ved mig, og jeg sender friend-invites til en masse personer der afslår, så vil FB-administratorerne måske få lyst til at diskutere begrebet "kender" med mig, udfra en masse rækker i en database, der siger at jeg "kender" hundreder af mennesker, som åbenbart ikke "kender" mig...
Bare sådan for at holde os skarpe på hvilke antagelser vi anvender i design :-)

  • 0
  • 0
Carsten Sonne

Nu når hypen om XML er kølnet noget af (bortset fra folk der skal forsvare at de har låst sig fast til XML) og RDBMS-tilhængernes Jedi-powers ("Dette er ikke en feature du leder efter") er faldet, så kunne det måske være relevant at se den vej igen. Er der nogen der har gode konkrete erfaringer.

Fornemmer jeg en vis bias?

:-)

  • 0
  • 0
Casper Bang

Så helt at afsværge hierarkier/træer er en unaturlig begrænsning at pålægge sig selv i sin datamodellering. Jeg forstår simpelhen ikke Caspers "Fri mig for hierarkier", samtidig med hans lovprisning af grafer. Træer er grafer, bare med en speciel struktur, hvor man kan høste diverse fordele fra grafteorien ud fra den viden, at det er et træ man har med at gøre. Fraværet af kredse er en stærk fordel at have i mange samme sammenhænge.

Prøv at hør her. Blog-indlægget opløfter hierakiske data som optimale i datamodelleringsøjemål. Derefter beskrives hvor svært det er at håndtere disse projektioner/snapshots, og slutter sågar af med en reference til at det bedste vi har er hierakiske filsystemer!!

På dén baggrund er det vel forståligt nok, at jeg pointerer hvorfor hierakier ofte ikke er optimale og at der underliggende findes en mere generel datastruktur (en graf) man kan modellere verden med.

Træer har mange fantastiske egenskaber, men der findes alternativer og nogengange er det fordelagtigt ikke at presse firkanter igennem et rundt hul med magt. Dét er såmænd hele min pointe, ikke at fornægte træer som nogen debattører konstant gradbøjer det til.

  • 1
  • 1
Martin Bøgelund

Blog-indlægget opløfter hierakiske data som optimale i datamodelleringsøjemål.

Peter Makholm må kunne svare på om det var budskabet.

Det jeg tager udgangspunkt i er:

Mange af mine projekter håndterer data der har en eller anden form for hierarkisk struktur.

Så er den for så vidt ikke længere for mig; Jeg forventer Peter har styr nok over sine data til at kunne afgøre om de er hierarkiske eller ej. Og derfor har jeg svært ved at følge dig, når du prøver at overbevise ham (og mig) om at de ikke er hierarkiske alligevel, men derimod bør betragtes som mere generelle grafer.

Hvis du har mere styr over Peters data end han selv har, bliver diskussionen selvsagt en anden end den snak om hierarkier, han lægger op til.

  • 0
  • 0
Casper Bang

Og derfor har jeg svært ved at følge dig, når du prøver at overbevise ham (og mig) om at de ikke er hierarkiske alligevel, men derimod bør betragtes som mere generelle grafer.

Problemet er jo bare at hvis man søger efter træer i en graf, så skal man nok finde dem... mange endda! Jeg kender selvsagt intet til Peters data, men hæfter mig blot ved generaliseringen og genkender de problematikker han jo beskriver.

Han efterlyser desuden en mere "æstetisk" løsning, hvorfor jeg påpeger at måske er problemet at han skal træde et skridt tilbage og tage et andet værktøj i brug end træstrukturen. Hvad er det der er så forfærdeligt ved at jeg gør dette?

  • 0
  • 0
Peter Makholm Blogger

Blog-indlægget opløfter hierakiske data som optimale i datamodelleringsøjemål.

Det er simpelthen en læsning jeg har svært ved at genkende. Jeg skriver netop: "overvejer jeg først og fremmest om jeg har et hierarki eller ikke har et hierarki". Jeg fatter ikke hvordan du får det til at jeg opløfter grafer som et ideal som alle problemer kan passes ind til om og at det er det eneste værktøj i min værktøjskasse.

Problemet er jo bare at hvis man søger efter træer i en graf, så skal man nok finde dem... mange endda!

Morsomt nok er der rigtig mange grafproblemer man løser ved at generere en (eller flere) træstruktur på baggrund af grafen: korteste vej-træer baseret på Dijkstras algoritme for eksempel. Men heldigvis kan man lige dreje problemstillingen en smule så den naturlige erstatning for korteste vej-træer bliver rigtige grafer. Men det har absolut intet med blog-indlæget at gøre...

Og hvorfor egentlig stoppe med grafer. Hvorfor begrænse os til at kanter forbinder to knuder? Hvad er der galt med at generaliserer alting til hypergrafer? Men det har absolut intet med blogindlæget at gøre...

Hvad der derimod kunne være interessant: Hvad mener du jeg vinder ved at generaliserer til grafer? Ud over at når den eneste sturkut jeg har er par af referencer, så er rdbms'er nærmest overkill - hvilket leder mig over i den anden grøft.

  • 1
  • 0
Casper Bang

Jeg fatter ikke hvordan du får det til at jeg opløfter grafer som et ideal som alle problemer kan passes ind til om og at det er det eneste værktøj i min værktøjskasse.

Fordi du springer direkte på hierakier og derefter opremser problemerne du render ind i, et "paradigmeskift" er nødvendigt, det generer dig "æstetisk" osv. Det lyder da lidt som om du leder efter an anden løsning ik?

Hvad mener du jeg vinder ved at generaliserer til grafer?

Tja du vender jo umiddelbart dét, at du kan tillade dig at kigge lidt bredere på persistensløsninger. Når du serialiserer Java/C# er du jo f.eks. ikke begrænset af de samme ting som når du skal gå igennem en ORM, eller gemme i et filsystem. Der findes fine løsninger til dette, f.eks. db4o som jeg har nævnt én gang.

Det er vist sidste gang jeg kommenterer på et lille 15 liniers blogindlæg, risikoen for at misforstå og blive misforstået er for stor. Om du reelt har et problem og ønsker debat omkring det eller ej, er mig lidt af en gåde.

  • 1
  • 2
Log ind eller Opret konto for at kommentere