(Fr.: structure (arrangement) de données; Du.: Datenaufbau; Eng.: data structure (organisation) of gegevensstructuur, begrip dat wordt aangetroffen bij het ontwerpen van informatiesystemen waarbij gegevens met een computer moeten worden beheerd.
Als in een bedrijf wordt besloten een of meer administraties te automatiseren, moet een aantal activiteiten worden ontwikkeld voor een optimale oplossing. Daarbij wordt begonnen met het bepalen van de informatiebehoefte; vervolgens wordt bepaald welke gegevens beschikbaar moeten zijn voor de gewenste informatie en tenslotte worden de gegevens zodanig gestructureerd, dat in de informatiebehoefte kan worden voorzien. Dit betekent het samenstellen van gegevensverzamelingen, waarbij gelijksoortige gegevens tot dezelfde verzameling behoren. Ook moet de samenhang tussen deze verzamelingen onderling worden aangegeven (constructie van een datastructuur). Bij het inbrengen van de gegevens in de computer moet de logische samenhang behouden blijven. De gegevens worden daartoe vastgelegd op bijv. magneetschijven, waarbij de structuur weerspiegeld wordt in de opslagstructuur. Computerprogramma’s kunnen dan naar behoefte gegevens uit verschillende verzamelingen ‘bij elkaar zoeken’.
Als gegevensverzamelingen en de onderlinge relaties ervan een afspiegeling vormen van de werkelijke relaties tussen die gegevens dan wordt het geheel van de relaties een datastructuur genoemd. Gegevens die ‘bij elkaar behoren’ worden door een gegevensstructuur aan elkaar gerelateerd. Enkele voorbeelden: Een telefoongids vormt een gegevensverzameling waarbij in principe elke naam met adres gerelateerd is aan één telefoonnummer, en omgekeerd (één-op-één-relatie). Een beroepengids vormt een gegevensverzameling waarbij elk beroep gerelateerd kan zijn aan meer dan één persoonsnaam, maar omgekeerd elke persoonsnaam gerelateerd is aan één beroep (één-op-N-relatie). Een trefwoordencatalogus van een bibliotheek vormt een gegevensverzameling waarbij een trefwoord aan meer dan een boek kan zijn toegekend, en omgekeerd (N-op-M-relatie).
Wanneer tussen de elementen van een verzameling uitsluitend één-op- N-relaties bestaan, waarbij voor minstens één van de relaties geldt N > 1, heet zo’n verzameling een boomstructuur; een voorbeeld van een dergelijke structuur is de stamboom waarvan elk element (mens) aan hoogstens één element van hogere orde en aan N elementen van lagere orde kan zijn gerelateerd. Worden uitsluitend relaties aangetroffen met N = 1, dan spreekt men van een sequentiële structuur.
Bij een netwerkstructuur zijn tussen de elementen een of meer N-op-M-relaties aanwezig; een voorbeeld hiervan vormt het spoorwegnet: N spoorlijnen komen samen bij een station (het element) van waaruit M spoorlijnen leiden naar andere stations.
Met betrekking tot gegevensstructuren is een aantal termen gangbaar.
Een entiteit wordt gevormd door gegevens die bij elkaar behoren en een begrip vertegenwoordigen. Veelal zal tussen deze gegevens de één-op-één-relatie worden aangetroffen. Bijv.: elke telefoonabonnee in de telefoongids wordt geïdentificeerd door een aantal bij elkaar behorende gegevens; in dit verband wordt het begrip ‘abonnee’ als entiteit aangeduid. Elke entiteit wordt gekarakteriseerd door een of meer kenmerken (properties), die van de entiteit ‘abonnee’ zijn: persoonsnaam, adres, netnummer en abonneenummer. Als aan elk kenmerk van de entiteit ‘abonnee’ een gegevenswaarde (value) wordt toegekend, wordt het begrip geconcretiseerd en is er sprake van één bepaalde telefoonabonnee; door andere gegevenswaarden wordt een tweede telefoonabonnee bepaald enz. Wanneer op deze wijze bijv. 100 telefoonabonnees worden beschouwd, dan is het aantal verschijningsvormen (occurrences) van de entiteit ‘abonnee’ 100.
Bij het construeren van een datastructuur kan gebruik worden gemaakt van een van C.W. Bachman afkomstige notatievorm. Deze omvat een rechthoek voor de weergave van een entiteit en de naam daarvan. Een relatie tussen twee verschillende entiteiten wordt aangeduid met een pijl. Deze impliceert dat aan elke verschijningsvorm van de entiteit waar de pijl ontspringt (owner type) nul of meer verschijningsvormen gerelateerd kunnen zijn van de entiteit waarnaar de pijl wijst (member type); een dergelijke set is de bouwsteen van elke datastructuur. De naam ervan is identiek aan die welke aan de relatie (pijl) wordt toegekend. Bijv.: de relatie C tussen de entiteiten A en B, waarbij A en B ten opzichte van elkaar verschillende begrippen vertegenwoordigen, vormt de set C die door middel van de afgesproken notatie als volgt kan worden geconstrueerd:
(zie afb. A)
In het volgende voorbeeld worden de telefoonabonnees per land beschouwd. Gegeven zijn de entiteiten ‘land’, ‘netnummer’, ‘woonplaats’, en ‘naam-straat-abonneenummer’, alsmede de relaties ‘netnummers-per-land’, ‘woonplaats-per-netnummer’ en abonnees-per-woonplaats'. Deze gegevens bepalen de volgende structuur:
(zie afb. B)
Een verschijningsvorm van de set ‘woonplaatsen-per-netnummer’ vertegenwoordigt alle woonplaatsen met hetzelfde netnummer binnen een bepaald land. Elke set uit de structuur is als het ware een deelverzameling van alle gegevens die betrekking hebben op alle telefoonabonnees. Ter nadere illustratie dient:
(zie afb. C)
Om een gegevensstructuur met betrekking tot de verschijningsvormen enigszins doorzichtig te maken kan een zgn. ‘occurrenceplaatje’ worden gebruikt. Een vereenvoudigde situatie voor bijv. Nederland wordt in de volgende figuur geïllustreerd. Het netnummer K1 is toegekend aan de woonplaatsen W1 , W2 en W3 die resp. twee, een en twee abonnees hebben. De woonplaats W5 met K2 als netnummer bezit daarentegen geen enkele abonnee. De gebruikte notatiemethode kan als tamelijk gangbaar worden aangemerkt maar niet als standaardmethode.
(zie afb. D)
Uitgaande van de behandelde vorm van notatie kunnen de volgende vier elementaire datastructuren worden onderscheiden.
1. De entiteiten A en B zijn verschillend en worden via de relatie C aan elkaar gerelateerd. Een dergelijke structuur is de afbeelding van bijv. een kast A waarin N boeken B zijn opgeborgen. De één-op-N-relatie komt in onderstaande verschijningsvorm tot uitdrukking:
(zie afb. E)
2. Entiteiten van hetzelfde type zijn aan elkaar gerelateerd door de relatie C. De structuur kan als afbeelding fungeren van een team bestaande uit onderzoekers A tussen wie een rapportering plaatsvindt. Elke onderzoeker rapporteert aan hoogstens één andere onderzoeker maar kan zelf meer dan één rapportering ontvangen. Door het team hiërarchisch (de onderzoekers A3 en A6 rapporteren aan A2 die zelf slechts rapporteert aan A1) op te bouwen kan de één-op-N-relatie in de volgende verschijningsvorm worden voorgesteld:
(zie afb. F)
3. De entiteiten B en T zijn verschillend en worden uitgaande van B aan elkaar gerelateerd door de relatie D en uitgaande van T door de relatie E. Beide relaties gaan via een derde entiteit R, die in de werkelijkheid niet voorkomt, maar een uitdrukkingshulpmiddel vormt. Onderstaande verschijningsvorm heeft betrekking op het toekennen van trefwoorden T aan boeken B. Aan boek B1 worden de trefwoorden T1 en T2 toegekend en aan boek B2 het trefwoord T2. B1 is via R1 en R2 (verschijningsvormen van de hulpentiteit R) aan T1 en T2 gerelateerd; T2 via R2 en R3 aan B1 en B2.
(zie afb. G)
4. Deze N-op-M-relatie tussen entiteiten van hetzelfde type valt uiteen in de één-op-M-relatie D en de één-op- N-relatie E, die beide via de hulpentiteit R lopen. Een voorbeeld van een verzameling die door een dergelijke structuur kan worden vertegenwoordigd, is een verzameling onderdelen S waarbij elk onderdeel weer uit andere onderdelen S kan zijn opgebouwd. Ter illustratie van een en ander wordt verondersteld dat onderdeel S1 uit de onderdelen S2 en S3 bestaat, S2 uit S4 en S3 eveneens uit S4. Dit impliceert dat de onderdelen S2 en S3 aan S1 zijn toegekend en onderdeel S4 aan S2 en S3.
(zie afb. H)
In de verschijningsvorm van deze gegevensstructuur komt vooral de betekenis van de hulpentiteit R tot uitdrukking.
S1 is via R1 en R2 (verschijningsvormen van de hulpentiteit R) aan S2 en S3 gerelateerd. R3 verbindt S2 met S4 en R4 verbindt S3 met S4. De getrokken lijnen beelden de relatie D af en de gestippelde lijnen de relatie E. In het algemeen zal een gegevensstructuur zijn opgebouwd uit combinaties van de elementaire gegevensstructuren, waarvan de volgende figuur een simplistisch voorbeeld is:
(zie afb. I)