DBMS in C

Professionelle Datenbanksysteme sind sehr komplex, damit sie wirklich performant sind. Da steckt auch sehr viel Mathematik und viel Erfahrung dahinter. Das ist also alles andere als trivial.

An deiner Stelle würde ich es einfach "irgendwie" programmieren, so das es funktioniert. Wirklich gute Performance wirst du vermutlich ohnehin nicht erreichen können.

Das ist mir und auch dem Aufgabensteller durchaus bewusst, daher soll ja auch nur ein einfaches, kleines DBMS geschrieben werden, welches mit einer einfachen Anfragesprache arbeitet.

Wir sollen uns halt im Vorfeld Gedanken machen, welche Struktur für unsere Verhältnisse besser geeignet ist. Daher muss ich mir überlegen, welche dynamische Datenstruktur für welchen Teil des Programms aufgrund der jeweiligen Laufzeitkomplexität besser geeignet ist.

Da wir ja mind. eine Liste und ein dyn. Array nutzen sollen, habe ich mir überlegt, ich mach eine verkettete Liste, in der ich in jedem Node ein dynamisches Array speichere und dann auf das nächste verweise...

Wutz

Es ist äußerst unpraktikabel, sich vorab schon auf konkrete Maßnahmen zur Implementierung festzulegen (LList,...) bevor überhaupt klar ist, welches die fachlichen Anforderungen sind. Optimierung auf fachlicher Ebene schlägt in jedem Fall solche auf technischer.

Okay...
Ich überlege gerade, wie ich am effektivsten das Parsen bzw. Interpretieren der Anfragesprache umsetze...

Die Anfragesprache befindet sich ja in einer Script-Datei im folgenden Format:

SELECT FROM tabelle1 WHERE spalte1 EQUAL 100 AS neuetabelle
APPEND TO tabelle1 100,200,300,400

Jetzt muss ich dieses file ja zeilenweise durchgehen, aber da jeder Befehl unterschiedlich aufgebaut ist, gibt es ja kein direktes Muster, nach dem man interpretieren kann. Ok, jedes Wort am Anfang einer Zeile ist ein Schlüsselwort (sowas wie SELECT, APPEND, REMOVE, etc.), aber dann müsste man ja für jeden Befehl eine individuelle Abfrage implementieren...Praktisch wenn ich schaue, ob es ein SELECT ist, dann muss ein FROM folgen, dann ein BEZEICHNER für die Tabelle usw. Aber das würde doch den Rahmen sprengen, wenn ich für jeden Befehl ein individuelles sscanf bzw fscanf bastel?

Was für Möglichkeiten gäbe es da noch?

Wutz

Wenn du SQL nachbauen willst, halte ich dies für ein kleines Projekt für nicht machbar. Außerdem gibt es schon freie Implementierungen von SQL-Interpretern, die Einarbeit ist aber aufwändig und die Schnittstellen kompliziert.
Passe die Syntax deiner Abfragesprache deinen Anforderungen an, d.h. was du brauchst ist zunächst mal (ohne DDL) select,insert,update,delete. Dabei kannst du z.B. zum erleichterten Parsen immer feste Positionen für die einzelnen Parameter festlegen, auch solltest du zunächst mal nur einfache Datentypen und Operatoren darauf zulassen (nur String/Integer).
Für select musst du dir prinzipielle Gedanken für das Datenstreaming/Persistenz machen.
...

Das direkte Nachbauen von SQL ist nicht Sinn und Zweck der Aufgabe. Die Aufgabenstellung verlangt halt, einige grundlegende Abfragen zu implementieren.

Dabei kannst du z.B. zum erleichterten Parsen immer feste Positionen für die einzelnen Parameter festlegen

Also verstehe ich das richtig, dass ich für jeden Fall (zB Select,Insert,usw.) eine feste Vorgabe/maske zum Parsen benötige? Sprich ich hab 5 verschiedene Abfragen (select, insert, remove, update und print) und somit 5 verschiedene Abfragen, ob es der Syntax entspricht? Anders kann ich mir das momentan irgendwie nicht vorstellen...

(Vom Datentyp her sollen es wirklich nur Strings/Interger sein, die Persistenz wäre nach dem Parsen der nächste Schritt, mir geht es halt erstmal um das richtige parsen/interpretieren)

Wutz

Mit festen Positionen war gemeint, dass für jede Aktion die Parameterliste konstant vorgegeben ist, d.h. der Parser sich mal schon darum nicht kümmern muss.
Schlüsselwörter wie from/where könnten somit entfallen.
Bei einen Trennzeichen '\t' (damit ' ' in Strings verwendet werden kann) und ',' als Aufzählungskennzeichen wäre also z.B. denkbar:

insert into tabelle (name,vorname,beide) values('tiger','scott','scott tiger');

i\ttabelle\tname,vorname,beide\ttiger,scott,scott tiger

Nochmal zurück zur Datenstruktur:

Folgendes ist ja zu Speichern:
1. Tabellenbezeichner
2. Spaltenbezeichner
3. Datensaetze

Ich habe mir überlegt, Punkt 1 und 2 jeweils in eine Liste zu speichern, Punkt 3 in einem dynamischen Array. Würde das Sinn machen? Eine erste Überlegung war, die Datensaetze evtl. in eine Liste zu speichern...

Ich habe mal versucht, meine Gedanken umzusetzen, doch habe ich irgendwo einen Denkfehler. Hier mal meine Struktur, funzt das so?

Meine Listenstruktur:

typedef struct Node * List;

struct Node
{
	List next;
	/** Nutzlast */
	Element elem;
};

Element ist deklariert als:

typedef Table Element;

Und dann habe ich eine Tabellenstruktur:

struct s_Table 
{
	String identifier;
	Column * cols; /* Spaltenbezeichner als dyn. Array, Column ist noch als struct definiert */

};

typedef struct s_Table Table;

Ich will die Tabellenbezeichner in eine Liste speichern, die Spaltenbezeichner in ein Array. Ich muss ja von die Tabellenbezeichner mit den zugehörigen Spalten verknüpfen, um darauf zugreifen zu können. Irgendwie habe ich das Gefühl, das meine Struktur irgendwie nicht hinhaut...

Zunächst würde ich jede Tabelle als eigenständige Datei speichern lassen. Damit sparst du dir schon einiges an Arbeit.

Den Aufbau der Datei könntest du dann so anlegen:

Spalte1|Spalte2|Spalte3|Spalte4
Datensatz1_1|Datensatz1_2|Datensatz1_3|Datensatz1_4
...

Du könntest auch die Feldgrößen mit angeben. Dann brauchst du keine Trennzeichen mehr.

Das Einlesen sollte kein Problem sein. Entweder an den Trennzeichen trennen oder die angegebene Länge einlesen.

Als Datenstruktur kannst du zwei verkettete Listen nehmen. Eine für die Spalte und eine für die Datensätze:

struct Data
{
 Col *col;
 Data *next;
 // ...
};

Die Tabelle weiß dann nur ihren Namen und kennt die Datensätze (inklusive Spaltenbezeichnung als ersten Datensatz):

struct Table
{
 char *name;
 Data *data;
};

Sollte funktionieren. Ob das sinnvoll ist, ist die andere Frage. Aber man sollte ja erst mal einen Prototypen fertigstellen.

Okay, das werd ich mir mal durch den Kopf gehen lassen.

Die Tabellen liegen schon als eigenständige Dateien (CSV-Format) vor, die deinen Aufbau etwa entsprechen.

Wie läuft das denn mit 2 verketteten Listen? Du hast ja gepostet:

struct Data
{
 Col *col;
 Data *next;
 // ...
};

Das ist ja für die Datensätze, kommt dann für die Spalten dann nochmal nen Struct oder kommt das mit da rein? Diese Vernüpfung macht mit Sorgen...

Col ist auch eine verkettete Liste:

struct Col
{
 char *value;
 Col *next; 
 //...
};

Was spricht gegen diese Verknüpfung?

Somit hätte ich dann kein dynamisches Array mehr in meiner Struktur,
benötige aber mindestens eins, da Vorgabe. Daher müsste wohl oder übel die Datensätze oder Spalten in ein solches speichern.

Dann speicherst du einfach die Spalteninhalte in einem dynamischen Array. Da du am besten eh nur char * dort speicherst, kannst du ruhig größere Blöcke anfordern.

Beginnst also z.B. am Anfang mit der Größe 4 und sollte das nicht genügend sein, so vergrößerst du es mit realloc einfach um das doppelte, usw...

Alles in allem muss man schon etwas Ahnung haben, um das umsetzen zu können. Ich empfinde die Aufgabe aber eh als sehr fraglich.

Schon umgesetzt, Tabellenbezeichner + Spalten werden erfolgreich eingelesen + gepeichert (Spalten nun im Array).

Mit den Datensätzen an sich muss ich jetzt mal schauen, Liste würde sich ja anbieten.

Es ist nicht so, auch wenn es danach klingt, das ich ein blutiger Anfänger bin. Mir fällt es etwas schwer, eine solche Datenstruktur aufzustellen. Steht die Struktur erstmal, bin ich relativ fix in der weiteren Verarbeitung.

Und...danke für deine Hilfe!