A Toy SQL Database in JavaScript

The code shown below implements an unfinished, extremely inefficient, buggy, and completely useless SQL database that runs in JavaScript in a web browser. To see it in action, copy the code to an .html file and open that file in a web browser.

I’m really just putting it here as a placeholder for further work. As I say, it doesn’t do too much at present other than running a single, simple, pre-defined query. Of course, even if it worked perfectly and had a million features, it’s doubtful that there’s ever going to be much need for a database that actually runs on the client side in a web browser.

<html>
<body>
<script type='text/javascript'>

// program

function DatabaseTest()
{
	this.main = function()
	{
		var database0 = new Database
		(
			"Database0",
			new Array
			(
				new Table
				(
					new TableDefn
					(
						"TableParent", 
						new Array
						(
							new ColumnDefn("ID", Datatype.Instances.Int, -1, true),
							new ColumnDefn("Name", Datatype.Instances.Varchar, 50, false)
						)
					),

					new Array
					(
						new Row(new Array(1, "One")),
						new Row(new Array(2, "Two")),
						new Row(new Array(3, "Three"))
					)
				),

				new Table
				(
					new TableDefn
					(
						"TableChild", 
						new Array
						(
							new ColumnDefn("ID", Datatype.Instances.Int, -1, true),
							new ColumnDefn("ParentID", Datatype.Instances.Int, -1, true),
							new ColumnDefn("Name", Datatype.Instances.Varchar, 50, false)
						)
					),

					new Array
					(
						new Row(new Array(1, 1, "One.One")),
						new Row(new Array(2, 1, "One.Two")),
						new Row(new Array(3, 1, "One.Three")),
						new Row(new Array(4, 2, "Two.One")),
						new Row(new Array(5, 3, "Three.One"))
					)
				)
			)
		);

		var server = new Server
		(
			"Server0",
			new Array
			(
				database0
			)
		);

		var managementInterface = new ManagementInterface();

		Globals.Instance.initialize
		(
			server,
			managementInterface
		);

		/*
		var query = new Query
		(
			database0.name,
			new Array
			(
				new TableReference("TableParent", "t")
			),
			new Array
			(
				new Expression(Operator.Instances.NotEqualTo, new Array("t0.Name", "Two"))
			),
			new Array
			(
				new ColumnReference("t", "Value")
			)
		);

		var tableJoined = query.execute();
		var tableJoinedAsHTMLElement = tableJoined.convertToHTMLElement();
		document.body.appendChild(tableJoinedAsHTMLElement);
		*/

		var managementInterfaceAsHTMLElement = managementInterface.convertToHTMLElement();
		document.body.appendChild(managementInterfaceAsHTMLElement);
	}
}

// classes

function ColumnDefn(name, datatype, dataLength, isPrimaryKey)
{
	this.name = name;
	this.datatype = datatype;
	this.dataLength = dataLength;
	this.isPrimaryKey = isPrimaryKey;

	this.indexWithinTable = -1;
}
{
	ColumnDefn.prototype.clone = function()
	{
		var returnValue = new ColumnDefn
		(
			this.name, this.datatype, this.dataLength, this.isPrimaryKey
		);

		return returnValue;
	}
}

function ColumnReference(tableAlias, columnName)
{
	this.tableAlias = tableAlias;
	this.columnName = columnName;
}

function Database(name, tables)
{
	this.name = name;

	this.tables = new Lookup();

	for (var t = 0; t < tables.length; t++)
	{
		var table = tables[t];
		this.tables.add(table.tableDefn.name, table);
	}
}

function Datatype(name)
{
	this.name = name;
}
{
	Datatype.Instances = new Datatype_Instances();

	function Datatype_Instances()
	{
		this.Bit = new Datatype("bit");
		this.Int = new Datatype("int");
		this.Varchar = new Datatype("varchar");

		this._All = new Array
		(
			this.Bit,
			this.Int,
			this.Varchar
		);
	}
}

function Expression(operator, operands)
{
	this.operator = operator;
	this.operands = operands;	
}
{
	Expression.prototype.evaluate = function()
	{
		return this.operator.evaluateFunction(this.operands);
	}
}

function Globals()
{}
{
	Globals.Instance = new Globals();

	Globals.prototype.initialize = function(server, managementInterface)
	{
		this.server = server;
		this.managementInterface = managementInterface;
	}
}

function Lookup()
{
	this.systemArray = new Array();
	this.systemLookup = new Array();
}
{
	Lookup.prototype.add = function(key, value)
	{
		this.systemArray.push(value);
		this.systemLookup[key] = value;
	}

	Lookup.prototype.addMany = function(itemsToAdd, keyName, valueName)
	{
		for (var i = 0; i < itemsToAdd.length; i++)
		{
			var item = itemsToAdd[i];

			this.add(item[keyName], (valueName == null ? item : item[valueName]));
		}

		return this;
	}

	Lookup.prototype.containsKey = function(key)
	{
		return (this.systemLookup[key] != null);
	}

	Lookup.prototype.getByIndex = function(index)
	{
		return this.systemArray[index];
	}

	Lookup.prototype.getByKey = function(key)
	{
		return this.systemLookup[key];
	}

	Lookup.prototype.length = function()
	{
		return this.systemArray.length;
	}

	Lookup.prototype.removeKey = function(key)
	{
		var value = this.systemLookup[key];
		this.systemArray.splice(this.systemArray.indexOf(value), 1);
		delete this.systemLookup[key];
	}
}

function ManagementInterface()
{
	// test
	var testQueryText = "select t.Name from TableParent t where t.Value != 'Two'";

	this.commandText = testQueryText;
	this.resultTable = null;

	this.htmlElementForCommandText = null;
	this.htmlElementForResults = null;
}
{
	// static methods

	ManagementInterface.ProcessButtonExecuteClick = function(event)
	{		
		var managementInterface = Globals.Instance.managementInterface;

		var resultAsString;

		var query;

		try
		{
			query = Query.parseFromString(managementInterface.commandText);

			try
			{
				var resultTable = query.execute();
				var resultAsString = resultTable.convertToString();

			}
			catch (ex) 
			{
				resultAsString = "An error occurred while executing the query: " + ex;
			}

		}
		catch (ex)
		{
			resultAsString = "An error occurred while parsing the query: " + ex;
		}

		managementInterface.htmlElementForResults.value = resultAsString;		
	}

	ManagementInterface.ProcessInputCommandsChange = function(event)
	{
		var inputCommands = event.target;
		Globals.Instance.managementInterface.commandText = inputCommands.value;
	}

	// instance methods

	ManagementInterface.prototype.convertToHTMLElement = function()
	{
		var returnValue = document.createElement("table");

		var tr = document.createElement("tr");
		var td = document.createElement("td");
		var pTitle = document.createElement("p");
		pTitle.innerHTML = "SQL Management Interface";
		td.appendChild(pTitle);
		tr.appendChild(td);
		returnValue.appendChild(tr);

		tr = document.createElement("tr");
		td = document.createElement("td");
		pTitle = document.createElement("p");
		pTitle.innerHTML = "Commands to Execute:";		
		td.appendChild(pTitle);
		tr.appendChild(td);
		returnValue.appendChild(tr);

		tr = document.createElement("tr");		
		td = document.createElement("td");
		var inputCommands = document.createElement("textarea");
		inputCommands.value = this.commandText;
		inputCommands.cols = 80;
		inputCommands.rows = 10;
		inputCommands.onchange = ManagementInterface.ProcessInputCommandsChange;
		this.htmlElementForCommandText = inputCommands;
		td.appendChild(inputCommands);
		tr.appendChild(td);
		returnValue.appendChild(tr);

		tr = document.createElement("tr");
		td = document.createElement("td");
		var buttonExecute = document.createElement("button");
		buttonExecute.innerHTML = "Execute Command";
		buttonExecute.onclick = ManagementInterface.ProcessButtonExecuteClick;
		td.appendChild(buttonExecute);
		tr.appendChild(td);
		returnValue.appendChild(tr);

		tr = document.createElement("tr");
		td = document.createElement("td");
		pTitle = document.createElement("p");
		pTitle.innerHTML = "Results:";
		td.appendChild(pTitle);
		tr.appendChild(td);
		returnValue.appendChild(tr);

		tr = document.createElement("tr");		
		td = document.createElement("td");
		var inputResults = document.createElement("textarea");
		inputResults.value = "[results]";
		inputResults.cols = 80;
		inputResults.rows = 10;
		this.htmlElementForResults = inputResults;
		td.appendChild(inputResults);
		tr.appendChild(td);
		returnValue.appendChild(tr);

		this.htmlElement = returnValue;

		return returnValue;
	}	
}

function Operator(name, symbol, evaluateFunction)
{
	this.name = name;
	this.symbol = symbol;
	this.evaluateFunction = evaluateFunction;
}
{
	// static methods

	Operator.ParseFromString = function(stringToParse)
	{
		var returnValue = Operator.Instances._SymbolToOperatorLookup.getByKey(stringToParse);

		if (returnValue == null)
		{
			throw ("No operator matching the token " + stringToParse + " could be found.");
		}

		return returnValue;
	}

	// instances

	Operator.Instances = new Operator_Instances();

	function Operator_Instances()
	{
		this.Equals = new Operator("Equals", "=", OperatorEquals);
		this.GreaterThan = new Operator("GreaterThan", "<", OperatorGreaterThan);
		this.GreaterThanOrEqualTo = new Operator("GreaterThanOrEqualTo", "<=", OperatorGreaterThanOrEqualTo);
		this.LessThan = new Operator("LessThan", "<", OperatorLessThan);
		this.LessThanOrEqualTo = new Operator("LessThanOrEqualTo", "<=", OperatorLessThanOrEqualTo);
		this.NotEqualTo = new Operator("NotEqualTo", "!=", OperatorNotEqualTo);

		this._All = new Array
		(
			this.Equals,
			this.GreaterThan,
			this.GreaterThanOrEqualTo,
			this.LessThan,
			this.LessThanOrEqualTo,
			this.NotEqualTo
		);

		this._SymbolToOperatorLookup = new Lookup().addMany(this._All, "symbol", null);
	}	
}

function OperatorEquals(operands)
{
	return (operands[0] == operands[1]);
}

function OperatorGreaterThan(operands)
{
	return (operands[0] > operands[1]);
}

function OperatorGreaterThanOrEqualTo(operands)
{
	return (operands[0] >= operands[1]);
}

function OperatorLessThan(operands)
{
	return (operands[0] < operands[1]);
}

function OperatorLessThanOrEqualTo(operands)
{
	return (operands[0] <= operands[1]);
}

function OperatorNotEqualTo(operands)
{
	return (operands[0] != operands[1]);
}

function Query(databaseName, tableReferences, conditionExpressions, columnReferences)
{
	this.databaseName = databaseName;
	this.tableReferences = tableReferences;
	this.conditionExpressions = conditionExpressions;
	this.columnReferences = columnReferences;
}
{
	Query.parseFromString = function(stringToParse)
	{
		var charsToReplaceWithSpaces = ",\r\n\t";

		for (var i = 0; i < charsToReplaceWithSpaces.length; i++)
		{
			var charToReplace = "" + charsToReplaceWithSpaces.charAt(i);

			stringToParse = stringToParse.split(charToReplace).join(" ");
		}

		var tokens = stringToParse.split(" ");

		var inSelectClause = false;
		var inFromClause = false;
		var inWhereClause = false;

		var columnReferences = new Array();
		var tableReferences = new Array();
		var conditionExpressions = new Array();

		var database = Globals.Instance.server.databaseCurrent;

		for (var t = 0; t < tokens.length; t++)
		{
			var token = tokens[t];

			if (token == "")
			{
				// do nothing
			}			
			else if (inSelectClause == true)
			{
				if (token == "from")
				{
					inSelectClause = false;
					inFromClause = true;
				}
				else if (token.indexOf(".") >= 0)
				{
					var tableAliasAndColumnName = token.split(".");
					var columnReference = new ColumnReference
					(
						tableAliasAndColumnName[0],
						tableAliasAndColumnName[1]
					);

					columnReferences.push(columnReference);
				}
				else
				{
					throw ("Could not parse token in select clause: " + token + ".");
				}
			}
			else if (inFromClause == true)
			{
				if (token == "where")
				{
					inFromClause = false;
					inWhereClause = true;
				}
				else
				{
					var tableName = token;
					if (database.tables.getByKey(tableName) == null)
					{
						throw ("No table named '" + tableName + "' was found in the database '" + database.name + "'.");
					}

					t++;
					var tableAlias = tokens[t];

					var tableReference = new TableReference
					(
						tableName,
						tableAlias
					);

					tableReferences.push(tableReference);
				}	
			}
			else if (inWhereClause == true)
			{
				if (token == "and" || token == "or")
				{
					// hack - ignore
				}
				else
				{
					var tokenForOperand0 = token;
					t++;
					var tokenForOperator = tokens[t];
					t++;
					var tokenForOperand1 = tokens[t];

					var operator = Operator.ParseFromString(tokenForOperator);

					var conditionExpression = new Expression
					(			
						new Array
						(
							tokenForOperand0,
							tokenForOperand1
						)
					);

					conditionExpressions.push(conditionExpression);
				}
			}
			else if (token == "select")
			{
				inSelectClause = true;
			}
			else
			{
				throw ("Could not parse token: " + token + ".");
			}
		}

		var returnValue = new Query
		(
			Globals.Instance.server.databaseCurrent.name,
			tableReferences,
			conditionExpressions,
			columnReferences
		);

		return returnValue;
	}

	// instance methods

	Query.prototype.execute = function()
	{
		var database = Globals.Instance.server.databases.getByKey(this.databaseName);

		var columnDefnsForTableJoined = new Array();

		var tableAliasToNameLookup = new Lookup().addMany(this.tableReferences, "tableAlias", "tableName");

		var tablesInJoin = new Array();
		var tablesInJoinNameToIndexLookup = new Array();
		for (var t = 0; t < this.tableReferences.length; t++)
		{
			var tableName = this.tableReferences[t].tableName;
			var table = database.tables.getByKey(tableName);
			tablesInJoin.push(table);
			tablesInJoinNameToIndexLookup[table.tableDefn.name] = t;
		}

		for (var c = 0; c < this.columnReferences.length; c++)
		{
			var columnReference = this.columnReferences[c];
			var tableName = tableAliasToNameLookup.getByKey(columnReference.tableAlias);
			var table = database.tables.getByKey(tableName);
			var tableDefn = table.tableDefn;
			var columnDefn = tableDefn.columnDefns.getByKey(columnReference.columnName);

			columnDefnsForTableJoined.push(columnDefn.clone());
		}

		var tableJoinedDefn = new TableDefn
		(
			"[joined table]",
			columnDefnsForTableJoined
		);

		var rowIndicesForTablesInJoin = new Array();
		for (var t = 0; t < tablesInJoin.length; t++)
		{			
			rowIndicesForTablesInJoin.push(0);			
		}

		var haveAllRowMatchingsBeenConsidered = false;

		var rowsForTableJoined = new Array();

		while (haveAllRowMatchingsBeenConsidered == false)
		{
			var haveAllConditionsBeenMetSoFar = true;
			for (var c = 0; c < this.conditionExpressions.length; c++)
			{
				// hack - Not sure how to implement expressions.

				var conditionExpression = this.conditionExpressions[c];			
				var operands = conditionExpression.operands;
				var operandsEvaluated = new Array();

				for (var o = 0; o < operands.length; o++)
				{
					var operand = operands[o];
					var operandEvaluated;

					if (operand.indexOf(".", 0) >= 0)
					{
						var tableAliasAndColumnName = operand.split(".");

						// fix - duplicated code?
						var tableName = tableAliasToNameLookup.getByKey(tableAliasAndColumnName[0]);
						var table = tablesInJoin[tablesInJoinNameToIndexLookup[tableName]];
						var tableIndex = tablesInJoinNameToIndexLookup[tableName];
						var rowIndex = rowIndicesForTablesInJoin[tableIndex];
						var rowToJoin = table.rows[rowIndex];					
						var columnDefn = table.tableDefn.columnDefns.getByKey(columnReference.columnName);
						var rowColumnValueIndex = columnDefn.indexWithinTable;
						var columnValueFromRow = rowToJoin.columnValues[rowColumnValueIndex];

						operandEvaluated = columnValueFromRow;
					}
					else
					{
						operandEvaluated = operand.split("'").join("");
					}

					operandsEvaluated[o] = operandEvaluated;
				}

				var result = new Expression(conditionExpression.operator, operandsEvaluated).evaluate();
				if (result != true)
				{
					haveAllConditionsBeenMetSoFar = false;
					break;
				}
			}			

			if (haveAllConditionsBeenMetSoFar == true)
			{
				var rowJoinedValues = new Array();

				for (var c = 0; c < this.columnReferences.length; c++)
				{
					var columnReference = this.columnReferences[c];
					var tableName = tableAliasToNameLookup.getByKey(columnReference.tableAlias);					
					var tableIndex = tablesInJoinNameToIndexLookup[tableName];
					var table = tablesInJoin[tableIndex];
					var rowIndex = rowIndicesForTablesInJoin[tableIndex];
					var rowToJoin = table.rows[rowIndex];					
					var columnDefn = table.tableDefn.columnDefns.getByKey(columnReference.columnName);
					var rowColumnValueIndex = columnDefn.indexWithinTable;
					var columnValueFromRow = rowToJoin.columnValues[rowColumnValueIndex]; 

					rowJoinedValues.push(columnValueFromRow);				
				}

				rowsForTableJoined.push(new Row(rowJoinedValues));
			}			

			// advance to next set of rows to be joined
			var t = 0;
			while (true)
			{
				var table = tablesInJoin[t];

				rowIndicesForTablesInJoin[t] += 1;
				if (rowIndicesForTablesInJoin[t] < table.rows.length) 
				{
					break;
				}
				else
				{
					rowIndicesForTablesInJoin[t] = 0;
					t++;
					if (t >= rowIndicesForTablesInJoin.length)
					{
						haveAllRowMatchingsBeenConsidered = true;
						break;
					}
				}
			}
		}

		var tableJoined = new Table
		(
			tableJoinedDefn,
			rowsForTableJoined
		);

		return tableJoined;
	}	
}

function Row(columnValues)
{
	this.columnValues = columnValues;
}

function Server(name, databases)
{
	this.name = name;
	this.databases = new Lookup().addMany(databases, "name", null);
	this.databaseCurrent = databases[0];
}

function Table(tableDefn, rows)
{
	this.tableDefn = tableDefn;
	this.rows = rows;
}
{
	Table.prototype.convertToHTMLElement = function()
	{
		var returnValue = document.createElement("table");

		var trForHeader = document.createElement("tr");

		for (var c = 0; c < this.tableDefn.columnDefns.length(); c++)
		{
			var columnDefn = this.tableDefn.columnDefns.getByIndex(c);

			var thForColumn = document.createElement("th");
			thForColumn.innerHTML = columnDefn.name;
			trForHeader.appendChild(thForColumn);
		}

		returnValue.appendChild(trForHeader);

		for (var r = 0; r < this.rows.length; r++)
		{
			var row = this.rows[r];

			var trForRow = document.createElement("tr");

			for (var c = 0; c < row.columnValues.length; c++)
			{
				var columnValue = row.columnValues[c];

				tdForColumnValue = document.createElement("td");
				tdForColumnValue.innerHTML = columnValue;
				trForRow.appendChild(tdForColumnValue);
			}

			returnValue.appendChild(trForRow);
		}

		return returnValue;
	}

	Table.prototype.convertToString = function()
	{
		var newline = "\r\n";

		var returnValue = this.tableDefn.name + newline;

		for (var c = 0; c < this.tableDefn.columnDefns.length(); c++)
		{
			var columnDefn = this.tableDefn.columnDefns.getByIndex(c);

			returnValue += columnDefn.name + " ";
		}

		returnValue += newline;

		for (var r = 0; r < this.rows.length; r++)
		{
			var row = this.rows[r];

			for (var c = 0; c < row.columnValues.length; c++)
			{
				var columnValue = row.columnValues[c];
				returnValue += columnValue + " ";
			}

			returnValue += newline;
		}

		returnValue += newline;

		returnValue += "Rows: " + this.rows.length;

		returnValue += newline;

		return returnValue;		
	}
}

function TableDefn(name, columnDefns)
{
	this.name = name;

	for (var c = 0; c < columnDefns.length; c++)
	{
		var columnDefn = columnDefns[c];
		columnDefn.indexWithinTable = c;
	}

	this.columnDefns = new Lookup().addMany(columnDefns, "name", null);
}

function TableReference(tableName, tableAlias)
{
	this.tableName = tableName;
	this.tableAlias = tableAlias;
}

// run

new DatabaseTest().main();

</script>
</body>
</html>
This entry was posted in Uncategorized and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s