diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/algebra/compiler/provider/GraphixCompilationProvider.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/algebra/compiler/provider/GraphixCompilationProvider.java
new file mode 100644
index 0000000..13d8c48
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/algebra/compiler/provider/GraphixCompilationProvider.java
@@ -0,0 +1,50 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.algebra.compiler.provider;
+
+import org.apache.asterix.algebra.base.ILangExpressionToPlanTranslatorFactory;
+import org.apache.asterix.compiler.provider.IRuleSetFactory;
+import org.apache.asterix.compiler.provider.SqlppCompilationProvider;
+import org.apache.asterix.graphix.algebra.translator.GraphixExpressionToPlanTranslatorFactory;
+import org.apache.asterix.graphix.lang.parser.GraphixParserFactory;
+import org.apache.asterix.graphix.lang.rewrites.GraphixRewriterFactory;
+import org.apache.asterix.lang.common.base.IParserFactory;
+import org.apache.asterix.lang.common.base.IRewriterFactory;
+
+public class GraphixCompilationProvider extends SqlppCompilationProvider {
+    @Override
+    public IParserFactory getParserFactory() {
+        return new GraphixParserFactory();
+    }
+
+    @Override
+    public IRuleSetFactory getRuleSetFactory() {
+        return new GraphixRuleSetFactory();
+    }
+
+    @Override
+    public IRewriterFactory getRewriterFactory() {
+        return new GraphixRewriterFactory(getParserFactory());
+    }
+
+    @Override
+    public ILangExpressionToPlanTranslatorFactory getExpressionToPlanTranslatorFactory() {
+        return new GraphixExpressionToPlanTranslatorFactory();
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/algebra/compiler/provider/GraphixRuleSetFactory.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/algebra/compiler/provider/GraphixRuleSetFactory.java
new file mode 100644
index 0000000..d37661c
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/algebra/compiler/provider/GraphixRuleSetFactory.java
@@ -0,0 +1,42 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.algebra.compiler.provider;
+
+import java.util.List;
+
+import org.apache.asterix.common.dataflow.ICcApplicationContext;
+import org.apache.asterix.compiler.provider.DefaultRuleSetFactory;
+import org.apache.asterix.compiler.provider.IRuleSetFactory;
+import org.apache.hyracks.algebricks.common.utils.Pair;
+import org.apache.hyracks.algebricks.core.rewriter.base.AbstractRuleController;
+import org.apache.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+
+public class GraphixRuleSetFactory implements IRuleSetFactory {
+    @Override
+    public List<Pair<AbstractRuleController, List<IAlgebraicRewriteRule>>> getLogicalRewrites(
+            ICcApplicationContext appCtx) {
+        return DefaultRuleSetFactory.buildLogical(appCtx);
+    }
+
+    @Override
+    public List<Pair<AbstractRuleController, List<IAlgebraicRewriteRule>>> getPhysicalRewrites(
+            ICcApplicationContext appCtx) {
+        return DefaultRuleSetFactory.buildPhysical(appCtx);
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/algebra/translator/GraphixExpressionToPlanTranslator.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/algebra/translator/GraphixExpressionToPlanTranslator.java
new file mode 100644
index 0000000..12a7f39
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/algebra/translator/GraphixExpressionToPlanTranslator.java
@@ -0,0 +1,32 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.algebra.translator;
+
+import java.util.Map;
+
+import org.apache.asterix.lang.common.struct.VarIdentifier;
+import org.apache.asterix.metadata.declared.MetadataProvider;
+import org.apache.asterix.om.base.IAObject;
+import org.apache.asterix.translator.SqlppExpressionToPlanTranslator;
+import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException;
+
+public class GraphixExpressionToPlanTranslator extends SqlppExpressionToPlanTranslator {
+    public GraphixExpressionToPlanTranslator(MetadataProvider metadataProvider, int currentVarCounter,
+            Map<VarIdentifier, IAObject> externalVars) throws AlgebricksException {
+        super(metadataProvider, currentVarCounter, externalVars);
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/algebra/translator/GraphixExpressionToPlanTranslatorFactory.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/algebra/translator/GraphixExpressionToPlanTranslatorFactory.java
new file mode 100644
index 0000000..c119e4d
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/algebra/translator/GraphixExpressionToPlanTranslatorFactory.java
@@ -0,0 +1,34 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ * http://www.apache.org/licenses/LICENSE-2.0
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.algebra.translator;
+
+import java.util.Map;
+
+import org.apache.asterix.algebra.base.ILangExpressionToPlanTranslator;
+import org.apache.asterix.algebra.base.ILangExpressionToPlanTranslatorFactory;
+import org.apache.asterix.lang.common.struct.VarIdentifier;
+import org.apache.asterix.metadata.declared.MetadataProvider;
+import org.apache.asterix.om.base.IAObject;
+import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException;
+
+public class GraphixExpressionToPlanTranslatorFactory implements ILangExpressionToPlanTranslatorFactory {
+    @Override
+    public ILangExpressionToPlanTranslator createExpressionToPlanTranslator(MetadataProvider metadataProvider,
+            int currentVarCounter, Map<VarIdentifier, IAObject> externalVars) throws AlgebricksException {
+        return new GraphixExpressionToPlanTranslator(metadataProvider, currentVarCounter, externalVars);
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/app/translator/GraphixQueryTranslator.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/app/translator/GraphixQueryTranslator.java
new file mode 100644
index 0000000..59889a3
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/app/translator/GraphixQueryTranslator.java
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.app.translator;
+
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+import java.util.concurrent.ExecutorService;
+import java.util.function.Function;
+
+import org.apache.asterix.app.translator.QueryTranslator;
+import org.apache.asterix.common.api.IResponsePrinter;
+import org.apache.asterix.common.dataflow.ICcApplicationContext;
+import org.apache.asterix.common.exceptions.CompilationException;
+import org.apache.asterix.common.exceptions.ErrorCode;
+import org.apache.asterix.common.functions.FunctionSignature;
+import org.apache.asterix.common.metadata.DataverseName;
+import org.apache.asterix.compiler.provider.ILangCompilationProvider;
+import org.apache.asterix.graphix.extension.GraphixMetadataExtension;
+import org.apache.asterix.graphix.lang.expression.GraphElementExpr;
+import org.apache.asterix.graphix.lang.rewrites.GraphixQueryRewriter;
+import org.apache.asterix.graphix.lang.rewrites.GraphixRewritingContext;
+import org.apache.asterix.graphix.lang.statement.GraphDropStatement;
+import org.apache.asterix.graphix.lang.statement.GraphElementDecl;
+import org.apache.asterix.graphix.metadata.entities.Graph;
+import org.apache.asterix.lang.common.base.Statement;
+import org.apache.asterix.lang.common.statement.DataverseDropStatement;
+import org.apache.asterix.lang.common.statement.DropDatasetStatement;
+import org.apache.asterix.lang.common.statement.FunctionDropStatement;
+import org.apache.asterix.lang.common.statement.Query;
+import org.apache.asterix.lang.common.statement.SynonymDropStatement;
+import org.apache.asterix.lang.common.statement.ViewDropStatement;
+import org.apache.asterix.lang.common.struct.Identifier;
+import org.apache.asterix.lang.common.util.ExpressionUtils;
+import org.apache.asterix.metadata.MetadataManager;
+import org.apache.asterix.metadata.MetadataTransactionContext;
+import org.apache.asterix.metadata.declared.MetadataProvider;
+import org.apache.asterix.metadata.entities.DependencyKind;
+import org.apache.asterix.translator.IRequestParameters;
+import org.apache.asterix.translator.SessionOutput;
+import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException;
+import org.apache.hyracks.algebricks.common.utils.Pair;
+import org.apache.hyracks.algebricks.common.utils.Triple;
+import org.apache.hyracks.api.client.IHyracksClientConnection;
+
+public class GraphixQueryTranslator extends QueryTranslator {
+    public GraphixQueryTranslator(ICcApplicationContext appCtx, List<Statement> statements, SessionOutput output,
+            ILangCompilationProvider compilationProvider, ExecutorService executorService,
+            IResponsePrinter responsePrinter) {
+        super(appCtx, statements, output, compilationProvider, executorService, responsePrinter);
+    }
+
+    public GraphixQueryRewriter getQueryRewriter() {
+        return (GraphixQueryRewriter) rewriterFactory.createQueryRewriter();
+    }
+
+    public void setGraphElementNormalizedBody(MetadataProvider metadataProvider, GraphElementDecl graphElementDecl,
+            GraphixQueryRewriter queryRewriter) throws CompilationException {
+        // Create a query AST for our rewriter to walk through.
+        GraphElementExpr functionCall = new GraphElementExpr(graphElementDecl.getIdentifier());
+        Query query = ExpressionUtils.createWrappedQuery(functionCall, graphElementDecl.getSourceLocation());
+
+        // We call our rewriter to set the normalized bodies of {@code graphElementDecl}.
+        GraphixRewritingContext graphixRewritingContext =
+                new GraphixRewritingContext(metadataProvider, declaredFunctions, null,
+                        Collections.singletonList(graphElementDecl), warningCollector, query.getVarCounter());
+        queryRewriter.loadNormalizedGraphElements(graphixRewritingContext, query);
+    }
+
+    @Override
+    protected void handleDropSynonymStatement(MetadataProvider metadataProvider, Statement stmt) throws Exception {
+        MetadataTransactionContext mdTxnCtx = MetadataManager.INSTANCE.beginTransaction();
+        metadataProvider.setMetadataTxnContext(mdTxnCtx);
+
+        // Forbid dropping the synonym if any graphs depend on this synonym.
+        DataverseName workingDataverse = getActiveDataverseName(((SynonymDropStatement) stmt).getDataverseName());
+        String synonymName = ((SynonymDropStatement) stmt).getSynonymName();
+        throwErrorIfDependentExists(mdTxnCtx, workingDataverse,
+                (dependency) -> dependency.first == DependencyKind.SYNONYM
+                        && dependency.second.second.equals(synonymName));
+
+        // Finish this transaction and perform the remainder of the DROP SYNONYM statement.
+        MetadataManager.INSTANCE.commitTransaction(mdTxnCtx);
+        super.handleDropSynonymStatement(metadataProvider, stmt);
+    }
+
+    @Override
+    protected void handleFunctionDropStatement(MetadataProvider metadataProvider, Statement stmt,
+            IRequestParameters requestParameters) throws Exception {
+        MetadataTransactionContext mdTxnCtx = MetadataManager.INSTANCE.beginTransaction();
+        metadataProvider.setMetadataTxnContext(mdTxnCtx);
+
+        // Forbid dropping the function if any graphs depend on this function.
+        FunctionSignature functionSignature = ((FunctionDropStatement) stmt).getFunctionSignature();
+        DataverseName workingDataverse = getActiveDataverseName(functionSignature.getDataverseName());
+        throwErrorIfDependentExists(mdTxnCtx, workingDataverse,
+                (dependency) -> dependency.first == DependencyKind.FUNCTION
+                        && dependency.second.second.equals(functionSignature.getName())
+                        && dependency.second.third.equals(Integer.toString(functionSignature.getArity())));
+
+        // Finish this transaction and perform the remainder of the DROP FUNCTION statement.
+        MetadataManager.INSTANCE.commitTransaction(mdTxnCtx);
+        super.handleFunctionDropStatement(metadataProvider, stmt, requestParameters);
+    }
+
+    @Override
+    public void handleViewDropStatement(MetadataProvider metadataProvider, Statement stmt) throws Exception {
+        MetadataTransactionContext mdTxnCtx = MetadataManager.INSTANCE.beginTransaction();
+        metadataProvider.setMetadataTxnContext(mdTxnCtx);
+
+        // Forbid dropping the dataset if any graphs depend on this dataset.
+        DataverseName workingDataverse = getActiveDataverseName(((ViewDropStatement) stmt).getDataverseName());
+        Identifier dsId = ((ViewDropStatement) stmt).getViewName();
+        throwErrorIfDependentExists(mdTxnCtx, workingDataverse,
+                (dependency) -> dependency.first == DependencyKind.DATASET
+                        && dependency.second.second.equals(dsId.getValue()));
+
+        // Finish this transaction and perform the remainder of the DROP VIEW statement.
+        MetadataManager.INSTANCE.commitTransaction(mdTxnCtx);
+        super.handleViewDropStatement(metadataProvider, stmt);
+    }
+
+    @Override
+    public void handleDatasetDropStatement(MetadataProvider metadataProvider, Statement stmt,
+            IHyracksClientConnection hcc, IRequestParameters requestParameters) throws Exception {
+        MetadataTransactionContext mdTxnCtx = MetadataManager.INSTANCE.beginTransaction();
+        metadataProvider.setMetadataTxnContext(mdTxnCtx);
+
+        // Forbid dropping the dataset if any graphs depend on this dataset.
+        DataverseName workingDataverse = getActiveDataverseName(((DropDatasetStatement) stmt).getDataverseName());
+        Identifier dsId = ((DropDatasetStatement) stmt).getDatasetName();
+        throwErrorIfDependentExists(mdTxnCtx, workingDataverse,
+                (dependency) -> dependency.first == DependencyKind.DATASET
+                        && dependency.second.second.equals(dsId.getValue()));
+
+        // Finish this transaction and perform the remainder of the DROP DATASET statement.
+        MetadataManager.INSTANCE.commitTransaction(mdTxnCtx);
+        super.handleDatasetDropStatement(metadataProvider, stmt, hcc, requestParameters);
+    }
+
+    private void throwErrorIfDependentExists(MetadataTransactionContext mdTxnCtx, DataverseName workingDataverse,
+            Function<Pair<DependencyKind, Triple<DataverseName, String, String>>, Boolean> isEntityDependent)
+            throws AlgebricksException {
+        List<Graph> allGraphs = GraphixMetadataExtension.getGraphs(mdTxnCtx, workingDataverse);
+        for (Graph graph : allGraphs) {
+            if (!graph.getDataverseName().equals(workingDataverse)) {
+                continue;
+            }
+            Iterator<Pair<DependencyKind, Triple<DataverseName, String, String>>> dependencyIterator =
+                    graph.getDependencies().getIterator();
+            while (dependencyIterator.hasNext()) {
+                Pair<DependencyKind, Triple<DataverseName, String, String>> dependency = dependencyIterator.next();
+                if (isEntityDependent.apply(dependency)) {
+                    throw new CompilationException(ErrorCode.CANNOT_DROP_OBJECT_DEPENDENT_EXISTS, dependency.first,
+                            dependency.first.getDependencyDisplayName(dependency.second), "graph",
+                            graph.getGraphName());
+                }
+            }
+        }
+    }
+
+    @Override
+    protected void handleDataverseDropStatement(MetadataProvider metadataProvider, Statement stmt,
+            IHyracksClientConnection hcc, IRequestParameters requestParameters) throws Exception {
+        MetadataTransactionContext mdTxnCtx = MetadataManager.INSTANCE.beginTransaction();
+        metadataProvider.setMetadataTxnContext(mdTxnCtx);
+
+        // Forbid dropping this dataverse if other graphs that are outside this dataverse depend on this dataverse.
+        DataverseName droppedDataverse = ((DataverseDropStatement) stmt).getDataverseName();
+        List<Graph> allGraphs = GraphixMetadataExtension.getGraphs(mdTxnCtx, null);
+        for (Graph graph : allGraphs) {
+            if (graph.getDataverseName().equals(droppedDataverse)) {
+                continue;
+            }
+            Iterator<Pair<DependencyKind, Triple<DataverseName, String, String>>> dependencyIterator =
+                    graph.getDependencies().getIterator();
+            while (dependencyIterator.hasNext()) {
+                Pair<DependencyKind, Triple<DataverseName, String, String>> dependency = dependencyIterator.next();
+                if (dependency.second.first.equals(droppedDataverse)) {
+                    throw new CompilationException(ErrorCode.CANNOT_DROP_DATAVERSE_DEPENDENT_EXISTS, dependency.first,
+                            dependency.first.getDependencyDisplayName(dependency.second), "graph",
+                            graph.getGraphName());
+                }
+            }
+        }
+
+        // Perform a drop for all graphs contained in this dataverse.
+        MetadataProvider tempMdProvider = MetadataProvider.create(appCtx, metadataProvider.getDefaultDataverse());
+        tempMdProvider.getConfig().putAll(metadataProvider.getConfig());
+        for (Graph graph : allGraphs) {
+            if (!graph.getDataverseName().equals(droppedDataverse)) {
+                continue;
+            }
+            tempMdProvider.getLocks().reset();
+            GraphDropStatement gds = new GraphDropStatement(droppedDataverse, graph.getGraphName(), false);
+            gds.handle(hcc, this, requestParameters, tempMdProvider, 0);
+        }
+
+        // Finish this transaction and perform the remainder of the DROP DATAVERSE statement.
+        MetadataManager.INSTANCE.commitTransaction(mdTxnCtx);
+        super.handleDataverseDropStatement(metadataProvider, stmt, hcc, requestParameters);
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/app/translator/GraphixQueryTranslatorFactory.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/app/translator/GraphixQueryTranslatorFactory.java
new file mode 100644
index 0000000..a0c4d2f
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/app/translator/GraphixQueryTranslatorFactory.java
@@ -0,0 +1,39 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.app.translator;
+
+import java.util.List;
+
+import org.apache.asterix.app.translator.DefaultStatementExecutorFactory;
+import org.apache.asterix.app.translator.QueryTranslator;
+import org.apache.asterix.common.api.IResponsePrinter;
+import org.apache.asterix.common.context.IStorageComponentProvider;
+import org.apache.asterix.common.dataflow.ICcApplicationContext;
+import org.apache.asterix.compiler.provider.ILangCompilationProvider;
+import org.apache.asterix.lang.common.base.Statement;
+import org.apache.asterix.translator.SessionOutput;
+
+public class GraphixQueryTranslatorFactory extends DefaultStatementExecutorFactory {
+    @Override
+    public QueryTranslator create(ICcApplicationContext appCtx, List<Statement> statements, SessionOutput output,
+            ILangCompilationProvider compilationProvider, IStorageComponentProvider storageComponentProvider,
+            IResponsePrinter printer) {
+        return new GraphixQueryTranslator(appCtx, statements, output, compilationProvider, executorService, printer);
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/common/metadata/GraphElementIdentifier.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/common/metadata/GraphElementIdentifier.java
new file mode 100644
index 0000000..fdd4ed4
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/common/metadata/GraphElementIdentifier.java
@@ -0,0 +1,87 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.common.metadata;
+
+import java.io.Serializable;
+import java.util.Objects;
+
+public class GraphElementIdentifier implements Serializable {
+    private static final long serialVersionUID = 1L;
+    private final GraphIdentifier graphIdentifier;
+    private final Kind elementKind;
+    private final String labelName;
+
+    public GraphElementIdentifier(GraphIdentifier graphIdentifier, Kind elementKind, String labelName) {
+        this.graphIdentifier = graphIdentifier;
+        this.elementKind = elementKind;
+        this.labelName = labelName;
+    }
+
+    public GraphIdentifier getGraphIdentifier() {
+        return graphIdentifier;
+    }
+
+    public Kind getElementKind() {
+        return elementKind;
+    }
+
+    public String getLabelName() {
+        return labelName;
+    }
+
+    @Override
+    public String toString() {
+        return graphIdentifier + "#" + labelName + " ( " + elementKind + " )";
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o) {
+            return true;
+        }
+        if (o instanceof GraphElementIdentifier) {
+            GraphElementIdentifier that = (GraphElementIdentifier) o;
+            return graphIdentifier.equals(that.graphIdentifier) && elementKind.equals(that.elementKind)
+                    && labelName.equals(that.labelName);
+        }
+        return false;
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(graphIdentifier, elementKind, labelName);
+    }
+
+    public enum Kind {
+        VERTEX,
+        EDGE;
+
+        @Override
+        public String toString() {
+            switch (this) {
+                case EDGE:
+                    return "edge";
+                case VERTEX:
+                    return "vertex";
+                default:
+                    throw new IllegalStateException("Unknown graph element kind.");
+            }
+        }
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/common/metadata/GraphIdentifier.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/common/metadata/GraphIdentifier.java
new file mode 100644
index 0000000..4b78434
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/common/metadata/GraphIdentifier.java
@@ -0,0 +1,65 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.common.metadata;
+
+import java.io.Serializable;
+import java.util.Objects;
+
+import org.apache.asterix.common.metadata.DataverseName;
+
+public class GraphIdentifier implements Serializable {
+    private static final long serialVersionUID = 1L;
+    private final DataverseName dataverseName;
+    private final String graphName;
+
+    public GraphIdentifier(DataverseName dataverseName, String graphName) {
+        this.dataverseName = dataverseName;
+        this.graphName = graphName;
+    }
+
+    public DataverseName getDataverseName() {
+        return dataverseName;
+    }
+
+    public String getGraphName() {
+        return graphName;
+    }
+
+    @Override
+    public String toString() {
+        return dataverseName + "." + graphName;
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (this == o) {
+            return true;
+        }
+        if (o instanceof GraphIdentifier) {
+            GraphIdentifier that = (GraphIdentifier) o;
+            return dataverseName.equals(that.dataverseName) && graphName.equals(that.graphName);
+        }
+        return false;
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(dataverseName, graphName);
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/extension/GraphixLangExtension.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/extension/GraphixLangExtension.java
new file mode 100644
index 0000000..2c46266
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/extension/GraphixLangExtension.java
@@ -0,0 +1,50 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.extension;
+
+import java.util.List;
+
+import org.apache.asterix.algebra.base.ILangExtension;
+import org.apache.asterix.common.api.ExtensionId;
+import org.apache.asterix.compiler.provider.ILangCompilationProvider;
+import org.apache.asterix.graphix.algebra.compiler.provider.GraphixCompilationProvider;
+import org.apache.hyracks.algebricks.common.utils.Pair;
+
+public class GraphixLangExtension implements ILangExtension {
+    public static final ExtensionId LANG_EXTENSION_ID = new ExtensionId(GraphixLangExtension.class.getSimpleName(), 0);
+
+    @Override
+    public ExtensionId getId() {
+        return LANG_EXTENSION_ID;
+    }
+
+    @Override
+    public void configure(List<Pair<String, String>> args) {
+    }
+
+    @Override
+    public ILangCompilationProvider getLangCompilationProvider(Language lang) {
+        return (lang == Language.SQLPP) ? new GraphixCompilationProvider() : null;
+    }
+
+    @Override
+    public ExtensionKind getExtensionKind() {
+        return ExtensionKind.LANG;
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/extension/GraphixMetadataExtension.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/extension/GraphixMetadataExtension.java
new file mode 100644
index 0000000..68df8b4
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/extension/GraphixMetadataExtension.java
@@ -0,0 +1,142 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.extension;
+
+import java.rmi.RemoteException;
+import java.util.Collections;
+import java.util.List;
+
+import org.apache.asterix.common.api.ExtensionId;
+import org.apache.asterix.common.exceptions.ACIDException;
+import org.apache.asterix.common.metadata.DataverseName;
+import org.apache.asterix.graphix.metadata.bootstrap.GraphixMetadataIndexes;
+import org.apache.asterix.graphix.metadata.bootstrap.GraphixMetadataRecordTypes;
+import org.apache.asterix.graphix.metadata.entities.Graph;
+import org.apache.asterix.metadata.MetadataManager;
+import org.apache.asterix.metadata.MetadataNode;
+import org.apache.asterix.metadata.MetadataTransactionContext;
+import org.apache.asterix.metadata.api.ExtensionMetadataDataset;
+import org.apache.asterix.metadata.api.ExtensionMetadataDatasetId;
+import org.apache.asterix.metadata.api.IExtensionMetadataSearchKey;
+import org.apache.asterix.metadata.api.IMetadataExtension;
+import org.apache.asterix.metadata.api.IMetadataIndex;
+import org.apache.asterix.metadata.bootstrap.MetadataBootstrap;
+import org.apache.asterix.metadata.entities.Datatype;
+import org.apache.asterix.metadata.entitytupletranslators.MetadataTupleTranslatorProvider;
+import org.apache.asterix.metadata.utils.MetadataConstants;
+import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException;
+import org.apache.hyracks.algebricks.common.utils.Pair;
+import org.apache.hyracks.api.application.INCServiceContext;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference;
+
+public class GraphixMetadataExtension implements IMetadataExtension {
+    public static final ExtensionId GRAPHIX_METADATA_EXTENSION_ID =
+            new ExtensionId(GraphixMetadataExtension.class.getName(), 0);
+
+    public static Graph getGraph(MetadataTransactionContext mdTxnCtx, DataverseName dataverseName, String graphName)
+            throws AlgebricksException {
+        IExtensionMetadataSearchKey graphSearchKey = new IExtensionMetadataSearchKey() {
+            private static final long serialVersionUID = 1L;
+
+            @Override
+            public ExtensionMetadataDatasetId getDatasetId() {
+                return GraphixMetadataIndexes.GRAPH_METADATA_DATASET_EXTENSION_ID;
+            }
+
+            @Override
+            public ITupleReference getSearchKey() {
+                return MetadataNode.createTuple(dataverseName, graphName);
+            }
+        };
+        List<Graph> graphs = MetadataManager.INSTANCE.getEntities(mdTxnCtx, graphSearchKey);
+        return (graphs.isEmpty()) ? null : graphs.get(0);
+    }
+
+    public static List<Graph> getGraphs(MetadataTransactionContext mdTxnTtx, DataverseName dataverseName)
+            throws AlgebricksException {
+        IExtensionMetadataSearchKey graphDataverseSearchKey = new IExtensionMetadataSearchKey() {
+            private static final long serialVersionUID = 1L;
+
+            @Override
+            public ExtensionMetadataDatasetId getDatasetId() {
+                return GraphixMetadataIndexes.GRAPH_METADATA_DATASET_EXTENSION_ID;
+            }
+
+            @Override
+            public ITupleReference getSearchKey() {
+                return (dataverseName == null) ? null : MetadataNode.createTuple(dataverseName);
+            }
+        };
+        return MetadataManager.INSTANCE.getEntities(mdTxnTtx, graphDataverseSearchKey);
+    }
+
+    @Override
+    public ExtensionId getId() {
+        return GRAPHIX_METADATA_EXTENSION_ID;
+    }
+
+    @Override
+    public void configure(List<Pair<String, String>> args) {
+        // No (extra) configuration needed.
+    }
+
+    @Override
+    public MetadataTupleTranslatorProvider getMetadataTupleTranslatorProvider() {
+        return new MetadataTupleTranslatorProvider();
+    }
+
+    @SuppressWarnings("rawtypes")
+    @Override
+    public List<ExtensionMetadataDataset> getExtensionIndexes() {
+        try {
+            return Collections.singletonList(GraphixMetadataIndexes.GRAPH_DATASET);
+
+        } catch (Throwable th) {
+            th.printStackTrace();
+            throw th;
+        }
+    }
+
+    @Override
+    public void initializeMetadata(INCServiceContext appCtx)
+            throws HyracksDataException, RemoteException, ACIDException {
+        MetadataBootstrap.enlistMetadataDataset(appCtx, GraphixMetadataIndexes.GRAPH_DATASET);
+        if (MetadataBootstrap.isNewUniverse()) {
+            MetadataTransactionContext mdTxnCtx = MetadataManager.INSTANCE.beginTransaction();
+            try {
+                // Insert our sole new metadata dataset (Graph).
+                MetadataBootstrap.insertMetadataDatasets(mdTxnCtx,
+                        new IMetadataIndex[] { GraphixMetadataIndexes.GRAPH_DATASET });
+
+                // Insert our sole datatype (Graph).
+                MetadataManager.INSTANCE.addDatatype(mdTxnCtx,
+                        new Datatype(MetadataConstants.METADATA_DATAVERSE_NAME,
+                                GraphixMetadataRecordTypes.GRAPH_RECORDTYPE.getTypeName(),
+                                GraphixMetadataRecordTypes.GRAPH_RECORDTYPE, false));
+
+                MetadataManager.INSTANCE.commitTransaction(mdTxnCtx);
+
+            } catch (Exception e) {
+                MetadataManager.INSTANCE.abortTransaction(mdTxnCtx);
+                throw HyracksDataException.create(e);
+            }
+        }
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/extension/GraphixQueryTranslatorExtension.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/extension/GraphixQueryTranslatorExtension.java
new file mode 100644
index 0000000..b6f7753
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/extension/GraphixQueryTranslatorExtension.java
@@ -0,0 +1,48 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.extension;
+
+import java.util.List;
+
+import org.apache.asterix.app.cc.IStatementExecutorExtension;
+import org.apache.asterix.common.api.ExtensionId;
+import org.apache.asterix.graphix.app.translator.GraphixQueryTranslatorFactory;
+import org.apache.asterix.translator.IStatementExecutorFactory;
+import org.apache.hyracks.algebricks.common.utils.Pair;
+
+public class GraphixQueryTranslatorExtension implements IStatementExecutorExtension {
+    public static final ExtensionId GRAPHIX_QUERY_TRANSLATOR_EXTENSION_ID =
+            new ExtensionId(GraphixQueryTranslatorExtension.class.getSimpleName(), 0);
+
+    private static final IStatementExecutorFactory INSTANCE = new GraphixQueryTranslatorFactory();
+
+    @Override
+    public ExtensionId getId() {
+        return GRAPHIX_QUERY_TRANSLATOR_EXTENSION_ID;
+    }
+
+    @Override
+    public void configure(List<Pair<String, String>> args) {
+    }
+
+    @Override
+    public IStatementExecutorFactory getQueryTranslatorFactory() {
+        return INSTANCE;
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/expression/GraphConstructor.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/expression/GraphConstructor.java
new file mode 100644
index 0000000..8ba4cea
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/expression/GraphConstructor.java
@@ -0,0 +1,238 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.lang.expression;
+
+import java.util.List;
+
+import org.apache.asterix.common.exceptions.CompilationException;
+import org.apache.asterix.graphix.lang.rewrites.visitor.IGraphixLangVisitor;
+import org.apache.asterix.lang.common.base.AbstractExpression;
+import org.apache.asterix.lang.common.base.AbstractLangExpression;
+import org.apache.asterix.lang.common.base.Expression;
+import org.apache.asterix.lang.common.visitor.base.ILangVisitor;
+
+public class GraphConstructor extends AbstractExpression {
+    private final List<VertexElement> vertexElements;
+    private final List<EdgeElement> edgeElements;
+
+    public GraphConstructor(List<VertexElement> vertexElements, List<EdgeElement> edgeElements) {
+        this.vertexElements = vertexElements;
+        this.edgeElements = edgeElements;
+    }
+
+    public List<VertexElement> getVertexElements() {
+        return vertexElements;
+    }
+
+    public List<EdgeElement> getEdgeElements() {
+        return edgeElements;
+    }
+
+    @Override
+    public Kind getKind() {
+        return null;
+    }
+
+    @Override
+    public <R, T> R accept(ILangVisitor<R, T> visitor, T arg) throws CompilationException {
+        return ((IGraphixLangVisitor<R, T>) visitor).visit(this, arg);
+    }
+
+    @Override
+    public boolean equals(Object object) {
+        if (this == object) {
+            return true;
+        }
+        if (!(object instanceof GraphConstructor)) {
+            return false;
+        }
+        GraphConstructor that = (GraphConstructor) object;
+        return vertexElements.equals(that.vertexElements) && edgeElements.equals(that.edgeElements);
+    }
+
+    public static class VertexElement extends AbstractLangExpression {
+        private final List<Integer> primaryKeySourceIndicators;
+        private final List<List<String>> primaryKeyFields;
+        private final Expression expression;
+        private final String definition;
+        private final String label;
+
+        public VertexElement(String label, List<List<String>> primaryKeyFields,
+                List<Integer> primaryKeySourceIndicators, Expression expression, String definition) {
+            this.primaryKeySourceIndicators = primaryKeySourceIndicators;
+            this.primaryKeyFields = primaryKeyFields;
+            this.expression = expression;
+            this.definition = definition;
+            this.label = label;
+        }
+
+        public List<List<String>> getPrimaryKeyFields() {
+            return primaryKeyFields;
+        }
+
+        public List<Integer> getPrimaryKeySourceIndicators() {
+            return primaryKeySourceIndicators;
+        }
+
+        public Expression getExpression() {
+            return expression;
+        }
+
+        public String getDefinition() {
+            return definition;
+        }
+
+        public String getLabel() {
+            return label;
+        }
+
+        @Override
+        public String toString() {
+            return "(:" + label + ") AS " + definition;
+        }
+
+        @Override
+        public <R, T> R accept(ILangVisitor<R, T> visitor, T arg) throws CompilationException {
+            return ((IGraphixLangVisitor<R, T>) visitor).visit(this, arg);
+        }
+
+        @Override
+        public boolean equals(Object object) {
+            if (this == object) {
+                return true;
+            }
+            if (!(object instanceof VertexElement)) {
+                return false;
+            }
+            VertexElement that = (VertexElement) object;
+            return primaryKeySourceIndicators.equals(that.primaryKeySourceIndicators)
+                    && primaryKeyFields.equals(that.primaryKeyFields) && expression.equals(that.expression)
+                    && definition.equals(that.definition) && label.equals(that.label);
+        }
+    }
+
+    public static class EdgeElement extends AbstractLangExpression {
+        private final List<Integer> destinationKeySourceIndicators;
+        private final List<Integer> sourceKeySourceIndicators;
+        private final List<Integer> primaryKeySourceIndicators;
+
+        private final List<List<String>> destinationKeyFields;
+        private final List<List<String>> sourceKeyFields;
+        private final List<List<String>> primaryKeyFields;
+
+        private final String destinationLabel, edgeLabel, sourceLabel;
+        private final Expression expression;
+        private final String definition;
+
+        public EdgeElement(String edgeLabel, String destinationLabel, String sourceLabel,
+                List<List<String>> primaryKeyFields, List<Integer> primaryKeySourceIndicators,
+                List<List<String>> destinationKeyFields, List<Integer> destinationKeySourceIndicators,
+                List<List<String>> sourceKeyFields, List<Integer> sourceKeySourceIndicators, Expression expression,
+                String definition) {
+            this.destinationKeySourceIndicators = destinationKeySourceIndicators;
+            this.sourceKeySourceIndicators = sourceKeySourceIndicators;
+            this.primaryKeySourceIndicators = primaryKeySourceIndicators;
+            this.destinationKeyFields = destinationKeyFields;
+            this.sourceKeyFields = sourceKeyFields;
+            this.primaryKeyFields = primaryKeyFields;
+            this.destinationLabel = destinationLabel;
+            this.edgeLabel = edgeLabel;
+            this.sourceLabel = sourceLabel;
+            this.expression = expression;
+            this.definition = definition;
+        }
+
+        public List<Integer> getDestinationKeySourceIndicators() {
+            return destinationKeySourceIndicators;
+        }
+
+        public List<Integer> getSourceKeySourceIndicators() {
+            return sourceKeySourceIndicators;
+        }
+
+        public List<Integer> getPrimaryKeySourceIndicators() {
+            return primaryKeySourceIndicators;
+        }
+
+        public List<List<String>> getDestinationKeyFields() {
+            return destinationKeyFields;
+        }
+
+        public List<List<String>> getSourceKeyFields() {
+            return sourceKeyFields;
+        }
+
+        public List<List<String>> getPrimaryKeyFields() {
+            return primaryKeyFields;
+        }
+
+        public String getDestinationLabel() {
+            return destinationLabel;
+        }
+
+        public String getEdgeLabel() {
+            return edgeLabel;
+        }
+
+        public String getSourceLabel() {
+            return sourceLabel;
+        }
+
+        public Expression getExpression() {
+            return expression;
+        }
+
+        public String getDefinition() {
+            return definition;
+        }
+
+        @Override
+        public String toString() {
+            String edgeBodyPattern = "[:" + edgeLabel + "]";
+            String sourceNodePattern = "(:" + sourceLabel + ")";
+            String destinationNodePattern = "(:" + destinationLabel + ")";
+            String edgePattern = sourceNodePattern + "-" + edgeBodyPattern + "->" + destinationNodePattern;
+            return (definition == null) ? edgePattern : (edgePattern + " AS " + definition);
+        }
+
+        @Override
+        public <R, T> R accept(ILangVisitor<R, T> visitor, T arg) throws CompilationException {
+            return ((IGraphixLangVisitor<R, T>) visitor).visit(this, arg);
+        }
+
+        @Override
+        public boolean equals(Object object) {
+            if (this == object) {
+                return true;
+            }
+            if (!(object instanceof EdgeElement)) {
+                return false;
+            }
+            EdgeElement that = (EdgeElement) object;
+            return destinationKeySourceIndicators.equals(that.destinationKeySourceIndicators)
+                    && sourceKeySourceIndicators.equals(that.sourceKeySourceIndicators)
+                    && primaryKeySourceIndicators.equals(that.primaryKeySourceIndicators)
+                    && destinationKeyFields.equals(that.destinationKeyFields)
+                    && sourceKeyFields.equals(that.sourceKeyFields) && primaryKeyFields.equals(that.primaryKeyFields)
+                    && destinationLabel.equals(that.destinationLabel) && edgeLabel.equals(that.edgeLabel)
+                    && sourceLabel.equals(that.sourceLabel) && expression.equals(that.expression)
+                    && definition.equals(that.definition);
+        }
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/expression/GraphElementExpr.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/expression/GraphElementExpr.java
new file mode 100644
index 0000000..11c1e34
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/expression/GraphElementExpr.java
@@ -0,0 +1,58 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.lang.expression;
+
+import java.util.Collections;
+
+import org.apache.asterix.common.functions.FunctionConstants;
+import org.apache.asterix.common.functions.FunctionSignature;
+import org.apache.asterix.graphix.common.metadata.GraphElementIdentifier;
+import org.apache.asterix.graphix.common.metadata.GraphIdentifier;
+import org.apache.asterix.graphix.lang.statement.GraphElementDecl;
+import org.apache.asterix.lang.common.expression.CallExpr;
+import org.apache.asterix.lang.common.statement.Query;
+import org.apache.asterix.lang.common.util.ExpressionUtils;
+import org.apache.hyracks.algebricks.core.algebra.functions.FunctionIdentifier;
+
+public class GraphElementExpr extends CallExpr {
+    public static final String GRAPH_ELEMENT_FUNCTION_NAME = "graph-element";
+    public static final FunctionIdentifier GRAPH_ELEMENT_FUNCTION_ID =
+            new FunctionIdentifier(FunctionConstants.ASTERIX_NS, GRAPH_ELEMENT_FUNCTION_NAME, 5);
+
+    // A graph element is uniquely identified by its identifier.
+    private final GraphElementIdentifier identifier;
+
+    public GraphElementExpr(GraphElementIdentifier identifier) {
+        super(new FunctionSignature(GRAPH_ELEMENT_FUNCTION_ID), Collections.emptyList(), null);
+        this.identifier = identifier;
+    }
+
+    public GraphElementIdentifier getIdentifier() {
+        return identifier;
+    }
+
+    public GraphIdentifier getGraphIdentifier() {
+        return identifier.getGraphIdentifier();
+    }
+
+    public static Query createGraphElementAccessorQuery(GraphElementDecl graphElementDecl) {
+        GraphElementExpr functionCall = new GraphElementExpr(graphElementDecl.getIdentifier());
+        return ExpressionUtils.createWrappedQuery(functionCall, graphElementDecl.getSourceLocation());
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/parser/GraphElementBodyParser.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/parser/GraphElementBodyParser.java
new file mode 100644
index 0000000..b1337b7
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/parser/GraphElementBodyParser.java
@@ -0,0 +1,56 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.lang.parser;
+
+import java.io.StringReader;
+import java.util.Objects;
+
+import org.apache.asterix.common.exceptions.CompilationException;
+import org.apache.asterix.graphix.lang.statement.GraphElementDecl;
+import org.apache.asterix.graphix.metadata.entities.Graph;
+import org.apache.hyracks.api.exceptions.IWarningCollector;
+
+public final class GraphElementBodyParser {
+    // Just a wrapper for the parseGraphElementBody method.
+    public static GraphElementDecl parse(Graph.Element element, GraphixParserFactory parserFactory,
+            IWarningCollector warningCollector) throws CompilationException {
+        GraphElementDecl graphElementDecl = null;
+        for (String definition : element.getDefinitions()) {
+            if (Objects.equals(definition, "")) {
+                continue;
+            }
+            GraphixParser parser = (GraphixParser) parserFactory.createParser(new StringReader(definition));
+            GraphElementDecl parsedElementDecl = parser.parseGraphElementBody(element.getIdentifier());
+
+            // Accumulate the element bodies.
+            if (graphElementDecl == null) {
+                graphElementDecl = parsedElementDecl;
+
+            } else {
+                graphElementDecl.getBodies().add(parsedElementDecl.getBodies().get(0));
+            }
+
+            // Gather any warnings.
+            if (warningCollector != null) {
+                parser.getWarnings(warningCollector);
+            }
+        }
+        return graphElementDecl;
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/parser/GraphixParserFactory.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/parser/GraphixParserFactory.java
new file mode 100644
index 0000000..ab97d6a
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/parser/GraphixParserFactory.java
@@ -0,0 +1,36 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.lang.parser;
+
+import java.io.Reader;
+
+import org.apache.asterix.lang.common.base.IParser;
+import org.apache.asterix.lang.sqlpp.parser.SqlppParserFactory;
+
+public class GraphixParserFactory extends SqlppParserFactory {
+    @Override
+    public IParser createParser(String query) {
+        return new GraphixParser(query);
+    }
+
+    @Override
+    public IParser createParser(Reader reader) {
+        return new GraphixParser(reader);
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/rewrites/GraphixQueryRewriter.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/rewrites/GraphixQueryRewriter.java
new file mode 100644
index 0000000..9e88251
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/rewrites/GraphixQueryRewriter.java
@@ -0,0 +1,186 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.lang.rewrites;
+
+import java.util.ArrayDeque;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.asterix.common.exceptions.CompilationException;
+import org.apache.asterix.common.exceptions.ErrorCode;
+import org.apache.asterix.common.metadata.DataverseName;
+import org.apache.asterix.graphix.common.metadata.GraphElementIdentifier;
+import org.apache.asterix.graphix.common.metadata.GraphIdentifier;
+import org.apache.asterix.graphix.extension.GraphixMetadataExtension;
+import org.apache.asterix.graphix.lang.expression.GraphElementExpr;
+import org.apache.asterix.graphix.lang.parser.GraphElementBodyParser;
+import org.apache.asterix.graphix.lang.parser.GraphixParserFactory;
+import org.apache.asterix.graphix.lang.statement.GraphElementDecl;
+import org.apache.asterix.graphix.metadata.entities.Graph;
+import org.apache.asterix.lang.common.base.Expression;
+import org.apache.asterix.lang.common.base.IParserFactory;
+import org.apache.asterix.lang.common.base.IReturningStatement;
+import org.apache.asterix.lang.common.expression.AbstractCallExpression;
+import org.apache.asterix.lang.common.statement.Query;
+import org.apache.asterix.lang.common.struct.VarIdentifier;
+import org.apache.asterix.lang.common.util.ExpressionUtils;
+import org.apache.asterix.lang.sqlpp.rewrites.SqlppQueryRewriter;
+import org.apache.asterix.lang.sqlpp.rewrites.visitor.SqlppGatherFunctionCallsVisitor;
+import org.apache.asterix.metadata.entities.Dataverse;
+import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException;
+import org.apache.hyracks.api.exceptions.SourceLocation;
+
+public class GraphixQueryRewriter extends SqlppQueryRewriter {
+    private final GraphixParserFactory parserFactory;
+    private final SqlppQueryRewriter bodyRewriter;
+
+    public GraphixQueryRewriter(IParserFactory parserFactory) {
+        super(parserFactory);
+
+        // We can safely downcast to our specific parser factory here.
+        this.parserFactory = (GraphixParserFactory) parserFactory;
+        this.bodyRewriter = new SqlppQueryRewriter(parserFactory);
+    }
+
+    public void rewrite(GraphixRewritingContext rewriteContext, IReturningStatement topStatement,
+            boolean allowNonStoredUdfCalls, boolean inlineUdfsAndViews, Collection<VarIdentifier> externalVars)
+            throws CompilationException {
+        // Get the graph elements in the top statement.
+        Map<GraphElementIdentifier, GraphElementDecl> graphElements =
+                loadNormalizedGraphElements(rewriteContext, topStatement);
+
+        // Perform the remainder of our rewrites in our parent.
+        super.rewrite(rewriteContext.getLangRewritingContext(), topStatement, allowNonStoredUdfCalls,
+                inlineUdfsAndViews, externalVars);
+    }
+
+    public Map<GraphElementIdentifier, GraphElementDecl> loadNormalizedGraphElements(
+            GraphixRewritingContext rewriteContext, IReturningStatement topExpr) throws CompilationException {
+        Map<GraphElementIdentifier, GraphElementDecl> graphElements = new HashMap<>();
+
+        // Gather all function calls.
+        Deque<AbstractCallExpression> workQueue = new ArrayDeque<>();
+        SqlppGatherFunctionCallsVisitor callVisitor = new SqlppGatherFunctionCallsVisitor(workQueue);
+        for (Expression expr : topExpr.getDirectlyEnclosedExpressions()) {
+            expr.accept(callVisitor, null);
+        }
+
+        AbstractCallExpression fnCall;
+        while ((fnCall = workQueue.poll()) != null) {
+            // Load only the graph element declarations (we will load the rest of the elements in the parent).
+            if (!fnCall.getKind().equals(Expression.Kind.CALL_EXPRESSION)
+                    || !fnCall.getFunctionSignature().getName().equals(GraphElementExpr.GRAPH_ELEMENT_FUNCTION_NAME)) {
+                continue;
+            }
+            GraphElementExpr graphElementExpr = (GraphElementExpr) fnCall;
+            GraphElementIdentifier identifier = graphElementExpr.getIdentifier();
+            if (!graphElements.containsKey(identifier)) {
+
+                // First, check if we have already loaded this graph element.
+                GraphElementDecl elementDecl = rewriteContext.getDeclaredGraphElements().get(identifier);
+
+                // If we cannot find the graph element in our context, search our metadata.
+                if (elementDecl == null) {
+                    GraphIdentifier graphIdentifier = identifier.getGraphIdentifier();
+                    Graph graph;
+                    try {
+                        graph = GraphixMetadataExtension.getGraph(
+                                rewriteContext.getMetadataProvider().getMetadataTxnContext(),
+                                graphIdentifier.getDataverseName(), graphIdentifier.getGraphName());
+
+                    } catch (AlgebricksException e) {
+                        throw new CompilationException(ErrorCode.COMPILATION_ERROR,
+                                graphElementExpr.getSourceLocation(),
+                                "Graph " + graphIdentifier.getGraphName() + " does not exist.");
+                    }
+
+                    // Parse our graph element.
+                    if (graph == null) {
+                        throw new CompilationException(ErrorCode.COMPILATION_ERROR,
+                                graphElementExpr.getSourceLocation(),
+                                "Graph " + graphIdentifier.getGraphName() + " does not exist.");
+                    }
+                    Graph.Element element = graph.getGraphSchema().getElement(identifier);
+                    elementDecl = GraphElementBodyParser.parse(element, parserFactory,
+                            rewriteContext.getLangRewritingContext().getWarningCollector());
+                }
+
+                // Get our normalized element bodies.
+                List<Expression> normalizedBodies = elementDecl.getNormalizedBodies();
+                if (normalizedBodies.size() != elementDecl.getBodies().size()) {
+                    GraphIdentifier graphIdentifier = elementDecl.getGraphIdentifier();
+                    for (Expression body : elementDecl.getBodies()) {
+                        Expression normalizedBody =
+                                rewriteGraphElementBody(rewriteContext, graphIdentifier.getDataverseName(), body,
+                                        Collections.emptyList(), elementDecl.getSourceLocation());
+                        normalizedBodies.add(normalizedBody);
+                    }
+                }
+
+                // Store the element declaration in our map, and iterate over this body.
+                graphElements.put(identifier, elementDecl);
+                for (Expression e : elementDecl.getNormalizedBodies()) {
+                    e.accept(callVisitor, null);
+                }
+            }
+        }
+
+        return graphElements;
+    }
+
+    private Expression rewriteGraphElementBody(GraphixRewritingContext rewriteContext, DataverseName elementDataverse,
+            Expression bodyExpr, List<VarIdentifier> externalVars, SourceLocation sourceLoc)
+            throws CompilationException {
+        Dataverse defaultDataverse = rewriteContext.getMetadataProvider().getDefaultDataverse();
+        Dataverse targetDataverse;
+
+        // We might need to change our dataverse, if the element definition requires a different one.
+        if (elementDataverse.equals(defaultDataverse.getDataverseName())) {
+            targetDataverse = defaultDataverse;
+
+        } else {
+            try {
+                targetDataverse = rewriteContext.getMetadataProvider().findDataverse(elementDataverse);
+
+            } catch (AlgebricksException e) {
+                throw new CompilationException(ErrorCode.UNKNOWN_DATAVERSE, e, sourceLoc, elementDataverse);
+            }
+        }
+        rewriteContext.getMetadataProvider().setDefaultDataverse(targetDataverse);
+
+        // Get the body of the rewritten query.
+        try {
+            Query wrappedQuery = ExpressionUtils.createWrappedQuery(bodyExpr, sourceLoc);
+            bodyRewriter.rewrite(rewriteContext.getLangRewritingContext(), wrappedQuery, false, false, externalVars);
+            return wrappedQuery.getBody();
+
+        } catch (CompilationException e) {
+            throw new CompilationException(ErrorCode.COMPILATION_ERROR, bodyExpr.getSourceLocation(),
+                    "Bad definition for a graph element: " + e.getMessage());
+
+        } finally {
+            // Switch back to the working dataverse.
+            rewriteContext.getMetadataProvider().setDefaultDataverse(defaultDataverse);
+        }
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/rewrites/GraphixRewriterFactory.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/rewrites/GraphixRewriterFactory.java
new file mode 100644
index 0000000..6b1cf30
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/rewrites/GraphixRewriterFactory.java
@@ -0,0 +1,40 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.lang.rewrites;
+
+import org.apache.asterix.graphix.lang.parser.GraphixParserFactory;
+import org.apache.asterix.lang.common.base.IParserFactory;
+import org.apache.asterix.lang.common.base.IQueryRewriter;
+import org.apache.asterix.lang.sqlpp.rewrites.SqlppRewriterFactory;
+
+public class GraphixRewriterFactory extends SqlppRewriterFactory {
+    private final GraphixParserFactory parserFactory;
+
+    public GraphixRewriterFactory(IParserFactory parserFactory) {
+        super(parserFactory);
+
+        // We can safely downcast the parser factory here.
+        this.parserFactory = (GraphixParserFactory) parserFactory;
+    }
+
+    @Override
+    public IQueryRewriter createQueryRewriter() {
+        return new GraphixQueryRewriter(parserFactory);
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/rewrites/GraphixRewritingContext.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/rewrites/GraphixRewritingContext.java
new file mode 100644
index 0000000..e62d337
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/rewrites/GraphixRewritingContext.java
@@ -0,0 +1,58 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.lang.rewrites;
+
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import org.apache.asterix.graphix.common.metadata.GraphElementIdentifier;
+import org.apache.asterix.graphix.lang.statement.GraphElementDecl;
+import org.apache.asterix.lang.common.rewrites.LangRewritingContext;
+import org.apache.asterix.lang.common.statement.FunctionDecl;
+import org.apache.asterix.lang.common.statement.ViewDecl;
+import org.apache.asterix.metadata.declared.MetadataProvider;
+import org.apache.hyracks.api.exceptions.IWarningCollector;
+
+public class GraphixRewritingContext {
+    private final Map<GraphElementIdentifier, GraphElementDecl> graphElementDeclMap = new HashMap<>();
+    private final LangRewritingContext langRewritingContext;
+
+    public GraphixRewritingContext(MetadataProvider metadataProvider, List<FunctionDecl> declaredFunctions,
+            List<ViewDecl> declaredViews, List<GraphElementDecl> declaredGraphElements,
+            IWarningCollector warningCollector, int varCounter) {
+        if (declaredGraphElements != null) {
+            declaredGraphElements.forEach(e -> graphElementDeclMap.put(e.getIdentifier(), e));
+        }
+        langRewritingContext = new LangRewritingContext(metadataProvider, declaredFunctions, declaredViews,
+                warningCollector, varCounter);
+    }
+
+    public Map<GraphElementIdentifier, GraphElementDecl> getDeclaredGraphElements() {
+        return graphElementDeclMap;
+    }
+
+    public LangRewritingContext getLangRewritingContext() {
+        return langRewritingContext;
+    }
+
+    public MetadataProvider getMetadataProvider() {
+        return langRewritingContext.getMetadataProvider();
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/rewrites/visitor/IGraphixLangVisitor.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/rewrites/visitor/IGraphixLangVisitor.java
new file mode 100644
index 0000000..2b41511
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/rewrites/visitor/IGraphixLangVisitor.java
@@ -0,0 +1,40 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.lang.rewrites.visitor;
+
+import org.apache.asterix.common.exceptions.CompilationException;
+import org.apache.asterix.graphix.lang.expression.GraphConstructor;
+import org.apache.asterix.graphix.lang.statement.CreateGraphStatement;
+import org.apache.asterix.graphix.lang.statement.GraphDropStatement;
+import org.apache.asterix.graphix.lang.statement.GraphElementDecl;
+import org.apache.asterix.lang.common.visitor.base.ILangVisitor;
+
+public interface IGraphixLangVisitor<R, T> extends ILangVisitor<R, T> {
+    R visit(GraphConstructor gc, T arg) throws CompilationException;
+
+    R visit(GraphConstructor.VertexElement ve, T arg) throws CompilationException;
+
+    R visit(GraphConstructor.EdgeElement ee, T arg) throws CompilationException;
+
+    R visit(CreateGraphStatement cgs, T arg) throws CompilationException;
+
+    R visit(GraphElementDecl gel, T arg) throws CompilationException;
+
+    R visit(GraphDropStatement gds, T arg) throws CompilationException;
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/statement/CreateGraphStatement.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/statement/CreateGraphStatement.java
new file mode 100644
index 0000000..866e2f2
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/statement/CreateGraphStatement.java
@@ -0,0 +1,110 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.lang.statement;
+
+import java.util.List;
+
+import org.apache.asterix.algebra.extension.ExtensionStatement;
+import org.apache.asterix.app.translator.QueryTranslator;
+import org.apache.asterix.common.exceptions.CompilationException;
+import org.apache.asterix.common.metadata.DataverseName;
+import org.apache.asterix.graphix.lang.expression.GraphConstructor;
+import org.apache.asterix.graphix.lang.rewrites.visitor.IGraphixLangVisitor;
+import org.apache.asterix.graphix.lang.util.GraphStatementHandlingUtil;
+import org.apache.asterix.lang.common.visitor.base.ILangVisitor;
+import org.apache.asterix.metadata.declared.MetadataProvider;
+import org.apache.asterix.translator.IRequestParameters;
+import org.apache.asterix.translator.IStatementExecutor;
+import org.apache.hyracks.api.client.IHyracksClientConnection;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+
+public class CreateGraphStatement extends ExtensionStatement {
+    private final GraphConstructor graphConstructor;
+    private final DataverseName dataverseName;
+    private final String graphName;
+    private final boolean replaceIfExists;
+    private final boolean ifNotExists;
+
+    public CreateGraphStatement(DataverseName dataverseName, String graphName, boolean replaceIfExists,
+            boolean ifNotExists, GraphConstructor graphConstructor) {
+        this.dataverseName = dataverseName;
+        this.graphName = graphName;
+        this.replaceIfExists = replaceIfExists;
+        this.ifNotExists = ifNotExists;
+        this.graphConstructor = graphConstructor;
+    }
+
+    public DataverseName getDataverseName() {
+        return dataverseName;
+    }
+
+    public String getGraphName() {
+        return graphName;
+    }
+
+    public boolean isReplaceIfExists() {
+        return replaceIfExists;
+    }
+
+    public boolean isIfNotExists() {
+        return ifNotExists;
+    }
+
+    public List<GraphConstructor.VertexElement> getVertexElements() {
+        return graphConstructor.getVertexElements();
+    }
+
+    public List<GraphConstructor.EdgeElement> getEdgeElements() {
+        return graphConstructor.getEdgeElements();
+    }
+
+    @Override
+    public <R, T> R accept(ILangVisitor<R, T> visitor, T arg) throws CompilationException {
+        return ((IGraphixLangVisitor<R, T>) visitor).visit(this, arg);
+    }
+
+    @Override
+    public byte getCategory() {
+        return Category.DDL;
+    }
+
+    @Override
+    public String getName() {
+        return CreateGraphStatement.class.getName();
+    }
+
+    @Override
+    public void handle(IHyracksClientConnection hcc, IStatementExecutor statementExecutor,
+            IRequestParameters requestParameters, MetadataProvider metadataProvider, int resultSetId) throws Exception {
+        metadataProvider.validateDatabaseObjectName(dataverseName, graphName, this.getSourceLocation());
+        DataverseName activeDataverseName = statementExecutor.getActiveDataverseName(this.dataverseName);
+        GraphStatementHandlingUtil.acquireGraphWriteLocks(metadataProvider, activeDataverseName, graphName);
+        try {
+            GraphStatementHandlingUtil.handleCreateGraph(this, metadataProvider, statementExecutor,
+                    activeDataverseName);
+
+        } catch (Exception e) {
+            QueryTranslator.abort(e, e, metadataProvider.getMetadataTxnContext());
+            throw HyracksDataException.create(e);
+
+        } finally {
+            metadataProvider.getLocks().unlock();
+        }
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/statement/GraphDropStatement.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/statement/GraphDropStatement.java
new file mode 100644
index 0000000..e9e8255
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/statement/GraphDropStatement.java
@@ -0,0 +1,90 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.lang.statement;
+
+import org.apache.asterix.algebra.extension.ExtensionStatement;
+import org.apache.asterix.app.translator.QueryTranslator;
+import org.apache.asterix.common.exceptions.CompilationException;
+import org.apache.asterix.common.metadata.DataverseName;
+import org.apache.asterix.graphix.lang.rewrites.visitor.IGraphixLangVisitor;
+import org.apache.asterix.graphix.lang.util.GraphStatementHandlingUtil;
+import org.apache.asterix.lang.common.visitor.base.ILangVisitor;
+import org.apache.asterix.metadata.declared.MetadataProvider;
+import org.apache.asterix.translator.IRequestParameters;
+import org.apache.asterix.translator.IStatementExecutor;
+import org.apache.hyracks.api.client.IHyracksClientConnection;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+
+public class GraphDropStatement extends ExtensionStatement {
+    private final DataverseName dataverseName;
+    private final String graphName;
+    private final boolean ifExists;
+
+    public GraphDropStatement(DataverseName dataverseName, String graphName, boolean ifExists) {
+        this.dataverseName = dataverseName;
+        this.graphName = graphName;
+        this.ifExists = ifExists;
+    }
+
+    public DataverseName getDataverseName() {
+        return dataverseName;
+    }
+
+    public String getGraphName() {
+        return graphName;
+    }
+
+    public boolean getIfExists() {
+        return ifExists;
+    }
+
+    @Override
+    public byte getCategory() {
+        return Category.DDL;
+    }
+
+    @Override
+    public <R, T> R accept(ILangVisitor<R, T> visitor, T arg) throws CompilationException {
+        return ((IGraphixLangVisitor<R, T>) visitor).visit(this, arg);
+    }
+
+    @Override
+    public String getName() {
+        return GraphDropStatement.class.getName();
+    }
+
+    @Override
+    public void handle(IHyracksClientConnection hcc, IStatementExecutor statementExecutor,
+            IRequestParameters requestParameters, MetadataProvider metadataProvider, int resultSetId) throws Exception {
+        metadataProvider.validateDatabaseObjectName(dataverseName, graphName, this.getSourceLocation());
+        DataverseName activeDataverseName = statementExecutor.getActiveDataverseName(this.dataverseName);
+        GraphStatementHandlingUtil.acquireGraphWriteLocks(metadataProvider, activeDataverseName, graphName);
+        try {
+            // TODO (GLENN): Determine how to handle functions and views that depend on graphs.
+            GraphStatementHandlingUtil.handleGraphDrop(this, metadataProvider, activeDataverseName);
+
+        } catch (Exception e) {
+            QueryTranslator.abort(e, e, metadataProvider.getMetadataTxnContext());
+            throw HyracksDataException.create(e);
+
+        } finally {
+            metadataProvider.getLocks().unlock();
+        }
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/statement/GraphElementDecl.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/statement/GraphElementDecl.java
new file mode 100644
index 0000000..c5e87de
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/statement/GraphElementDecl.java
@@ -0,0 +1,85 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.lang.statement;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+
+import org.apache.asterix.algebra.extension.ExtensionStatement;
+import org.apache.asterix.common.exceptions.CompilationException;
+import org.apache.asterix.common.exceptions.ErrorCode;
+import org.apache.asterix.graphix.common.metadata.GraphElementIdentifier;
+import org.apache.asterix.graphix.common.metadata.GraphIdentifier;
+import org.apache.asterix.graphix.lang.rewrites.visitor.IGraphixLangVisitor;
+import org.apache.asterix.lang.common.base.Expression;
+import org.apache.asterix.lang.common.visitor.base.ILangVisitor;
+import org.apache.asterix.metadata.declared.MetadataProvider;
+import org.apache.asterix.translator.IRequestParameters;
+import org.apache.asterix.translator.IStatementExecutor;
+import org.apache.hyracks.api.client.IHyracksClientConnection;
+
+public final class GraphElementDecl extends ExtensionStatement {
+    private final GraphElementIdentifier identifier;
+    private final List<Expression> bodies = new ArrayList<>();
+    private final List<Expression> normalizedBodies = new ArrayList<>();
+
+    public GraphElementDecl(GraphElementIdentifier identifier, Expression body) {
+        this.identifier = Objects.requireNonNull(identifier);
+        this.bodies.add(Objects.requireNonNull(body));
+    }
+
+    public GraphElementIdentifier getIdentifier() {
+        return identifier;
+    }
+
+    public GraphIdentifier getGraphIdentifier() {
+        return identifier.getGraphIdentifier();
+    }
+
+    public List<Expression> getBodies() {
+        return bodies;
+    }
+
+    public List<Expression> getNormalizedBodies() {
+        return normalizedBodies;
+    }
+
+    @Override
+    public byte getCategory() {
+        return Category.QUERY;
+    }
+
+    @Override
+    public <R, T> R accept(ILangVisitor<R, T> visitor, T arg) throws CompilationException {
+        return ((IGraphixLangVisitor<R, T>) visitor).visit(this, arg);
+    }
+
+    @Override
+    public String getName() {
+        return GraphElementDecl.class.getName();
+    }
+
+    @Override
+    public void handle(IHyracksClientConnection hcc, IStatementExecutor statementExecutor,
+            IRequestParameters requestParameters, MetadataProvider metadataProvider, int resultSetId) throws Exception {
+        throw new CompilationException(ErrorCode.COMPILATION_ILLEGAL_STATE, getSourceLocation(),
+                "Handling a GraphElementDecl (this should not be possible).");
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/util/GraphStatementHandlingUtil.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/util/GraphStatementHandlingUtil.java
new file mode 100644
index 0000000..1d7d0da
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/util/GraphStatementHandlingUtil.java
@@ -0,0 +1,226 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.lang.util;
+
+import java.rmi.RemoteException;
+import java.util.LinkedHashMap;
+import java.util.Map;
+
+import org.apache.asterix.common.api.IMetadataLockManager;
+import org.apache.asterix.common.exceptions.CompilationException;
+import org.apache.asterix.common.exceptions.ErrorCode;
+import org.apache.asterix.common.metadata.DataverseName;
+import org.apache.asterix.graphix.app.translator.GraphixQueryTranslator;
+import org.apache.asterix.graphix.common.metadata.GraphElementIdentifier;
+import org.apache.asterix.graphix.common.metadata.GraphIdentifier;
+import org.apache.asterix.graphix.extension.GraphixMetadataExtension;
+import org.apache.asterix.graphix.lang.expression.GraphConstructor;
+import org.apache.asterix.graphix.lang.rewrites.GraphixQueryRewriter;
+import org.apache.asterix.graphix.lang.statement.CreateGraphStatement;
+import org.apache.asterix.graphix.lang.statement.GraphDropStatement;
+import org.apache.asterix.graphix.lang.statement.GraphElementDecl;
+import org.apache.asterix.graphix.metadata.entities.Graph;
+import org.apache.asterix.graphix.metadata.entities.GraphDependencies;
+import org.apache.asterix.lang.common.base.Expression;
+import org.apache.asterix.metadata.MetadataManager;
+import org.apache.asterix.metadata.MetadataTransactionContext;
+import org.apache.asterix.metadata.declared.MetadataProvider;
+import org.apache.asterix.metadata.entities.Dataverse;
+import org.apache.asterix.translator.IStatementExecutor;
+import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException;
+
+public final class GraphStatementHandlingUtil {
+    public static void acquireGraphWriteLocks(MetadataProvider metadataProvider, DataverseName activeDataverseName,
+            String graphName) throws AlgebricksException {
+        // Acquire a READ lock on our dataverse and a WRITE lock on our graph.
+        IMetadataLockManager metadataLockManager = metadataProvider.getApplicationContext().getMetadataLockManager();
+        metadataLockManager.acquireDataverseReadLock(metadataProvider.getLocks(), activeDataverseName);
+        metadataLockManager.acquireExtensionEntityWriteLock(metadataProvider.getLocks(),
+                GraphixMetadataExtension.GRAPHIX_METADATA_EXTENSION_ID.getName(), activeDataverseName, graphName);
+    }
+
+    public static void handleCreateGraph(CreateGraphStatement cgs, MetadataProvider metadataProvider,
+            IStatementExecutor statementExecutor, DataverseName activeDataverseName) throws Exception {
+        MetadataTransactionContext mdTxnCtx = MetadataManager.INSTANCE.beginTransaction();
+        metadataProvider.setMetadataTxnContext(mdTxnCtx);
+
+        // Ensure that our active dataverse exists.
+        Dataverse dv = MetadataManager.INSTANCE.getDataverse(mdTxnCtx, activeDataverseName);
+        if (dv == null) {
+            throw new CompilationException(ErrorCode.UNKNOWN_DATAVERSE, cgs.getSourceLocation(), activeDataverseName);
+        }
+
+        // If a graph already exists, skip.
+        Graph existingGraph = GraphixMetadataExtension.getGraph(mdTxnCtx, activeDataverseName, cgs.getGraphName());
+        if (existingGraph != null) {
+            if (cgs.isIfNotExists()) {
+                MetadataManager.INSTANCE.commitTransaction(mdTxnCtx);
+                return;
+
+            } else if (!cgs.isReplaceIfExists()) {
+                throw new CompilationException(ErrorCode.COMPILATION_ERROR, cgs.getSourceLocation(),
+                        "Graph " + existingGraph.getGraphName() + " already exists.");
+            }
+        }
+
+        // Build the graph schema.
+        GraphIdentifier graphIdentifier = new GraphIdentifier(activeDataverseName, cgs.getGraphName());
+        Graph.Schema.Builder schemaBuilder = new Graph.Schema.Builder(graphIdentifier);
+        Map<GraphElementIdentifier, GraphElementDecl> graphElementDecls = new LinkedHashMap<>();
+        for (GraphConstructor.VertexElement vertex : cgs.getVertexElements()) {
+            Graph.Vertex schemaVertex =
+                    schemaBuilder.addVertex(vertex.getLabel(), vertex.getPrimaryKeyFields(), vertex.getDefinition());
+            switch (schemaBuilder.getLastError()) {
+                case NO_ERROR:
+                    GraphElementIdentifier id = schemaVertex.getIdentifier();
+                    if (graphElementDecls.containsKey(id)) {
+                        graphElementDecls.get(id).getBodies().add(vertex.getExpression());
+
+                    } else {
+                        GraphElementDecl decl = new GraphElementDecl(id, vertex.getExpression());
+                        decl.setSourceLocation(vertex.getSourceLocation());
+                        graphElementDecls.put(schemaVertex.getIdentifier(), decl);
+                    }
+                    break;
+
+                case CONFLICTING_PRIMARY_KEY:
+                    throw new CompilationException(ErrorCode.COMPILATION_ERROR, vertex.getSourceLocation(),
+                            "Conflicting primary keys for vertices with label " + vertex.getLabel());
+
+                default:
+                    throw new CompilationException(ErrorCode.COMPILATION_ILLEGAL_STATE, vertex.getSourceLocation(),
+                            "Schema vertex was not returned, but the error is not a conflicting primary key!");
+            }
+        }
+        for (GraphConstructor.EdgeElement edge : cgs.getEdgeElements()) {
+            Graph.Edge schemaEdge;
+            if (edge.getDefinition() == null) {
+                schemaEdge = schemaBuilder.addEdge(edge.getEdgeLabel(), edge.getDestinationLabel(),
+                        edge.getSourceLabel(), edge.getDestinationKeyFields());
+
+            } else {
+                schemaEdge = schemaBuilder.addEdge(edge.getEdgeLabel(), edge.getDestinationLabel(),
+                        edge.getSourceLabel(), edge.getPrimaryKeyFields(), edge.getDestinationKeyFields(),
+                        edge.getSourceKeyFields(), edge.getDefinition());
+            }
+
+            switch (schemaBuilder.getLastError()) {
+                case NO_ERROR:
+                    if (edge.getDefinition() != null) {
+                        GraphElementIdentifier id = schemaEdge.getIdentifier();
+                        if (graphElementDecls.containsKey(id)) {
+                            graphElementDecls.get(id).getBodies().add(edge.getExpression());
+
+                        } else {
+                            GraphElementDecl decl = new GraphElementDecl(id, edge.getExpression());
+                            decl.setSourceLocation(edge.getSourceLocation());
+                            graphElementDecls.put(id, decl);
+                        }
+                    }
+                    break;
+
+                case SOURCE_VERTEX_NOT_FOUND:
+                    throw new CompilationException(ErrorCode.COMPILATION_ERROR, edge.getSourceLocation(),
+                            "Source vertex " + edge.getSourceLabel() + " not found in the edge " + edge.getEdgeLabel()
+                                    + ".");
+
+                case DESTINATION_VERTEX_NOT_FOUND:
+                    throw new CompilationException(ErrorCode.COMPILATION_ERROR, edge.getSourceLocation(),
+                            "Destination vertex " + edge.getDestinationLabel() + " not found in the edge "
+                                    + edge.getEdgeLabel() + ".");
+
+                case CONFLICTING_PRIMARY_KEY:
+                case CONFLICTING_SOURCE_VERTEX:
+                case CONFLICTING_DESTINATION_VERTEX:
+                    throw new CompilationException(ErrorCode.COMPILATION_ERROR, edge.getSourceLocation(),
+                            "Conflicting edge with the same label found: " + edge.getEdgeLabel());
+
+                default:
+                    throw new CompilationException(ErrorCode.COMPILATION_ILLEGAL_STATE, edge.getSourceLocation(),
+                            "Schema edge was not returned, and an unexpected error encountered");
+            }
+        }
+
+        // Verify that each element definition is usable.
+        GraphixQueryRewriter graphixQueryRewriter = ((GraphixQueryTranslator) statementExecutor).getQueryRewriter();
+        metadataProvider.setDefaultDataverse(dv);
+        for (GraphElementDecl graphElementDecl : graphElementDecls.values()) {
+            ((GraphixQueryTranslator) statementExecutor).setGraphElementNormalizedBody(metadataProvider,
+                    graphElementDecl, graphixQueryRewriter);
+        }
+
+        // Build our dependencies (collected over all graph element bodies).
+        GraphDependencies graphDependencies = new GraphDependencies();
+        for (GraphElementDecl graphElementDecl : graphElementDecls.values()) {
+            if (graphElementDecl.getNormalizedBodies().size() != graphElementDecl.getBodies().size()) {
+                // We should have set the normalized body by calling {@code normalizeGraphElementAsQuery} beforehand.
+                throw new CompilationException(ErrorCode.COMPILATION_ILLEGAL_STATE,
+                        graphElementDecl.getSourceLocation(), "Normalized body not found!");
+            }
+            for (Expression normalizedBody : graphElementDecl.getNormalizedBodies()) {
+                graphDependencies.collectDependencies(normalizedBody, graphixQueryRewriter);
+            }
+        }
+
+        // Add / upsert our graph to our metadata.
+        Graph newGraph = new Graph(graphIdentifier, schemaBuilder.build(), graphDependencies);
+        if (existingGraph == null) {
+            MetadataManager.INSTANCE.addEntity(mdTxnCtx, newGraph);
+
+        } else {
+            MetadataManager.INSTANCE.upsertEntity(mdTxnCtx, newGraph);
+        }
+        MetadataManager.INSTANCE.commitTransaction(mdTxnCtx);
+    }
+
+    public static void handleGraphDrop(GraphDropStatement gds, MetadataProvider metadataProvider,
+            DataverseName activeDataverseName) throws RemoteException, AlgebricksException {
+        MetadataTransactionContext mdTxnCtx = MetadataManager.INSTANCE.beginTransaction();
+        metadataProvider.setMetadataTxnContext(mdTxnCtx);
+
+        // Verify that our active dataverse exists.
+        Dataverse dataverse = MetadataManager.INSTANCE.getDataverse(mdTxnCtx, activeDataverseName);
+        if (dataverse == null) {
+            if (gds.getIfExists()) {
+                MetadataManager.INSTANCE.commitTransaction(mdTxnCtx);
+                return;
+
+            } else {
+                throw new CompilationException(ErrorCode.UNKNOWN_DATAVERSE, gds.getSourceLocation(),
+                        activeDataverseName);
+            }
+        }
+
+        // Verify that our graph exists. If it does not, skip.
+        Graph graph = GraphixMetadataExtension.getGraph(mdTxnCtx, activeDataverseName, gds.getGraphName());
+        if (graph == null) {
+            if (gds.getIfExists()) {
+                MetadataManager.INSTANCE.commitTransaction(mdTxnCtx);
+                return;
+
+            } else {
+                throw new CompilationException(ErrorCode.COMPILATION_ERROR, gds.getSourceLocation(),
+                        "Graph " + gds.getGraphName() + " does not exist.");
+            }
+        }
+
+        MetadataManager.INSTANCE.deleteEntity(mdTxnCtx, graph);
+        MetadataManager.INSTANCE.commitTransaction(mdTxnCtx);
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/bootstrap/GraphixMetadataIndexes.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/bootstrap/GraphixMetadataIndexes.java
new file mode 100644
index 0000000..c2e7770
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/bootstrap/GraphixMetadataIndexes.java
@@ -0,0 +1,54 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.metadata.bootstrap;
+
+import static org.apache.asterix.metadata.bootstrap.MetadataRecordTypes.FIELD_NAME_DATAVERSE_NAME;
+
+import java.util.Arrays;
+import java.util.Collections;
+
+import org.apache.asterix.common.metadata.MetadataIndexImmutableProperties;
+import org.apache.asterix.graphix.extension.GraphixMetadataExtension;
+import org.apache.asterix.graphix.metadata.entities.Graph;
+import org.apache.asterix.graphix.metadata.entitytupletranslators.GraphTupleTranslator;
+import org.apache.asterix.metadata.api.ExtensionMetadataDataset;
+import org.apache.asterix.metadata.api.ExtensionMetadataDatasetId;
+import org.apache.asterix.metadata.api.IMetadataEntityTupleTranslatorFactory;
+import org.apache.asterix.om.types.BuiltinType;
+import org.apache.asterix.om.types.IAType;
+
+public class GraphixMetadataIndexes {
+    public static final String METADATA_DATASET_NAME_GRAPH = "Graph";
+
+    public static final ExtensionMetadataDatasetId GRAPH_METADATA_DATASET_EXTENSION_ID = new ExtensionMetadataDatasetId(
+            GraphixMetadataExtension.GRAPHIX_METADATA_EXTENSION_ID, METADATA_DATASET_NAME_GRAPH);
+
+    public static final MetadataIndexImmutableProperties PROPERTIES_GRAPH_METADATA_DATASET =
+            new MetadataIndexImmutableProperties(METADATA_DATASET_NAME_GRAPH,
+                    MetadataIndexImmutableProperties.FIRST_AVAILABLE_EXTENSION_METADATA_DATASET_ID,
+                    MetadataIndexImmutableProperties.FIRST_AVAILABLE_EXTENSION_METADATA_DATASET_ID);
+
+    public static final ExtensionMetadataDataset<Graph> GRAPH_DATASET = new ExtensionMetadataDataset<>(
+            PROPERTIES_GRAPH_METADATA_DATASET, 3, new IAType[] { BuiltinType.ASTRING, BuiltinType.ASTRING },
+            Arrays.asList(Collections.singletonList(FIELD_NAME_DATAVERSE_NAME),
+                    Collections.singletonList(GraphixMetadataRecordTypes.FIELD_NAME_GRAPH_NAME)),
+            0, GraphixMetadataRecordTypes.GRAPH_RECORDTYPE, true, new int[] { 0, 1 },
+            GRAPH_METADATA_DATASET_EXTENSION_ID,
+            (IMetadataEntityTupleTranslatorFactory<Graph>) GraphTupleTranslator::new);
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/bootstrap/GraphixMetadataRecordTypes.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/bootstrap/GraphixMetadataRecordTypes.java
new file mode 100644
index 0000000..055056d
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/bootstrap/GraphixMetadataRecordTypes.java
@@ -0,0 +1,86 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.metadata.bootstrap;
+
+import static org.apache.asterix.metadata.bootstrap.MetadataRecordTypes.FIELD_NAME_DATAVERSE_NAME;
+import static org.apache.asterix.metadata.bootstrap.MetadataRecordTypes.FIELD_NAME_DEPENDENCIES;
+import static org.apache.asterix.metadata.bootstrap.MetadataRecordTypes.FIELD_NAME_PRIMARY_KEY;
+
+import org.apache.asterix.metadata.bootstrap.MetadataRecordTypes;
+import org.apache.asterix.om.types.AOrderedListType;
+import org.apache.asterix.om.types.ARecordType;
+import org.apache.asterix.om.types.BuiltinType;
+import org.apache.asterix.om.types.IAType;
+
+public final class GraphixMetadataRecordTypes {
+    public static final String RECORD_NAME_GRAPH = "GraphRecordType";
+    public static final String RECORD_NAME_VERTICES = "VerticesRecordType";
+    public static final String RECORD_NAME_EDGES = "EdgesRecordType";
+
+    public static final String FIELD_NAME_DEFINITIONS = "Definitions";
+    public static final String FIELD_NAME_DESTINATION_KEY = "DestinationKey";
+    public static final String FIELD_NAME_DESTINATION_LABEL = "DestinationLabel";
+    public static final String FIELD_NAME_EDGES = "Edges";
+    public static final String FIELD_NAME_GRAPH_NAME = "GraphName";
+    public static final String FIELD_NAME_LABEL = "Label";
+    public static final String FIELD_NAME_SOURCE_KEY = "SourceKey";
+    public static final String FIELD_NAME_SOURCE_LABEL = "SourceLabel";
+    public static final String FIELD_NAME_VERTICES = "Vertices";
+
+    public static final int GRAPH_VERTICES_ARECORD_LABEL_FIELD_INDEX = 0;
+    public static final int GRAPH_VERTICES_ARECORD_PRIMARY_KEY_FIELD_INDEX = 1;
+    public static final int GRAPH_VERTICES_ARECORD_DEFINITIONS_FIELD_INDEX = 2;
+    public static final ARecordType VERTICES_RECORDTYPE = MetadataRecordTypes.createRecordType(RECORD_NAME_VERTICES,
+            new String[] { FIELD_NAME_LABEL, FIELD_NAME_PRIMARY_KEY, FIELD_NAME_DEFINITIONS },
+            new IAType[] { BuiltinType.ASTRING,
+                    new AOrderedListType(new AOrderedListType(BuiltinType.ASTRING, null), null),
+                    new AOrderedListType(BuiltinType.ASTRING, null) },
+            true);
+
+    public static final int GRAPH_EDGES_ARECORD_LABEL_FIELD_INDEX = 0;
+    public static final int GRAPH_EDGES_ARECORD_DEST_LABEL_FIELD_INDEX = 1;
+    public static final int GRAPH_EDGES_ARECORD_SOURCE_LABEL_FIELD_INDEX = 2;
+    public static final int GRAPH_EDGES_ARECORD_PRIMARY_KEY_FIELD_INDEX = 3;
+    public static final int GRAPH_EDGES_ARECORD_DEST_KEY_FIELD_INDEX = 4;
+    public static final int GRAPH_EDGES_ARECORD_SOURCE_KEY_FIELD_INDEX = 5;
+    public static final int GRAPH_EDGES_ARECORD_DEFINITIONS_FIELD_INDEX = 6;
+    public static final ARecordType EDGES_RECORDTYPE = MetadataRecordTypes.createRecordType(RECORD_NAME_EDGES,
+            new String[] { FIELD_NAME_LABEL, FIELD_NAME_DESTINATION_LABEL, FIELD_NAME_SOURCE_LABEL,
+                    FIELD_NAME_PRIMARY_KEY, FIELD_NAME_DESTINATION_KEY, FIELD_NAME_SOURCE_KEY, FIELD_NAME_DEFINITIONS },
+            new IAType[] { BuiltinType.ASTRING, BuiltinType.ASTRING, BuiltinType.ASTRING,
+                    new AOrderedListType(new AOrderedListType(BuiltinType.ASTRING, null), null),
+                    new AOrderedListType(new AOrderedListType(BuiltinType.ASTRING, null), null),
+                    new AOrderedListType(new AOrderedListType(BuiltinType.ASTRING, null), null),
+                    new AOrderedListType(BuiltinType.ASTRING, null) },
+            true);
+
+    public static final int GRAPH_ARECORD_DATAVERSENAME_FIELD_INDEX = 0;
+    public static final int GRAPH_ARECORD_GRAPHNAME_FIELD_INDEX = 1;
+    public static final int GRAPH_ARECORD_DEPENDENCIES_FIELD_INDEX = 2;
+    public static final int GRAPH_ARECORD_VERTICES_FIELD_INDEX = 3;
+    public static final int GRAPH_ARECORD_EDGES_FIELD_INDEX = 4;
+    public static final ARecordType GRAPH_RECORDTYPE = MetadataRecordTypes.createRecordType(RECORD_NAME_GRAPH,
+            new String[] { FIELD_NAME_DATAVERSE_NAME, FIELD_NAME_GRAPH_NAME, FIELD_NAME_DEPENDENCIES,
+                    FIELD_NAME_VERTICES, FIELD_NAME_EDGES },
+            new IAType[] { BuiltinType.ASTRING, BuiltinType.ASTRING,
+                    new AOrderedListType(new AOrderedListType(new AOrderedListType(BuiltinType.ASTRING, null), null),
+                            null),
+                    new AOrderedListType(VERTICES_RECORDTYPE, null), new AOrderedListType(EDGES_RECORDTYPE, null) },
+            true);
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entities/Graph.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entities/Graph.java
new file mode 100644
index 0000000..21afc2d
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entities/Graph.java
@@ -0,0 +1,348 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.metadata.entities;
+
+import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Objects;
+
+import org.apache.asterix.common.metadata.DataverseName;
+import org.apache.asterix.graphix.common.metadata.GraphElementIdentifier;
+import org.apache.asterix.graphix.common.metadata.GraphIdentifier;
+import org.apache.asterix.graphix.metadata.bootstrap.GraphixMetadataIndexes;
+import org.apache.asterix.metadata.api.ExtensionMetadataDatasetId;
+import org.apache.asterix.metadata.api.IExtensionMetadataEntity;
+
+/**
+ * Metadata describing a graph view, composed of vertices and edges.
+ */
+public class Graph implements IExtensionMetadataEntity {
+    private static final long serialVersionUID = 1L;
+
+    private final GraphIdentifier identifier;
+    private final GraphDependencies dependencies;
+    private final Schema graphSchema;
+
+    public Graph(GraphIdentifier identifier, Schema graphSchema, GraphDependencies dependencies) {
+        this.identifier = Objects.requireNonNull(identifier);
+        this.dependencies = dependencies;
+        this.graphSchema = graphSchema;
+    }
+
+    public DataverseName getDataverseName() {
+        return identifier.getDataverseName();
+    }
+
+    public String getGraphName() {
+        return identifier.getGraphName();
+    }
+
+    public GraphIdentifier getIdentifier() {
+        return identifier;
+    }
+
+    public Schema getGraphSchema() {
+        return graphSchema;
+    }
+
+    public GraphDependencies getDependencies() {
+        return dependencies;
+    }
+
+    @Override
+    public ExtensionMetadataDatasetId getDatasetId() {
+        return GraphixMetadataIndexes.GRAPH_METADATA_DATASET_EXTENSION_ID;
+    }
+
+    public static class Schema implements Serializable {
+        private static final long serialVersionUID = 1L;
+
+        // The element map is composed of the vertices and edges.
+        private final Map<GraphElementIdentifier, Element> elementMap = new HashMap<>();
+        private final List<Vertex> vertexList = new ArrayList<>();
+        private final List<Edge> edgeList = new ArrayList<>();
+
+        public List<Vertex> getVertices() {
+            return vertexList;
+        }
+
+        public List<Edge> getEdges() {
+            return edgeList;
+        }
+
+        public Element getElement(GraphElementIdentifier identifier) {
+            return elementMap.get(identifier);
+        }
+
+        private Schema() {
+        }
+
+        public static class Builder {
+            private final Map<String, Vertex> vertexLabelMap = new HashMap<>();
+            private final Map<String, Edge> edgeLabelMap = new HashMap<>();
+
+            // We aim to populate the schema object below.
+            private final Schema workingSchema = new Schema();
+            private final GraphIdentifier graphIdentifier;
+            private Error lastError = Error.NO_ERROR;
+
+            public Builder(GraphIdentifier graphIdentifier) {
+                this.graphIdentifier = graphIdentifier;
+            }
+
+            /**
+             * @return Null if the primary keys of an existing vertex conflict with the vertex to-be-added. The vertex
+             * to-be-added otherwise.
+             */
+            public Vertex addVertex(String labelName, List<List<String>> primaryKeyFieldNames, String definition) {
+                if (!vertexLabelMap.containsKey(labelName)) {
+                    GraphElementIdentifier identifier =
+                            new GraphElementIdentifier(graphIdentifier, GraphElementIdentifier.Kind.VERTEX, labelName);
+                    Vertex newVertex = new Vertex(identifier, primaryKeyFieldNames, definition);
+                    workingSchema.vertexList.add(newVertex);
+                    vertexLabelMap.put(labelName, newVertex);
+                    return newVertex;
+
+                } else {
+                    Vertex existingVertex = vertexLabelMap.get(labelName);
+                    if (!existingVertex.getPrimaryKeyFieldNames().equals(primaryKeyFieldNames)) {
+                        lastError = Error.CONFLICTING_PRIMARY_KEY;
+                        return null;
+                    }
+                    existingVertex.getDefinitions().add(definition);
+                    return existingVertex;
+                }
+            }
+
+            /**
+             * @return Null if there exists no vertex with the given source label or destination label, OR if the
+             * primary key / source vertex / destination vertex of an existing edge conflict with the edge to-be-added.
+             */
+            public Edge addEdge(String edgeLabelName, String destinationLabelName, String sourceLabelName,
+                    List<List<String>> destinationKeyFieldNames) {
+                if (!vertexLabelMap.containsKey(sourceLabelName)) {
+                    lastError = Error.SOURCE_VERTEX_NOT_FOUND;
+                    return null;
+                }
+
+                Vertex representativeSourceVertex = vertexLabelMap.get(sourceLabelName);
+                return addEdge(edgeLabelName, destinationLabelName, sourceLabelName,
+                        representativeSourceVertex.getPrimaryKeyFieldNames(), destinationKeyFieldNames,
+                        representativeSourceVertex.getPrimaryKeyFieldNames(), "");
+            }
+
+            /**
+             * @return Null if there exists no vertex with the given source label or destination label, OR if the
+             * primary key / source vertex / destination vertex of an existing edge conflict with the edge to-be-added.
+             */
+            public Edge addEdge(String edgeLabelName, String destinationLabelName, String sourceLabelName,
+                    List<List<String>> primaryKeyFieldNames, List<List<String>> destinationKeyFieldNames,
+                    List<List<String>> sourceKeyFieldNames, String definition) {
+                if (!vertexLabelMap.containsKey(sourceLabelName)) {
+                    lastError = Error.SOURCE_VERTEX_NOT_FOUND;
+                    return null;
+
+                } else if (!vertexLabelMap.containsKey(destinationLabelName)) {
+                    lastError = Error.DESTINATION_VERTEX_NOT_FOUND;
+                    return null;
+
+                } else if (edgeLabelMap.containsKey(edgeLabelName)) {
+                    Edge existingEdge = edgeLabelMap.get(edgeLabelName);
+                    if (!existingEdge.getPrimaryKeyFieldNames().equals(primaryKeyFieldNames)) {
+                        lastError = Error.CONFLICTING_PRIMARY_KEY;
+                        return null;
+
+                    } else if (!existingEdge.getSourceLabelName().equals(sourceLabelName)) {
+                        // This also covers any source-key conflicts.
+                        lastError = Error.CONFLICTING_SOURCE_VERTEX;
+                        return null;
+
+                    } else if (!existingEdge.getDestinationLabelName().equals(destinationLabelName)) {
+                        // This also covers any destination-key conflicts.
+                        lastError = Error.CONFLICTING_DESTINATION_VERTEX;
+                        return null;
+                    }
+                    existingEdge.getDefinitions().add(definition);
+                    return existingEdge;
+
+                } else {
+                    GraphElementIdentifier identifier = new GraphElementIdentifier(graphIdentifier,
+                            GraphElementIdentifier.Kind.EDGE, edgeLabelName);
+                    Edge newEdge = new Edge(identifier, primaryKeyFieldNames, destinationKeyFieldNames,
+                            sourceKeyFieldNames, vertexLabelMap.get(destinationLabelName),
+                            vertexLabelMap.get(sourceLabelName), definition);
+                    workingSchema.edgeList.add(newEdge);
+                    edgeLabelMap.put(edgeLabelName, newEdge);
+                    return newEdge;
+                }
+            }
+
+            public Schema build() {
+                // Build the element map, composed of our vertices and edges.
+                workingSchema.elementMap.clear();
+                workingSchema.getVertices().forEach(v -> workingSchema.elementMap.put(v.identifier, v));
+                workingSchema.getEdges().forEach(e -> workingSchema.elementMap.put(e.identifier, e));
+                return workingSchema;
+            }
+
+            public Error getLastError() {
+                return lastError;
+            }
+
+            public enum Error {
+                NO_ERROR,
+
+                CONFLICTING_PRIMARY_KEY,
+                CONFLICTING_SOURCE_VERTEX,
+                CONFLICTING_DESTINATION_VERTEX,
+
+                SOURCE_VERTEX_NOT_FOUND,
+                DESTINATION_VERTEX_NOT_FOUND
+            }
+        }
+    }
+
+    public static final class Vertex implements Element {
+        private static final long serialVersionUID = 1L;
+
+        private final GraphElementIdentifier identifier;
+        private final List<List<String>> primaryKeyFieldNames;
+        private final List<String> definitions;
+
+        private Vertex(GraphElementIdentifier identifier, List<List<String>> primaryKeyFieldNames, String definition) {
+            this.identifier = Objects.requireNonNull(identifier);
+            this.primaryKeyFieldNames = Objects.requireNonNull(primaryKeyFieldNames);
+            this.definitions = new ArrayList<>();
+            this.definitions.add(Objects.requireNonNull(definition));
+        }
+
+        public List<List<String>> getPrimaryKeyFieldNames() {
+            return primaryKeyFieldNames;
+        }
+
+        @Override
+        public GraphElementIdentifier getIdentifier() {
+            return identifier;
+        }
+
+        @Override
+        public String getLabelName() {
+            return identifier.getLabelName();
+        }
+
+        @Override
+        public List<String> getDefinitions() {
+            return definitions;
+        }
+
+        @Override
+        public String toString() {
+            return "(:" + getLabelName() + ") AS " + String.join(",\n", definitions);
+        }
+    }
+
+    public static final class Edge implements Element {
+        private static final long serialVersionUID = 1L;
+
+        private final List<List<String>> primaryKeyFieldNames;
+        private final List<List<String>> destinationKeyFieldNames;
+        private final List<List<String>> sourceKeyFieldNames;
+
+        private final GraphElementIdentifier identifier;
+        private final Vertex destinationVertex;
+        private final Vertex sourceVertex;
+        private final List<String> definitions;
+
+        private Edge(GraphElementIdentifier identifier, List<List<String>> primaryKeyFieldNames,
+                List<List<String>> destinationKeyFieldNames, List<List<String>> sourceKeyFieldNames,
+                Vertex destinationVertex, Vertex sourceVertex, String edgeDefinition) {
+            this.primaryKeyFieldNames = Objects.requireNonNull(primaryKeyFieldNames);
+            this.destinationKeyFieldNames = Objects.requireNonNull(destinationKeyFieldNames);
+            this.sourceKeyFieldNames = Objects.requireNonNull(sourceKeyFieldNames);
+            this.destinationVertex = Objects.requireNonNull(destinationVertex);
+            this.sourceVertex = Objects.requireNonNull(sourceVertex);
+            this.identifier = Objects.requireNonNull(identifier);
+            this.definitions = new ArrayList<>();
+            this.definitions.add(Objects.requireNonNull(edgeDefinition));
+        }
+
+        public String getDestinationLabelName() {
+            return destinationVertex.getLabelName();
+        }
+
+        public String getSourceLabelName() {
+            return sourceVertex.getLabelName();
+        }
+
+        public List<List<String>> getPrimaryKeyFieldNames() {
+            return primaryKeyFieldNames;
+        }
+
+        public List<List<String>> getDestinationKeyFieldNames() {
+            return destinationKeyFieldNames;
+        }
+
+        public List<List<String>> getSourceKeyFieldNames() {
+            return sourceKeyFieldNames;
+        }
+
+        public Vertex getDestinationVertex() {
+            return destinationVertex;
+        }
+
+        public Vertex getSourceVertex() {
+            return sourceVertex;
+        }
+
+        @Override
+        public GraphElementIdentifier getIdentifier() {
+            return identifier;
+        }
+
+        @Override
+        public String getLabelName() {
+            return identifier.getLabelName();
+        }
+
+        @Override
+        public List<String> getDefinitions() {
+            return definitions;
+        }
+
+        @Override
+        public String toString() {
+            String edgeBodyPattern = "[:" + getLabelName() + "]";
+            String sourceNodePattern = "(:" + getSourceLabelName() + ")";
+            String destinationNodePattern = "(:" + getDestinationLabelName() + ")";
+            String edgePattern = sourceNodePattern + "-" + edgeBodyPattern + "->" + destinationNodePattern;
+            return edgePattern + " AS " + String.join(",\n", getDefinitions());
+        }
+    }
+
+    public interface Element extends Serializable {
+        GraphElementIdentifier getIdentifier();
+
+        String getLabelName();
+
+        List<String> getDefinitions();
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entities/GraphDependencies.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entities/GraphDependencies.java
new file mode 100644
index 0000000..0e7aa5a
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entities/GraphDependencies.java
@@ -0,0 +1,76 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.asterix.graphix.metadata.entities;
+
+import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+
+import org.apache.asterix.common.exceptions.CompilationException;
+import org.apache.asterix.common.metadata.DataverseName;
+import org.apache.asterix.lang.common.base.Expression;
+import org.apache.asterix.lang.common.base.IQueryRewriter;
+import org.apache.asterix.lang.common.util.ExpressionUtils;
+import org.apache.asterix.metadata.entities.DependencyKind;
+import org.apache.hyracks.algebricks.common.utils.Pair;
+import org.apache.hyracks.algebricks.common.utils.Triple;
+
+/**
+ * Helper class to manage dependencies for a graph metadata entity.
+ */
+public class GraphDependencies {
+    private final List<Triple<DataverseName, String, String>> datasetDependencies;
+    private final List<Triple<DataverseName, String, String>> synonymDependencies;
+    private final List<Triple<DataverseName, String, String>> functionDependencies;
+
+    public GraphDependencies(List<List<Triple<DataverseName, String, String>>> listRepresentation) {
+        datasetDependencies = listRepresentation.get(0);
+        synonymDependencies = listRepresentation.get(1);
+        functionDependencies = listRepresentation.get(2);
+    }
+
+    public GraphDependencies() {
+        datasetDependencies = new ArrayList<>();
+        synonymDependencies = new ArrayList<>();
+        functionDependencies = new ArrayList<>();
+    }
+
+    public List<List<Triple<DataverseName, String, String>>> getListRepresentation() {
+        return List.of(datasetDependencies, synonymDependencies, functionDependencies);
+    }
+
+    public Iterator<Pair<DependencyKind, Triple<DataverseName, String, String>>> getIterator() {
+        List<Pair<DependencyKind, Triple<DataverseName, String, String>>> resultant = new ArrayList<>();
+        for (Triple<DataverseName, String, String> datasetDependency : datasetDependencies) {
+            resultant.add(new Pair<>(DependencyKind.DATASET, datasetDependency));
+        }
+        for (Triple<DataverseName, String, String> synonymDependency : synonymDependencies) {
+            resultant.add(new Pair<>(DependencyKind.SYNONYM, synonymDependency));
+        }
+        for (Triple<DataverseName, String, String> functionDependency : functionDependencies) {
+            resultant.add(new Pair<>(DependencyKind.FUNCTION, functionDependency));
+        }
+        return resultant.listIterator();
+    }
+
+    public void collectDependencies(Expression expression, IQueryRewriter queryRewriter) throws CompilationException {
+        ExpressionUtils.collectDependencies(expression, queryRewriter, datasetDependencies, synonymDependencies,
+                functionDependencies);
+    }
+}
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entitytupletranslators/GraphTupleTranslator.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entitytupletranslators/GraphTupleTranslator.java
new file mode 100644
index 0000000..9c83184
--- /dev/null
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entitytupletranslators/GraphTupleTranslator.java
@@ -0,0 +1,437 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.asterix.graphix.metadata.entitytupletranslators;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.asterix.builders.IARecordBuilder;
+import org.apache.asterix.builders.OrderedListBuilder;
+import org.apache.asterix.builders.RecordBuilder;
+import org.apache.asterix.common.exceptions.AsterixException;
+import org.apache.asterix.common.exceptions.ErrorCode;
+import org.apache.asterix.common.metadata.DataverseName;
+import org.apache.asterix.graphix.common.metadata.GraphIdentifier;
+import org.apache.asterix.graphix.metadata.bootstrap.GraphixMetadataIndexes;
+import org.apache.asterix.graphix.metadata.bootstrap.GraphixMetadataRecordTypes;
+import org.apache.asterix.graphix.metadata.entities.Graph;
+import org.apache.asterix.graphix.metadata.entities.GraphDependencies;
+import org.apache.asterix.metadata.entitytupletranslators.AbstractTupleTranslator;
+import org.apache.asterix.om.base.AOrderedList;
+import org.apache.asterix.om.base.ARecord;
+import org.apache.asterix.om.base.AString;
+import org.apache.asterix.om.base.IACursor;
+import org.apache.asterix.om.types.AOrderedListType;
+import org.apache.asterix.om.types.BuiltinType;
+import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException;
+import org.apache.hyracks.algebricks.common.utils.Triple;
+import org.apache.hyracks.api.exceptions.HyracksDataException;
+import org.apache.hyracks.data.std.util.ArrayBackedValueStorage;
+import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference;
+
+public class GraphTupleTranslator extends AbstractTupleTranslator<Graph> {
+    // Payload field containing serialized Graph.
+    private static final int GRAPH_PAYLOAD_TUPLE_FIELD_INDEX = 2;
+
+    // For constructing our dependency, edge, and vertex lists.
+    protected OrderedListBuilder listBuilder;
+    protected OrderedListBuilder innerListBuilder;
+    protected OrderedListBuilder nameListBuilder;
+    protected IARecordBuilder subRecordBuilder;
+    protected AOrderedListType stringListList;
+    protected AOrderedListType stringList;
+
+    public GraphTupleTranslator(boolean getTuple) {
+        super(getTuple, GraphixMetadataIndexes.GRAPH_DATASET, GRAPH_PAYLOAD_TUPLE_FIELD_INDEX);
+        if (getTuple) {
+            listBuilder = new OrderedListBuilder();
+            innerListBuilder = new OrderedListBuilder();
+            nameListBuilder = new OrderedListBuilder();
+            subRecordBuilder = new RecordBuilder();
+            stringListList = new AOrderedListType(new AOrderedListType(BuiltinType.ASTRING, null), null);
+            stringList = new AOrderedListType(BuiltinType.ASTRING, null);
+        }
+    }
+
+    @Override
+    protected Graph createMetadataEntityFromARecord(ARecord graphRecord) throws AlgebricksException {
+        // Read in the dataverse name.
+        DataverseName dataverseName = DataverseName.createFromCanonicalForm(((AString) graphRecord
+                .getValueByPos(GraphixMetadataRecordTypes.GRAPH_ARECORD_DATAVERSENAME_FIELD_INDEX)).getStringValue());
+
+        // Read in the graph name.
+        String graphName =
+                ((AString) graphRecord.getValueByPos(GraphixMetadataRecordTypes.GRAPH_ARECORD_GRAPHNAME_FIELD_INDEX))
+                        .getStringValue();
+
+        // Read in the dependencies.
+        IACursor dependenciesCursor = ((AOrderedList) graphRecord
+                .getValueByPos(GraphixMetadataRecordTypes.GRAPH_ARECORD_DEPENDENCIES_FIELD_INDEX)).getCursor();
+        List<List<Triple<DataverseName, String, String>>> graphDependencies = new ArrayList<>();
+        while (dependenciesCursor.next()) {
+            List<Triple<DataverseName, String, String>> dependencyList = new ArrayList<>();
+            IACursor qualifiedDependencyCursor = ((AOrderedList) dependenciesCursor.get()).getCursor();
+            while (qualifiedDependencyCursor.next()) {
+                Triple<DataverseName, String, String> dependency =
+                        getDependency((AOrderedList) qualifiedDependencyCursor.get());
+                dependencyList.add(dependency);
+            }
+            graphDependencies.add(dependencyList);
+        }
+
+        // Read in the vertex and edge lists.
+        GraphIdentifier graphIdentifier = new GraphIdentifier(dataverseName, graphName);
+        Graph.Schema graphSchema = readGraphSchema(graphRecord, graphIdentifier);
+        return new Graph(graphIdentifier, graphSchema, new GraphDependencies(graphDependencies));
+    }
+
+    private Graph.Schema readGraphSchema(ARecord graphRecord, GraphIdentifier graphIdentifier) throws AsterixException {
+        Graph.Schema.Builder schemaBuilder = new Graph.Schema.Builder(graphIdentifier);
+
+        // Read in the vertex list.
+        IACursor verticesCursor = ((AOrderedList) graphRecord
+                .getValueByPos(GraphixMetadataRecordTypes.GRAPH_ARECORD_VERTICES_FIELD_INDEX)).getCursor();
+        while (verticesCursor.next()) {
+            ARecord vertex = (ARecord) verticesCursor.get();
+
+            // Read in the label name.
+            String labelName = ((AString) vertex
+                    .getValueByPos(GraphixMetadataRecordTypes.GRAPH_VERTICES_ARECORD_LABEL_FIELD_INDEX))
+                            .getStringValue();
+
+            // Read in the primary key fields.
+            List<List<String>> primaryKeyFields = new ArrayList<>();
+            IACursor primaryKeyCursor = ((AOrderedList) vertex
+                    .getValueByPos(GraphixMetadataRecordTypes.GRAPH_VERTICES_ARECORD_PRIMARY_KEY_FIELD_INDEX))
+                            .getCursor();
+            while (primaryKeyCursor.next()) {
+                IACursor nameCursor = ((AOrderedList) primaryKeyCursor.get()).getCursor();
+                primaryKeyFields.add(readNameList(nameCursor));
+            }
+
+            // Read in the vertex definition(s). Validate each definition.
+            IACursor definitionsCursor = ((AOrderedList) vertex
+                    .getValueByPos(GraphixMetadataRecordTypes.GRAPH_VERTICES_ARECORD_DEFINITIONS_FIELD_INDEX))
+                            .getCursor();
+            while (definitionsCursor.next()) {
+                String definition = ((AString) definitionsCursor.get()).getStringValue();
+                schemaBuilder.addVertex(labelName, primaryKeyFields, definition);
+                switch (schemaBuilder.getLastError()) {
+                    case NO_ERROR:
+                        break;
+
+                    case CONFLICTING_PRIMARY_KEY:
+                        throw new AsterixException(ErrorCode.METADATA_ERROR,
+                                "Conflicting primary keys for vertices with label " + labelName);
+
+                    default:
+                        throw new AsterixException(ErrorCode.METADATA_ERROR,
+                                "Schema vertex was not returned, but the error is not a conflicting primary key!");
+                }
+            }
+        }
+
+        // Read in the edge list.
+        IACursor edgesCursor =
+                ((AOrderedList) graphRecord.getValueByPos(GraphixMetadataRecordTypes.GRAPH_ARECORD_EDGES_FIELD_INDEX))
+                        .getCursor();
+        while (edgesCursor.next()) {
+            ARecord edge = (ARecord) edgesCursor.get();
+
+            // Read in the label name.
+            String labelName =
+                    ((AString) edge.getValueByPos(GraphixMetadataRecordTypes.GRAPH_EDGES_ARECORD_LABEL_FIELD_INDEX))
+                            .getStringValue();
+
+            // Read in the destination label name.
+            String destinationLabelName = ((AString) edge
+                    .getValueByPos(GraphixMetadataRecordTypes.GRAPH_EDGES_ARECORD_DEST_LABEL_FIELD_INDEX))
+                            .getStringValue();
+
+            // Read in the source label name.
+            String sourceLabelName = ((AString) edge
+                    .getValueByPos(GraphixMetadataRecordTypes.GRAPH_EDGES_ARECORD_SOURCE_LABEL_FIELD_INDEX))
+                            .getStringValue();
+
+            // Read in the primary key fields.
+            List<List<String>> primaryKeyFields = new ArrayList<>();
+            IACursor primaryKeyCursor = ((AOrderedList) edge
+                    .getValueByPos(GraphixMetadataRecordTypes.GRAPH_EDGES_ARECORD_PRIMARY_KEY_FIELD_INDEX)).getCursor();
+            while (primaryKeyCursor.next()) {
+                IACursor nameCursor = ((AOrderedList) primaryKeyCursor.get()).getCursor();
+                primaryKeyFields.add(readNameList(nameCursor));
+            }
+
+            // Read in the destination key fields.
+            List<List<String>> destinationKeyFields = new ArrayList<>();
+            IACursor destinationKeyCursor = ((AOrderedList) edge
+                    .getValueByPos(GraphixMetadataRecordTypes.GRAPH_EDGES_ARECORD_DEST_KEY_FIELD_INDEX)).getCursor();
+            while (destinationKeyCursor.next()) {
+                IACursor nameCursor = ((AOrderedList) destinationKeyCursor.get()).getCursor();
+                destinationKeyFields.add(readNameList(nameCursor));
+            }
+
+            // Read in the source key fields.
+            List<List<String>> sourceKeyFields = new ArrayList<>();
+            IACursor sourceKeyCursor = ((AOrderedList) edge
+                    .getValueByPos(GraphixMetadataRecordTypes.GRAPH_EDGES_ARECORD_SOURCE_KEY_FIELD_INDEX)).getCursor();
+            while (sourceKeyCursor.next()) {
+                IACursor nameCursor = ((AOrderedList) sourceKeyCursor.get()).getCursor();
+                sourceKeyFields.add(readNameList(nameCursor));
+            }
+
+            // Read in the edge definition(s). Validate each definition.
+            IACursor definitionsCursor = ((AOrderedList) edge
+                    .getValueByPos(GraphixMetadataRecordTypes.GRAPH_EDGES_ARECORD_DEFINITIONS_FIELD_INDEX)).getCursor();
+            while (definitionsCursor.next()) {
+                String definition = ((AString) definitionsCursor.get()).getStringValue();
+                schemaBuilder.addEdge(labelName, destinationLabelName, sourceLabelName, primaryKeyFields,
+                        destinationKeyFields, sourceKeyFields, definition);
+                switch (schemaBuilder.getLastError()) {
+                    case NO_ERROR:
+                        break;
+
+                    case SOURCE_VERTEX_NOT_FOUND:
+                        throw new AsterixException(ErrorCode.METADATA_ERROR,
+                                "Source vertex " + sourceLabelName + " not found in the edge " + labelName + ".");
+
+                    case DESTINATION_VERTEX_NOT_FOUND:
+                        throw new AsterixException(ErrorCode.METADATA_ERROR, "Destination vertex "
+                                + destinationLabelName + " not found in the edge " + labelName + ".");
+
+                    case CONFLICTING_PRIMARY_KEY:
+                    case CONFLICTING_SOURCE_VERTEX:
+                    case CONFLICTING_DESTINATION_VERTEX:
+                        throw new AsterixException(ErrorCode.METADATA_ERROR,
+                                "Conflicting edge with the same label found: " + labelName);
+
+                    default:
+                        throw new AsterixException(ErrorCode.METADATA_ERROR,
+                                "Schema edge was not returned, and an unexpected error encountered");
+                }
+            }
+        }
+
+        return schemaBuilder.build();
+    }
+
+    private List<String> readNameList(IACursor nameCursor) {
+        List<String> fieldName = new ArrayList<>();
+        while (nameCursor.next()) {
+            String subName = ((AString) nameCursor.get()).getStringValue();
+            fieldName.add(subName);
+        }
+        return fieldName;
+    }
+
+    @Override
+    public ITupleReference getTupleFromMetadataEntity(Graph graph) throws HyracksDataException {
+        // Write our primary key (dataverse name, graph name).
+        String dataverseCanonicalName = graph.getDataverseName().getCanonicalForm();
+        tupleBuilder.reset();
+        aString.setValue(dataverseCanonicalName);
+        stringSerde.serialize(aString, tupleBuilder.getDataOutput());
+        tupleBuilder.addFieldEndOffset();
+        aString.setValue(graph.getGraphName());
+        stringSerde.serialize(aString, tupleBuilder.getDataOutput());
+        tupleBuilder.addFieldEndOffset();
+
+        // Write the payload in the third field of the tuple.
+        recordBuilder.reset(GraphixMetadataRecordTypes.GRAPH_RECORDTYPE);
+
+        // Write the dataverse name.
+        fieldValue.reset();
+        aString.setValue(dataverseCanonicalName);
+        stringSerde.serialize(aString, fieldValue.getDataOutput());
+        recordBuilder.addField(GraphixMetadataRecordTypes.GRAPH_ARECORD_DATAVERSENAME_FIELD_INDEX, fieldValue);
+
+        // Write the graph name.
+        fieldValue.reset();
+        aString.setValue(graph.getGraphName());
+        stringSerde.serialize(aString, fieldValue.getDataOutput());
+        recordBuilder.addField(GraphixMetadataRecordTypes.GRAPH_ARECORD_GRAPHNAME_FIELD_INDEX, fieldValue);
+
+        // Write our dependencies.
+        ArrayBackedValueStorage itemValue = new ArrayBackedValueStorage();
+        listBuilder.reset((AOrderedListType) GraphixMetadataRecordTypes.GRAPH_RECORDTYPE
+                .getFieldTypes()[GraphixMetadataRecordTypes.GRAPH_ARECORD_DEPENDENCIES_FIELD_INDEX]);
+        for (List<Triple<DataverseName, String, String>> dependencies : graph.getDependencies()
+                .getListRepresentation()) {
+            List<String> subNames = new ArrayList<>();
+            innerListBuilder.reset(stringListList);
+            for (Triple<DataverseName, String, String> dependency : dependencies) {
+                subNames.clear();
+                getDependencySubNames(dependency, subNames);
+                writeNameList(subNames, itemValue);
+                innerListBuilder.addItem(itemValue);
+            }
+            itemValue.reset();
+            innerListBuilder.write(itemValue.getDataOutput(), true);
+            listBuilder.addItem(itemValue);
+        }
+        fieldValue.reset();
+        listBuilder.write(fieldValue.getDataOutput(), true);
+        recordBuilder.addField(GraphixMetadataRecordTypes.GRAPH_ARECORD_DEPENDENCIES_FIELD_INDEX, fieldValue);
+
+        // Write our vertex set.
+        listBuilder.reset((AOrderedListType) GraphixMetadataRecordTypes.GRAPH_RECORDTYPE
+                .getFieldTypes()[GraphixMetadataRecordTypes.GRAPH_ARECORD_VERTICES_FIELD_INDEX]);
+        for (Graph.Vertex vertex : graph.getGraphSchema().getVertices()) {
+            writeVertexRecord(vertex, itemValue);
+            listBuilder.addItem(itemValue);
+        }
+        fieldValue.reset();
+        listBuilder.write(fieldValue.getDataOutput(), true);
+        recordBuilder.addField(GraphixMetadataRecordTypes.GRAPH_ARECORD_VERTICES_FIELD_INDEX, fieldValue);
+
+        // Write our edge set.
+        listBuilder.reset((AOrderedListType) GraphixMetadataRecordTypes.GRAPH_RECORDTYPE
+                .getFieldTypes()[GraphixMetadataRecordTypes.GRAPH_ARECORD_EDGES_FIELD_INDEX]);
+        for (Graph.Edge edge : graph.getGraphSchema().getEdges()) {
+            writeEdgeRecord(edge, itemValue);
+            listBuilder.addItem(itemValue);
+        }
+        fieldValue.reset();
+        listBuilder.write(fieldValue.getDataOutput(), true);
+        recordBuilder.addField(GraphixMetadataRecordTypes.GRAPH_ARECORD_EDGES_FIELD_INDEX, fieldValue);
+
+        // Finally, write our record.
+        recordBuilder.write(tupleBuilder.getDataOutput(), true);
+        tupleBuilder.addFieldEndOffset();
+        tuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
+        return tuple;
+    }
+
+    private void writeVertexRecord(Graph.Vertex vertex, ArrayBackedValueStorage itemValue) throws HyracksDataException {
+        subRecordBuilder.reset(GraphixMetadataRecordTypes.VERTICES_RECORDTYPE);
+
+        // Write the label name.
+        fieldValue.reset();
+        aString.setValue(vertex.getLabelName());
+        stringSerde.serialize(aString, fieldValue.getDataOutput());
+        subRecordBuilder.addField(GraphixMetadataRecordTypes.GRAPH_VERTICES_ARECORD_LABEL_FIELD_INDEX, fieldValue);
+
+        // Write the primary key fields.
+        fieldValue.reset();
+        innerListBuilder.reset(stringListList);
+        for (List<String> keyField : vertex.getPrimaryKeyFieldNames()) {
+            writeNameList(keyField, itemValue);
+            innerListBuilder.addItem(itemValue);
+        }
+        innerListBuilder.write(fieldValue.getDataOutput(), true);
+        subRecordBuilder.addField(GraphixMetadataRecordTypes.GRAPH_VERTICES_ARECORD_PRIMARY_KEY_FIELD_INDEX,
+                fieldValue);
+
+        // Write the vertex definition(s).
+        fieldValue.reset();
+        innerListBuilder.reset(stringList);
+        for (String definition : vertex.getDefinitions()) {
+            itemValue.reset();
+            aString.setValue(definition);
+            stringSerde.serialize(aString, itemValue.getDataOutput());
+            innerListBuilder.addItem(itemValue);
+        }
+        innerListBuilder.write(fieldValue.getDataOutput(), true);
+        subRecordBuilder.addField(GraphixMetadataRecordTypes.GRAPH_VERTICES_ARECORD_DEFINITIONS_FIELD_INDEX,
+                fieldValue);
+
+        itemValue.reset();
+        subRecordBuilder.write(itemValue.getDataOutput(), true);
+    }
+
+    private void writeEdgeRecord(Graph.Edge edge, ArrayBackedValueStorage itemValue) throws HyracksDataException {
+        subRecordBuilder.reset(GraphixMetadataRecordTypes.EDGES_RECORDTYPE);
+
+        // Write the label name.
+        fieldValue.reset();
+        aString.setValue(edge.getLabelName());
+        stringSerde.serialize(aString, fieldValue.getDataOutput());
+        subRecordBuilder.addField(GraphixMetadataRecordTypes.GRAPH_EDGES_ARECORD_LABEL_FIELD_INDEX, fieldValue);
+
+        // Write the destination label name.
+        fieldValue.reset();
+        aString.setValue(edge.getDestinationLabelName());
+        stringSerde.serialize(aString, fieldValue.getDataOutput());
+        subRecordBuilder.addField(GraphixMetadataRecordTypes.GRAPH_EDGES_ARECORD_DEST_LABEL_FIELD_INDEX, fieldValue);
+
+        // Write the source label name.
+        fieldValue.reset();
+        aString.setValue(edge.getSourceLabelName());
+        stringSerde.serialize(aString, fieldValue.getDataOutput());
+        subRecordBuilder.addField(GraphixMetadataRecordTypes.GRAPH_EDGES_ARECORD_SOURCE_LABEL_FIELD_INDEX, fieldValue);
+
+        // Write the primary key fields.
+        fieldValue.reset();
+        innerListBuilder.reset(stringListList);
+        for (List<String> keyField : edge.getPrimaryKeyFieldNames()) {
+            writeNameList(keyField, itemValue);
+            innerListBuilder.addItem(itemValue);
+        }
+        innerListBuilder.write(fieldValue.getDataOutput(), true);
+        subRecordBuilder.addField(GraphixMetadataRecordTypes.GRAPH_EDGES_ARECORD_PRIMARY_KEY_FIELD_INDEX, fieldValue);
+
+        // Write the destination key fields.
+        fieldValue.reset();
+        innerListBuilder.reset(stringListList);
+        for (List<String> keyField : edge.getDestinationKeyFieldNames()) {
+            writeNameList(keyField, itemValue);
+            innerListBuilder.addItem(itemValue);
+        }
+        innerListBuilder.write(fieldValue.getDataOutput(), true);
+        subRecordBuilder.addField(GraphixMetadataRecordTypes.GRAPH_EDGES_ARECORD_DEST_KEY_FIELD_INDEX, fieldValue);
+
+        // Write the source key fields.
+        fieldValue.reset();
+        innerListBuilder.reset(stringListList);
+        for (List<String> keyField : edge.getSourceKeyFieldNames()) {
+            writeNameList(keyField, itemValue);
+            innerListBuilder.addItem(itemValue);
+        }
+        innerListBuilder.write(fieldValue.getDataOutput(), true);
+        subRecordBuilder.addField(GraphixMetadataRecordTypes.GRAPH_EDGES_ARECORD_SOURCE_KEY_FIELD_INDEX, fieldValue);
+
+        // Write the edge definition(s).
+        fieldValue.reset();
+        innerListBuilder.reset(stringList);
+        for (String definition : edge.getDefinitions()) {
+            itemValue.reset();
+            aString.setValue(definition);
+            stringSerde.serialize(aString, itemValue.getDataOutput());
+            innerListBuilder.addItem(itemValue);
+        }
+        innerListBuilder.write(fieldValue.getDataOutput(), true);
+        subRecordBuilder.addField(GraphixMetadataRecordTypes.GRAPH_EDGES_ARECORD_DEFINITIONS_FIELD_INDEX, fieldValue);
+
+        itemValue.reset();
+        subRecordBuilder.write(itemValue.getDataOutput(), true);
+    }
+
+    private void writeNameList(List<String> name, ArrayBackedValueStorage itemValue) throws HyracksDataException {
+        nameListBuilder.reset(stringList);
+        for (String subName : name) {
+            itemValue.reset();
+            aString.setValue(subName);
+            stringSerde.serialize(aString, itemValue.getDataOutput());
+            nameListBuilder.addItem(itemValue);
+        }
+        itemValue.reset();
+        nameListBuilder.write(itemValue.getDataOutput(), true);
+    }
+}
diff --git a/asterix-graphix/src/main/resources/cc.conf b/asterix-graphix/src/main/resources/cc.conf
new file mode 100644
index 0000000..8452471
--- /dev/null
+++ b/asterix-graphix/src/main/resources/cc.conf
@@ -0,0 +1,68 @@
+; Licensed to the Apache Software Foundation (ASF) under one
+; or more contributor license agreements.  See the NOTICE file
+; distributed with this work for additional information
+; regarding copyright ownership.  The ASF licenses this file
+; to you under the Apache License, Version 2.0 (the
+; "License"); you may not use this file except in compliance
+; with the License.  You may obtain a copy of the License at
+;
+;   http://www.apache.org/licenses/LICENSE-2.0
+;
+; Unless required by applicable law or agreed to in writing,
+; software distributed under the License is distributed on an
+; "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+; KIND, either express or implied.  See the License for the
+; specific language governing permissions and limitations
+; under the License.
+
+[nc/asterix_nc1]
+txn.log.dir=target/tmp/asterix_nc1/txnlog
+core.dump.dir=target/tmp/asterix_nc1/coredump
+iodevices=target/tmp/asterix_nc1/iodevice1,../asterix-server/target/tmp/asterix_nc1/iodevice2
+#jvm.args=-agentlib:jdwp=transport=dt_socket,server=y,suspend=y,address=5006
+
+[nc/asterix_nc2]
+ncservice.port=9091
+nc.api.port=19005
+txn.log.dir=target/tmp/asterix_nc2/txnlog
+core.dump.dir=target/tmp/asterix_nc2/coredump
+iodevices=target/tmp/asterix_nc2/iodevice1,../asterix-server/target/tmp/asterix_nc2/iodevice2
+#jvm.args=-agentlib:jdwp=transport=dt_socket,server=y,suspend=y,address=5007
+
+[nc]
+address=127.0.0.1
+command=asterixnc
+app.class=org.apache.asterix.hyracks.bootstrap.NCApplication
+jvm.args=-Xmx4096m -Dnode.Resolver="org.apache.asterix.external.util.IdentitiyResolverFactory"
+storage.buffercache.pagesize=32KB
+storage.buffercache.size=128MB
+storage.memorycomponent.globalbudget=512MB
+storage.io.scheduler=greedy
+storage.filtered.memorycomponent.max.size=16MB
+
+[cc]
+address=127.0.0.1
+app.class=org.apache.asterix.hyracks.bootstrap.CCApplication
+heartbeat.period=2000
+heartbeat.max.misses=25
+
+[common]
+log.dir=logs/
+log.level=INFO
+compiler.framesize=32KB
+compiler.sortmemory=320KB
+compiler.groupmemory=160KB
+compiler.joinmemory=256KB
+compiler.textsearchmemory=160KB
+compiler.windowmemory=192KB
+compiler.sort.parallel=false
+compiler.internal.sanitycheck=true
+messaging.frame.size=4096
+messaging.frame.count=512
+
+[extension/org.apache.asterix.graphix.extension.GraphixQueryTranslatorExtension]
+enabled=true
+[extension/org.apache.asterix.graphix.extension.GraphixLangExtension]
+enabled=true
+[extension/org.apache.asterix.graphix.extension.GraphixMetadataExtension]
+enabled=true
\ No newline at end of file
diff --git a/asterix-graphix/src/main/resources/lang-extension/lang.txt b/asterix-graphix/src/main/resources/lang-extension/lang.txt
new file mode 100644
index 0000000..6d215f0
--- /dev/null
+++ b/asterix-graphix/src/main/resources/lang-extension/lang.txt
@@ -0,0 +1,354 @@
+//
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements.  See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership.  The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License.  You may obtain a copy of the License at
+//
+//   http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied.  See the License for the
+// specific language governing permissions and limitations
+// under the License.
+//
+
+import org.apache.asterix.graphix.common.metadata.GraphElementIdentifier;
+import org.apache.asterix.graphix.lang.expression.GraphConstructor;
+import org.apache.asterix.graphix.lang.statement.CreateGraphStatement;
+import org.apache.asterix.graphix.lang.statement.GraphDropStatement;
+import org.apache.asterix.graphix.lang.statement.GraphElementDecl;
+import org.apache.asterix.lang.sqlpp.parser.ParseException;
+import org.apache.asterix.lang.sqlpp.parser.SqlppParseException;
+import org.apache.asterix.lang.sqlpp.parser.Token;
+
+@new_at_the_class_def
+public GraphElementDecl parseGraphElementBody(GraphElementIdentifier identifier) throws CompilationException {
+    return parseImpl(new ParseFunction<GraphElementDecl>() {
+        @Override
+        public GraphElementDecl parse() throws ParseException {
+            DataverseName dataverse = defaultDataverse;
+            defaultDataverse = identifier.getGraphIdentifier().getDataverseName();
+
+            // We borrow the ViewBody production, where we have a SelectExpression or a VariableRef.
+            createNewScope();
+            Expression elementBodyExpr = GraphixParser.this.ViewBody();
+            removeCurrentScope();
+
+            defaultDataverse = dataverse;
+            return new GraphElementDecl(identifier, elementBodyExpr);
+        }
+    });
+}
+
+@merge
+Statement CreateStatement() throws ParseException:
+{
+  // merge area 1
+  before:
+  after:
+}
+{
+  (
+    // merge area 2
+    before:
+    after:    | stmt = CreateGraphStatement(startToken, false)
+  )
+  {
+    // merge area 3
+  }
+}
+
+@merge
+Statement CreateOrReplaceStatement(Token startStmtToken) throws ParseException:
+{
+  // merge area 1
+  before:
+  after:
+}
+{
+  (
+    // merge area 2
+    before:
+    after:    | stmt = CreateGraphStatement(startStmtToken, true)
+  )
+  {
+    // merge area 3
+  }
+}
+
+@merge
+Statement DropStatement() throws ParseException:
+{
+  // merge area 1
+  before:
+  after:
+}
+{
+  (
+    // merge area 2
+    before:
+    after:    | stmt = DropGraphStatement(startToken)
+  )
+  {
+    // merge area 3
+  }
+}
+
+@new
+CreateGraphStatement CreateGraphStatement(Token startStmtToken, boolean orReplace) throws ParseException:
+{
+  CreateGraphStatement stmt = null;
+}
+{
+  <GRAPH> stmt = CreateGraphSpecification(startStmtToken, orReplace)
+  {
+    return stmt;
+  }
+}
+
+@new
+CreateGraphStatement CreateGraphSpecification(Token startStmtToken, boolean orReplace) throws ParseException:
+{
+  Pair<DataverseName, Identifier> nameComponents = null;
+  GraphConstructor graphConstructor = null;
+  boolean ifNotExists = false;
+}
+{
+  nameComponents = QualifiedName()
+  ifNotExists = IfNotExists()
+  {
+    if (orReplace && ifNotExists) {
+      throw new SqlppParseException(getSourceLocation(startStmtToken), "Unexpected IF NOT EXISTS");
+    }
+  }
+  <AS> graphConstructor = GraphConstructor(token)
+  {
+    CreateGraphStatement stmt = new CreateGraphStatement(nameComponents.first, nameComponents.second.getValue(),
+        orReplace, ifNotExists, graphConstructor);
+    return addSourceLocation(stmt, startStmtToken);
+  }
+}
+
+@new
+GraphDropStatement DropGraphStatement(Token startStmtToken) throws ParseException:
+{
+   GraphDropStatement stmt = null;
+}
+{
+  <GRAPH> stmt = DropGraphSpecification(startStmtToken)
+  {
+    return stmt;
+  }
+}
+
+@new
+GraphDropStatement DropGraphSpecification(Token startStmtToken) throws ParseException:
+{
+  Pair<DataverseName, Identifier> pairId = null;
+  boolean ifExists = false;
+}
+{
+  pairId = QualifiedName() ifExists = IfExists()
+  {
+    GraphDropStatement stmt = new GraphDropStatement(pairId.first, pairId.second.getValue(), ifExists);
+    return addSourceLocation(stmt, startStmtToken);
+  }
+}
+
+@new
+Pair<List<Integer>, List<List<String>>> KeyFields() throws ParseException:
+{
+  Pair<List<Integer>, List<List<String>>> keyFields = null;
+}
+{
+  // This is essentially an alias for the production PrimaryKeyFields.
+  keyFields = PrimaryKeyFields()
+  {
+    return keyFields;
+  }
+}
+
+@new
+GraphConstructor GraphConstructor(Token startStmtToken) throws ParseException:
+{
+  List<GraphConstructor.VertexElement> vertexElements = new ArrayList<GraphConstructor.VertexElement>();
+  List<GraphConstructor.EdgeElement> edgeElements = new ArrayList<GraphConstructor.EdgeElement>();
+  GraphConstructor.VertexElement vertexElement = null;
+  GraphConstructor.EdgeElement edgeElement = null;
+}
+{
+  vertexElement = GraphVertexSpecification(startStmtToken) { vertexElements.add(vertexElement); }
+  ( <COMMA>
+    (
+      ( vertexElement = GraphVertexSpecification(token) { vertexElements.add(vertexElement); } )
+      | ( edgeElement = GraphEdgeSpecification(token) { edgeElements.add(edgeElement); } )
+    )
+  )*
+  {
+    GraphConstructor graphConstructor = new GraphConstructor(vertexElements, edgeElements);
+    return addSourceLocation(graphConstructor, startStmtToken);
+  }
+}
+
+@new
+GraphConstructor.VertexElement GraphVertexSpecification(Token startStmtToken) throws ParseException:
+{
+  Pair<List<Integer>, List<List<String>>> primaryKeyFields;
+  Token beginPos = null, endPos = null;
+  Expression vertexDefinitionExpr;
+  String vertexName;
+}
+{
+  <VERTEX>
+  vertexName = GraphVertexDefinitionPattern()
+  <PRIMARY> <KEY> <LEFTPAREN> primaryKeyFields = KeyFields() <RIGHTPAREN>
+  <AS>
+  {
+    beginPos = token;
+    createNewScope();
+  }
+  (
+    vertexDefinitionExpr = ViewBody()
+    | <LEFTPAREN> vertexDefinitionExpr = ViewBody() <RIGHTPAREN>
+  )
+  {
+    endPos = token;
+    String vDef = extractFragment(beginPos.beginLine, beginPos.beginColumn + 1, endPos.endLine, endPos.endColumn + 1);
+    removeCurrentScope();
+    GraphConstructor.VertexElement vertexElement = new GraphConstructor.VertexElement(vertexName,
+      primaryKeyFields.second, primaryKeyFields.first, vertexDefinitionExpr, vDef);
+    return addSourceLocation(vertexElement, startStmtToken);
+  }
+}
+
+@new
+String GraphVertexDefinitionPattern() throws ParseException:
+{
+  String vertexName;
+}
+{
+  <LEFTPAREN> <COLON> vertexName = Identifier() <RIGHTPAREN>
+  {
+    return vertexName;
+  }
+}
+
+@new
+GraphConstructor.EdgeElement GraphEdgeSpecification(Token startStmtToken) throws ParseException:
+{
+  Pair<Triple<String, String, String>, Boolean> edgeDefinitionPattern;
+  Pair<List<Integer>, List<List<String>>> keyFields;
+  Token beginPos = null, endPos = null;
+  Expression edgeDefinitionExpr = null;
+
+  List<Integer> destinationKeySourceIndicators = null;
+  List<Integer> sourceKeySourceIndicators = null;
+  List<Integer> primaryKeySourceIndicators = null;
+  List<List<String>> destinationKeyFields = null;
+  List<List<String>> sourceKeyFields = null;
+  List<List<String>> primaryKeyFields = null;
+}
+{
+  <EDGE>
+  edgeDefinitionPattern = GraphEdgeDefinitionPattern()
+  (
+    (
+      <PRIMARY> <KEY> <LEFTPAREN> keyFields = KeyFields() <RIGHTPAREN>
+      {
+        primaryKeyFields = keyFields.second;
+        primaryKeySourceIndicators = keyFields.first;
+      }
+      <SOURCE> <KEY> <LEFTPAREN> keyFields = KeyFields() <RIGHTPAREN>
+      {
+        sourceKeyFields = keyFields.second;
+        sourceKeySourceIndicators = keyFields.first;
+      }
+      <DESTINATION> <KEY> <LEFTPAREN> keyFields = KeyFields() <RIGHTPAREN>
+      {
+        destinationKeyFields = keyFields.second;
+        destinationKeySourceIndicators = keyFields.first;
+      }
+      <AS>
+      {
+        beginPos = token;
+        createNewScope();
+      }
+      (
+        edgeDefinitionExpr = ViewBody()
+        | <LEFTPAREN> edgeDefinitionExpr = ViewBody() <RIGHTPAREN>
+      )
+    )
+    |
+    (
+      <DESTINATION> <KEY> <LEFTPAREN> keyFields = KeyFields() <RIGHTPAREN>
+      {
+        destinationKeyFields = keyFields.second;
+        destinationKeySourceIndicators = keyFields.first;
+      }
+    )
+  )
+  {
+    String destinationLabel, edgeLabel, sourceLabel;
+    if (edgeDefinitionPattern.second) { // isDirectedLeft
+      sourceLabel = edgeDefinitionPattern.first.third;
+      edgeLabel = edgeDefinitionPattern.first.second;
+      destinationLabel = edgeDefinitionPattern.first.first;
+    } else {
+      sourceLabel = edgeDefinitionPattern.first.first;
+      edgeLabel = edgeDefinitionPattern.first.second;
+      destinationLabel = edgeDefinitionPattern.first.third;
+    }
+
+    String eDef = null;
+    if (edgeDefinitionExpr != null) {
+      endPos = token;
+      eDef = extractFragment(beginPos.beginLine, beginPos.beginColumn + 1, endPos.endLine, endPos.endColumn + 1);
+      removeCurrentScope();
+    }
+
+    GraphConstructor.EdgeElement edgeElement = new GraphConstructor.EdgeElement(edgeLabel, destinationLabel,
+        sourceLabel, primaryKeyFields, primaryKeySourceIndicators, destinationKeyFields, destinationKeySourceIndicators,
+        sourceKeyFields, sourceKeySourceIndicators, edgeDefinitionExpr, eDef);
+    return addSourceLocation(edgeElement, startStmtToken);
+  }
+}
+
+@new
+Pair<Triple<String, String, String>, Boolean> GraphEdgeDefinitionPattern() throws ParseException:
+{
+  String leftVertexName, edgeName, rightVertexName;
+  boolean isDirectedLeft;
+}
+{
+  leftVertexName = GraphVertexDefinitionPattern()
+  ( <MINUS> <LEFTBRACKET> <COLON> edgeName = Identifier() <RIGHTBRACKET> <MINUS> <GT> { isDirectedLeft = false; }
+  | <LT> <MINUS> <LEFTBRACKET> <COLON> edgeName = Identifier() <RIGHTBRACKET> <MINUS> { isDirectedLeft = true; } )
+  rightVertexName = GraphVertexDefinitionPattern()
+  {
+    Triple<String, String, String> t = new Triple<String, String, String>(leftVertexName, edgeName, rightVertexName);
+    return new Pair<Triple<String, String, String>, Boolean>(t, isDirectedLeft);
+  }
+}
+
+@new
+<DEFAULT,IN_DBL_BRACE>
+TOKEN [IGNORE_CASE]:
+{
+  <DESTINATION: "destination">
+  | <EDGE: "edge">
+  | <GRAPH: "graph">
+  | <SOURCE: "source">
+  | <VERTEX: "vertex">
+}
+
+@new_at_the_end
+<DEFAULT,IN_DBL_BRACE>
+TOKEN :
+{
+  <BAR: "|">
+}
\ No newline at end of file