SQLxD Part 11 — JOINs – Random IT Utensils

This is the eleventh part of the SQLxD series. For your convenience you can find other parts in the table of contents in Part 1 – XML Transformation

Today we implement various JOIN operators. Let’s start with interfaces:

using QueryLogic.RelationProviding;

namespace QueryLogic.Joins.Abstraction
{
    public interface IJoin : IRelationProvider
    {
        IRelationProvider FirstRelation { get; }
        IRelationProvider SecondRelation { get; }
    }
}

using QueryLogic.RelationProviding;

namespace QueryLogic.Joins.Abstraction

{

public interface IJoin : IRelationProvider

{

IRelationProvider FirstRelation { get; }

IRelationProvider SecondRelation { get; }

}

namespace QueryLogic.Joins.Abstraction
{
    public interface IInnerJoin : IJoin
    {
    }
}

namespace QueryLogic.Joins.Abstraction

{

public interface IInnerJoin : IJoin

{

}

namespace QueryLogic.Joins.Abstraction
{
    public interface IOuterJoin : IJoin
    {
    }
}

namespace QueryLogic.Joins.Abstraction

{

public interface IOuterJoin : IJoin

{

}

Let’s start with the simplest join — CROSS JOIN:

using Model;
using QueryLogic.Joins.Abstraction;
using QueryLogic.RelationProviding;

namespace QueryLogic.Joins.Implementation
{
    public class CrossJoin : IInnerJoin
    {
        public CrossJoin(IRelationProvider firstRelation, IRelationProvider secondRelation)
        {
            FirstRelation = firstRelation;
            SecondRelation = secondRelation;
        }

        public IRelationProvider FirstRelation { get; private set; }
        public IRelationProvider SecondRelation { get; private set; }

        public Relation CreateRelation(Node source)
        {
            var result = new Relation();

            foreach (Row first in FirstRelation.CreateRelation(source).Rows)
            {
                foreach (Row second in SecondRelation.CreateRelation(source).Rows)
                {
                    var newRow = new Row();

                    newRow.AddCells(first.Cells);
                    newRow.AddCells(second.Cells);
                    newRow.AddGuids(first.Guids);
                    newRow.AddGuids(second.Guids);

                    result.AddRow(newRow);
                }
            }

            return result;
        }

        protected bool Equals(CrossJoin other)
        {
            return Equals(FirstRelation, other.FirstRelation) && Equals(SecondRelation, other.SecondRelation);
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj)) return false;
            if (ReferenceEquals(this, obj)) return true;
            if (obj.GetType() != GetType()) return false;
            return Equals((CrossJoin)obj);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                return ((FirstRelation != null ? FirstRelation.GetHashCode() : 0) * 397) ^
                       (SecondRelation != null ? SecondRelation.GetHashCode() : 0);
            }
        }
    }
}

using Model;

using QueryLogic.Joins.Abstraction;

using QueryLogic.RelationProviding;

namespace QueryLogic.Joins.Implementation

{

public class CrossJoin : IInnerJoin

{

public CrossJoin(IRelationProvider firstRelation, IRelationProvider secondRelation)

{

FirstRelation = firstRelation;

SecondRelation = secondRelation;

}

public IRelationProvider FirstRelation { get; private set; }

public IRelationProvider SecondRelation { get; private set; }

public Relation CreateRelation(Node source)

{

var result = new Relation();

foreach (Row first in FirstRelation.CreateRelation(source).Rows)

{

foreach (Row second in SecondRelation.CreateRelation(source).Rows)

{

var newRow = new Row();

newRow.AddCells(first.Cells);

newRow.AddCells(second.Cells);

newRow.AddGuids(first.Guids);

newRow.AddGuids(second.Guids);

result.AddRow(newRow);

}

return result;

}

protected bool Equals(CrossJoin other)

{

return Equals(FirstRelation, other.FirstRelation) && Equals(SecondRelation, other.SecondRelation);

}

public override bool Equals(object obj)

{

if (ReferenceEquals(null, obj)) return false;

if (ReferenceEquals(this, obj)) return true;

if (obj.GetType() != GetType()) return false;

return Equals((CrossJoin)obj);

}

public override int GetHashCode()

{

unchecked

{

return ((FirstRelation != null ? FirstRelation.GetHashCode() : 0) * 397) ^

(SecondRelation != null ? SecondRelation.GetHashCode() : 0);

}

We simply implement nested loop algorithm and add cells from both of the rows.

The INNER JOIN is CROSS JOIN + WHERE:

using Model;
using QueryLogic.Filtering;
using QueryLogic.Joins.Abstraction;
using QueryLogic.Predicates;
using QueryLogic.RelationProviding;

namespace QueryLogic.Joins.Implementation
{
    public class InnerJoin : IInnerJoin
    {
        public InnerJoin(IRelationProvider firstRelation, IRelationProvider secondRelation,
            IPredicate predicate)
        {
            FirstRelation = firstRelation;
            SecondRelation = secondRelation;
            Predicate = predicate;
        }

        public IPredicate Predicate { get; protected set; }

        public IRelationProvider FirstRelation { get; protected set; }
        public IRelationProvider SecondRelation { get; protected set; }

        public virtual Relation CreateRelation(Node source)
        {
            var join = new CrossJoin(FirstRelation, SecondRelation);

            Relation relation = new Where(join, Predicate).CreateRelation(source);

            return relation;
        }

        protected bool Equals(InnerJoin other)
        {
            return Equals(FirstRelation, other.FirstRelation) &&
                   Equals(SecondRelation, other.SecondRelation) && Equals(Predicate, other.Predicate);
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj)) return false;
            if (ReferenceEquals(this, obj)) return true;
            if (obj.GetType() != GetType()) return false;
            return Equals((InnerJoin)obj);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                int hashCode = (FirstRelation != null ? FirstRelation.GetHashCode() : 0);
                hashCode = (hashCode * 397) ^ (SecondRelation != null ? SecondRelation.GetHashCode() : 0);
                hashCode = (hashCode * 397) ^ (Predicate != null ? Predicate.GetHashCode() : 0);
                return hashCode;
            }
        }
    }
}

using Model;

using QueryLogic.Filtering;

using QueryLogic.Joins.Abstraction;

using QueryLogic.Predicates;

using QueryLogic.RelationProviding;

namespace QueryLogic.Joins.Implementation

{

public class InnerJoin : IInnerJoin

{

public InnerJoin(IRelationProvider firstRelation, IRelationProvider secondRelation,

IPredicate predicate)

{

FirstRelation = firstRelation;

SecondRelation = secondRelation;

Predicate = predicate;

}

public IPredicate Predicate { get; protected set; }

public IRelationProvider FirstRelation { get; protected set; }

public IRelationProvider SecondRelation { get; protected set; }

public virtual Relation CreateRelation(Node source)

{

var join = new CrossJoin(FirstRelation, SecondRelation);

Relation relation = new Where(join, Predicate).CreateRelation(source);

return relation;

}

protected bool Equals(InnerJoin other)

{

return Equals(FirstRelation, other.FirstRelation) &&

Equals(SecondRelation, other.SecondRelation) && Equals(Predicate, other.Predicate);

}

public override bool Equals(object obj)

{

if (ReferenceEquals(null, obj)) return false;

if (ReferenceEquals(this, obj)) return true;

if (obj.GetType() != GetType()) return false;

return Equals((InnerJoin)obj);

}

public override int GetHashCode()

{

unchecked

{

int hashCode = (FirstRelation != null ? FirstRelation.GetHashCode() : 0);

hashCode = (hashCode * 397) ^ (SecondRelation != null ? SecondRelation.GetHashCode() : 0);

hashCode = (hashCode * 397) ^ (Predicate != null ? Predicate.GetHashCode() : 0);

return hashCode;

}

And we are good to go. Now outer joins:

using System.Linq;
using Model;
using QueryLogic.Joins.Abstraction;
using QueryLogic.RelationProviding;

namespace QueryLogic.Joins.Implementation
{
    public abstract class OuterJoin : IOuterJoin
    {
        public abstract Relation CreateRelation(Node source);
        public IRelationProvider FirstRelation { get; protected set; }
        public IRelationProvider SecondRelation { get; protected set; }

        protected void AddNonjoinedRows(Relation result, Relation source, Relation target)
        {
            foreach (Row row in source.Rows)
            {
                if (ContainsRowPart(result, row)) continue;
                var newRow = new Row();

                newRow.AddCells(row.Cells);
                newRow.AddCells(target.Columns.Select(c => new Cell(c, null)));

                result.AddRow(newRow);
            }
        }

        private bool ContainsRowPart(Relation relation, Row rowPart)
        {
            return relation.Rows.Any(r => ContainsRowPart(r, rowPart));
        }

        private bool ContainsRowPart(Row source, Row part)
        {
            return part.Cells.All(partCell => source.GetCellValue(partCell.ColumnHeader) == partCell.Value);
        }
    }
}

using System.Linq;

using Model;

using QueryLogic.Joins.Abstraction;

using QueryLogic.RelationProviding;

namespace QueryLogic.Joins.Implementation

{

public abstract class OuterJoin : IOuterJoin

{

public abstract Relation CreateRelation(Node source);

public IRelationProvider FirstRelation { get; protected set; }

public IRelationProvider SecondRelation { get; protected set; }

protected void AddNonjoinedRows(Relation result, Relation source, Relation target)

{

foreach (Row row in source.Rows)

{

if (ContainsRowPart(result, row)) continue;

var newRow = new Row();

newRow.AddCells(row.Cells);

newRow.AddCells(target.Columns.Select(c => new Cell(c, null)));

result.AddRow(newRow);

}

private bool ContainsRowPart(Relation relation, Row rowPart)

{

return relation.Rows.Any(r => ContainsRowPart(r, rowPart));

}

private bool ContainsRowPart(Row source, Row part)

{

return part.Cells.All(partCell => source.GetCellValue(partCell.ColumnHeader) == partCell.Value);

}

using Model;
using QueryLogic.Predicates;
using QueryLogic.RelationProviding;

namespace QueryLogic.Joins.Implementation
{
    public class LeftOuterJoin : OuterJoin
    {
        public LeftOuterJoin(IRelationProvider firstRelation, IRelationProvider secondRelation, IPredicate predicate)
        {
            FirstRelation = firstRelation;
            SecondRelation = secondRelation;
            Predicate = predicate;
        }

        public IPredicate Predicate { get; private set; }

        protected bool Equals(LeftOuterJoin other)
        {
            return Equals(FirstRelation, other.FirstRelation) && Equals(SecondRelation, other.SecondRelation) &&
                   Equals(Predicate, other.Predicate);
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj)) return false;
            if (ReferenceEquals(this, obj)) return true;
            if (obj.GetType() != GetType()) return false;
            return Equals((LeftOuterJoin)obj);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                int hashCode = (FirstRelation != null ? FirstRelation.GetHashCode() : 0);
                hashCode = (hashCode * 397) ^ (SecondRelation != null ? SecondRelation.GetHashCode() : 0);
                hashCode = (hashCode * 397) ^ (Predicate != null ? Predicate.GetHashCode() : 0);
                return hashCode;
            }
        }

        public override Relation CreateRelation(Node source)
        {
            Relation result = new InnerJoin(FirstRelation, SecondRelation, Predicate).CreateRelation(source);

            AddNonjoinedRows(result, FirstRelation.CreateRelation(source), SecondRelation.CreateRelation(source));

            return result;
        }
    }
}

using Model;

using QueryLogic.Predicates;

using QueryLogic.RelationProviding;

namespace QueryLogic.Joins.Implementation

{

public class LeftOuterJoin : OuterJoin

{

public LeftOuterJoin(IRelationProvider firstRelation, IRelationProvider secondRelation, IPredicate predicate)

{

FirstRelation = firstRelation;

SecondRelation = secondRelation;

Predicate = predicate;

}

public IPredicate Predicate { get; private set; }

protected bool Equals(LeftOuterJoin other)

{

return Equals(FirstRelation, other.FirstRelation) && Equals(SecondRelation, other.SecondRelation) &&

Equals(Predicate, other.Predicate);

}

public override bool Equals(object obj)

{

if (ReferenceEquals(null, obj)) return false;

if (ReferenceEquals(this, obj)) return true;

if (obj.GetType() != GetType()) return false;

return Equals((LeftOuterJoin)obj);

}

public override int GetHashCode()

{

unchecked

{

int hashCode = (FirstRelation != null ? FirstRelation.GetHashCode() : 0);

hashCode = (hashCode * 397) ^ (SecondRelation != null ? SecondRelation.GetHashCode() : 0);

hashCode = (hashCode * 397) ^ (Predicate != null ? Predicate.GetHashCode() : 0);

return hashCode;

}

public override Relation CreateRelation(Node source)

{

Relation result = new InnerJoin(FirstRelation, SecondRelation, Predicate).CreateRelation(source);

AddNonjoinedRows(result, FirstRelation.CreateRelation(source), SecondRelation.CreateRelation(source));

return result;

}

using Model;
using QueryLogic.Joins.Abstraction;
using QueryLogic.Predicates;
using QueryLogic.RelationProviding;

namespace QueryLogic.Joins.Implementation
{
    public class RightOuterJoin : IOuterJoin
    {
        public RightOuterJoin(IRelationProvider firstRelation, IRelationProvider secondRelation, IPredicate predicate)
        {
            FirstRelation = firstRelation;
            SecondRelation = secondRelation;
            Predicate = predicate;
        }

        public IPredicate Predicate { get; private set; }
        public IRelationProvider FirstRelation { get; private set; }
        public IRelationProvider SecondRelation { get; private set; }

        public Relation CreateRelation(Node source)
        {
            return new LeftOuterJoin(SecondRelation, FirstRelation, Predicate).CreateRelation(source);
        }

        protected bool Equals(RightOuterJoin other)
        {
            return Equals(FirstRelation, other.FirstRelation) && Equals(SecondRelation, other.SecondRelation) &&
                   Equals(Predicate, other.Predicate);
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj)) return false;
            if (ReferenceEquals(this, obj)) return true;
            if (obj.GetType() != GetType()) return false;
            return Equals((RightOuterJoin)obj);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                int hashCode = (FirstRelation != null ? FirstRelation.GetHashCode() : 0);
                hashCode = (hashCode * 397) ^ (SecondRelation != null ? SecondRelation.GetHashCode() : 0);
                hashCode = (hashCode * 397) ^ (Predicate != null ? Predicate.GetHashCode() : 0);
                return hashCode;
            }
        }
    }
}

using Model;

using QueryLogic.Joins.Abstraction;

using QueryLogic.Predicates;

using QueryLogic.RelationProviding;

namespace QueryLogic.Joins.Implementation

{

public class RightOuterJoin : IOuterJoin

{

public RightOuterJoin(IRelationProvider firstRelation, IRelationProvider secondRelation, IPredicate predicate)

{

FirstRelation = firstRelation;

SecondRelation = secondRelation;

Predicate = predicate;

}

public IPredicate Predicate { get; private set; }

public IRelationProvider FirstRelation { get; private set; }

public IRelationProvider SecondRelation { get; private set; }

public Relation CreateRelation(Node source)

{

return new LeftOuterJoin(SecondRelation, FirstRelation, Predicate).CreateRelation(source);

}

protected bool Equals(RightOuterJoin other)

{

return Equals(FirstRelation, other.FirstRelation) && Equals(SecondRelation, other.SecondRelation) &&

Equals(Predicate, other.Predicate);

}

public override bool Equals(object obj)

{

if (ReferenceEquals(null, obj)) return false;

if (ReferenceEquals(this, obj)) return true;

if (obj.GetType() != GetType()) return false;

return Equals((RightOuterJoin)obj);

}

public override int GetHashCode()

{

unchecked

{

int hashCode = (FirstRelation != null ? FirstRelation.GetHashCode() : 0);

hashCode = (hashCode * 397) ^ (SecondRelation != null ? SecondRelation.GetHashCode() : 0);

hashCode = (hashCode * 397) ^ (Predicate != null ? Predicate.GetHashCode() : 0);

return hashCode;

}

using Model;
using QueryLogic.Predicates;
using QueryLogic.RelationProviding;

namespace QueryLogic.Joins.Implementation
{
    public class FullOuterJoin : OuterJoin
    {
        public FullOuterJoin(IRelationProvider firstRelation, IRelationProvider secondRelation, IPredicate predicate)
        {
            FirstRelation = firstRelation;
            SecondRelation = secondRelation;
            Predicate = predicate;
        }

        public IPredicate Predicate { get; private set; }

        protected bool Equals(FullOuterJoin other)
        {
            return Equals(FirstRelation, other.FirstRelation) && Equals(Predicate, other.Predicate) &&
                   Equals(SecondRelation, other.SecondRelation);
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj)) return false;
            if (ReferenceEquals(this, obj)) return true;
            if (obj.GetType() != GetType()) return false;
            return Equals((FullOuterJoin)obj);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                int hashCode = (FirstRelation != null ? FirstRelation.GetHashCode() : 0);
                hashCode = (hashCode * 397) ^ (Predicate != null ? Predicate.GetHashCode() : 0);
                hashCode = (hashCode * 397) ^ (SecondRelation != null ? SecondRelation.GetHashCode() : 0);
                return hashCode;
            }
        }

        public override Relation CreateRelation(Node source)
        {
            Relation result = new LeftOuterJoin(FirstRelation, SecondRelation, Predicate).CreateRelation(source);

            AddNonjoinedRows(result, SecondRelation.CreateRelation(source), FirstRelation.CreateRelation(source));

            return result;
        }
    }
}

using Model;

using QueryLogic.Predicates;

using QueryLogic.RelationProviding;

namespace QueryLogic.Joins.Implementation

{

public class FullOuterJoin : OuterJoin

{

public FullOuterJoin(IRelationProvider firstRelation, IRelationProvider secondRelation, IPredicate predicate)

{

FirstRelation = firstRelation;

SecondRelation = secondRelation;

Predicate = predicate;

}

public IPredicate Predicate { get; private set; }

protected bool Equals(FullOuterJoin other)

{

return Equals(FirstRelation, other.FirstRelation) && Equals(Predicate, other.Predicate) &&

Equals(SecondRelation, other.SecondRelation);

}

public override bool Equals(object obj)

{

if (ReferenceEquals(null, obj)) return false;

if (ReferenceEquals(this, obj)) return true;

if (obj.GetType() != GetType()) return false;

return Equals((FullOuterJoin)obj);

}

public override int GetHashCode()

{

unchecked

{

int hashCode = (FirstRelation != null ? FirstRelation.GetHashCode() : 0);

hashCode = (hashCode * 397) ^ (Predicate != null ? Predicate.GetHashCode() : 0);

hashCode = (hashCode * 397) ^ (SecondRelation != null ? SecondRelation.GetHashCode() : 0);

return hashCode;

}

public override Relation CreateRelation(Node source)

{

Relation result = new LeftOuterJoin(FirstRelation, SecondRelation, Predicate).CreateRelation(source);

AddNonjoinedRows(result, SecondRelation.CreateRelation(source), FirstRelation.CreateRelation(source));

return result;

}

Each OUTER JOIN is INNER JOIN + some missing rows which we add manually. That’s all.