diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/struct/EdgeDescriptor.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/struct/EdgeDescriptor.java
index 2898a16..d5f88e4 100644
--- a/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/struct/EdgeDescriptor.java
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/struct/EdgeDescriptor.java
@@ -18,6 +18,7 @@
  */
 package org.apache.asterix.graphix.lang.struct;
 
+import java.io.Serializable;
 import java.util.List;
 import java.util.Objects;
 import java.util.Set;
@@ -36,7 +37,9 @@
  * 5. A maximum number of hops (not allowed to be NULL).
  * 6. An edge direction (left to right, right to left, or undirected).
  */
-public class EdgeDescriptor {
+public class EdgeDescriptor implements Serializable {
+    private static final long serialVersionUID = 1L;
+
     private final Set<ElementLabel> edgeLabels;
     private final Integer minimumHops;
     private final Integer maximumHops;
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/struct/ElementLabel.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/struct/ElementLabel.java
index 9add17a..a65afc6 100644
--- a/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/struct/ElementLabel.java
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/lang/struct/ElementLabel.java
@@ -18,9 +18,12 @@
  */
 package org.apache.asterix.graphix.lang.struct;
 
+import java.io.Serializable;
 import java.util.Objects;
 
-public class ElementLabel {
+public class ElementLabel implements Serializable {
+    private static final long serialVersionUID = 1L;
+
     private final String labelName;
     private boolean isInferred;
 
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/DependencyIdentifier.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/DependencyIdentifier.java
index 7c63de8..8a2ffe5 100644
--- a/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/DependencyIdentifier.java
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/DependencyIdentifier.java
@@ -18,6 +18,7 @@
  */
 package org.apache.asterix.graphix.metadata.entity.dependency;
 
+import java.io.Serializable;
 import java.util.Objects;
 
 import org.apache.asterix.common.functions.FunctionSignature;
@@ -30,7 +31,9 @@
  * A graph may depend on datasets, synonyms, functions, and other graphs. Similarly, functions and views may depend
  * on graphs themselves.
  */
-public class DependencyIdentifier {
+public class DependencyIdentifier implements Serializable {
+    private static final long serialVersionUID = 1L;
+
     private final DataverseName dataverseName;
     private final String entityName;
     private final String entityDetail;
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/FunctionRequirements.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/FunctionRequirements.java
index 5e73325..0b88f27 100644
--- a/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/FunctionRequirements.java
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/FunctionRequirements.java
@@ -18,6 +18,7 @@
  */
 package org.apache.asterix.graphix.metadata.entity.dependency;
 
+import java.io.IOException;
 import java.util.Iterator;
 import java.util.Objects;
 import java.util.Set;
@@ -25,7 +26,6 @@
 import org.apache.asterix.common.functions.FunctionSignature;
 import org.apache.asterix.common.metadata.DataverseName;
 import org.apache.asterix.om.base.AGeneratedUUID;
-import org.apache.asterix.om.base.AUUID;
 
 /**
  * A collection of {@link org.apache.asterix.graphix.metadata.entity.schema.Graph} dependencies associated with a
@@ -33,20 +33,27 @@
  * for functions.
  */
 public class FunctionRequirements implements IEntityRequirements {
+    private static final long serialVersionUID = 1L;
+
     private final Set<DependencyIdentifier> functionRequirements;
     private final FunctionSignature functionSignature;
 
-    // Physically, our requirements are indexed by a UUID. Logically, we ignore this.
-    private final AUUID primaryKeyValue;
+    // Physically, our requirements are indexed by the string below. Logically, we ignore this.
+    private final String primaryKeyValue;
 
-    public FunctionRequirements(FunctionSignature functionSignature, Set<DependencyIdentifier> functionRequirements) {
+    public FunctionRequirements(FunctionSignature functionSignature, Set<DependencyIdentifier> functionRequirements)
+            throws IOException {
         this.functionRequirements = Objects.requireNonNull(functionRequirements);
         this.functionSignature = Objects.requireNonNull(functionSignature);
-        this.primaryKeyValue = new AGeneratedUUID();
+
+        // Generate a unique primary key from a AUUID.
+        StringBuilder sb = new StringBuilder();
+        new AGeneratedUUID().appendLiteralOnly(sb);
+        this.primaryKeyValue = sb.toString();
     }
 
     public FunctionRequirements(FunctionSignature functionSignature, Set<DependencyIdentifier> functionRequirements,
-            AUUID primaryKeyValue) {
+            String primaryKeyValue) {
         this.functionRequirements = Objects.requireNonNull(functionRequirements);
         this.functionSignature = Objects.requireNonNull(functionSignature);
         this.primaryKeyValue = Objects.requireNonNull(primaryKeyValue);
@@ -57,7 +64,7 @@
     }
 
     @Override
-    public AUUID getPrimaryKeyValue() {
+    public String getPrimaryKeyValue() {
         return primaryKeyValue;
     }
 
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/GraphRequirements.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/GraphRequirements.java
index 98c669a..ef4dab2 100644
--- a/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/GraphRequirements.java
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/GraphRequirements.java
@@ -18,6 +18,7 @@
  */
 package org.apache.asterix.graphix.metadata.entity.dependency;
 
+import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.HashSet;
@@ -33,7 +34,6 @@
 import org.apache.asterix.lang.common.util.ExpressionUtils;
 import org.apache.asterix.metadata.utils.MetadataUtil;
 import org.apache.asterix.om.base.AGeneratedUUID;
-import org.apache.asterix.om.base.AUUID;
 import org.apache.hyracks.algebricks.common.utils.Triple;
 
 /**
@@ -41,29 +41,35 @@
  * {@link org.apache.asterix.graphix.metadata.entity.schema.Graph} instance.
  */
 public class GraphRequirements implements IEntityRequirements {
+    private static final long serialVersionUID = 1L;
+
     // A graph potentially depends on datasets, synonyms, functions, and graphs.
     private final Set<DependencyIdentifier> graphRequirements;
     private final DataverseName dataverseName;
     private final String graphName;
 
-    // Physically, our requirements are indexed by a UUID. Logically, we ignore this.
-    private AUUID primaryKeyValue;
+    // Physically, our requirements are indexed by the string below. Logically, we ignore this.
+    private String primaryKeyValue;
+
+    public GraphRequirements(DataverseName dataverseName, String graphName) throws IOException {
+        this.graphRequirements = new HashSet<>();
+        this.dataverseName = Objects.requireNonNull(dataverseName);
+        this.graphName = Objects.requireNonNull(graphName);
+
+        // Generate a unique primary key from a AUUID.
+        StringBuilder sb = new StringBuilder();
+        new AGeneratedUUID().appendLiteralOnly(sb);
+        this.primaryKeyValue = sb.toString();
+    }
 
     public GraphRequirements(DataverseName dataverseName, String graphName, Set<DependencyIdentifier> graphRequirements,
-            AUUID primaryKeyValue) {
+            String primaryKeyValue) {
         this.graphRequirements = Objects.requireNonNull(graphRequirements);
         this.dataverseName = Objects.requireNonNull(dataverseName);
         this.graphName = Objects.requireNonNull(graphName);
         this.primaryKeyValue = Objects.requireNonNull(primaryKeyValue);
     }
 
-    public GraphRequirements(DataverseName dataverseName, String graphName) {
-        this.graphRequirements = new HashSet<>();
-        this.dataverseName = Objects.requireNonNull(dataverseName);
-        this.graphName = Objects.requireNonNull(graphName);
-        this.primaryKeyValue = new AGeneratedUUID();
-    }
-
     public void loadNonGraphDependencies(Expression body, IQueryRewriter queryRewriter) throws CompilationException {
         // Collect our dependencies as triples.
         List<Triple<DataverseName, String, String>> datasetDependencies = new ArrayList<>();
@@ -88,12 +94,12 @@
         graphRequirements.addAll(graphDependencies);
     }
 
-    public void setPrimaryKeyValue(AUUID primaryKeyValue) {
+    public void setPrimaryKeyValue(String primaryKeyValue) {
         this.primaryKeyValue = primaryKeyValue;
     }
 
     @Override
-    public AUUID getPrimaryKeyValue() {
+    public String getPrimaryKeyValue() {
         return primaryKeyValue;
     }
 
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/IEntityRequirements.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/IEntityRequirements.java
index 371d4e3..c0e111c 100644
--- a/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/IEntityRequirements.java
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/IEntityRequirements.java
@@ -18,11 +18,12 @@
  */
 package org.apache.asterix.graphix.metadata.entity.dependency;
 
+import java.io.Serializable;
+
 import org.apache.asterix.common.metadata.DataverseName;
 import org.apache.asterix.graphix.metadata.bootstrap.GraphixIndexDetailProvider;
 import org.apache.asterix.metadata.api.ExtensionMetadataDatasetId;
 import org.apache.asterix.metadata.api.IExtensionMetadataEntity;
-import org.apache.asterix.om.base.AUUID;
 
 /**
  * Metadata for describing the pair [entity, list of dependencies for said entity]. This includes the following:
@@ -32,8 +33,8 @@
  * 4. The kind associated with the entity (FUNCTION, GRAPH, or VIEW).
  * 5. An iterator of the dependencies associated with the entity.
  */
-public interface IEntityRequirements extends Iterable<DependencyIdentifier>, IExtensionMetadataEntity {
-    AUUID getPrimaryKeyValue();
+public interface IEntityRequirements extends Iterable<DependencyIdentifier>, IExtensionMetadataEntity, Serializable {
+    String getPrimaryKeyValue();
 
     DataverseName getDataverseName();
 
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/ViewRequirements.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/ViewRequirements.java
index 2e529a6..6c84eab 100644
--- a/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/ViewRequirements.java
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entity/dependency/ViewRequirements.java
@@ -18,6 +18,7 @@
  */
 package org.apache.asterix.graphix.metadata.entity.dependency;
 
+import java.io.IOException;
 import java.util.Iterator;
 import java.util.Objects;
 import java.util.Set;
@@ -25,29 +26,35 @@
 import org.apache.asterix.common.metadata.DataverseName;
 import org.apache.asterix.metadata.utils.DatasetUtil;
 import org.apache.asterix.om.base.AGeneratedUUID;
-import org.apache.asterix.om.base.AUUID;
 
 /**
  * A collection of {@link org.apache.asterix.graphix.metadata.entity.schema.Graph} dependencies associated with a view
  * instance. This does **not** include non-graph dependencies for views.
  */
 public class ViewRequirements implements IEntityRequirements {
+    private static final long serialVersionUID = 1L;
+
     private final Set<DependencyIdentifier> viewRequirements;
     private final DataverseName dataverseName;
     private final String viewName;
 
-    // Physically, our requirements are indexed by a UUID. Logically, we ignore this.
-    private final AUUID primaryKeyValue;
+    // Physically, our requirements are indexed by the string below. Logically, we ignore this.
+    private final String primaryKeyValue;
 
-    public ViewRequirements(DataverseName dataverseName, String viewName, Set<DependencyIdentifier> viewRequirements) {
+    public ViewRequirements(DataverseName dataverseName, String viewName, Set<DependencyIdentifier> viewRequirements)
+            throws IOException {
         this.viewRequirements = Objects.requireNonNull(viewRequirements);
         this.dataverseName = Objects.requireNonNull(dataverseName);
         this.viewName = Objects.requireNonNull(viewName);
-        this.primaryKeyValue = new AGeneratedUUID();
+
+        // Generate a unique primary key from a AUUID.
+        StringBuilder sb = new StringBuilder();
+        new AGeneratedUUID().appendLiteralOnly(sb);
+        this.primaryKeyValue = sb.toString();
     }
 
     public ViewRequirements(DataverseName dataverseName, String viewName, Set<DependencyIdentifier> viewRequirements,
-            AUUID primaryKeyValue) {
+            String primaryKeyValue) {
         this.viewRequirements = Objects.requireNonNull(viewRequirements);
         this.dataverseName = Objects.requireNonNull(dataverseName);
         this.viewName = Objects.requireNonNull(viewName);
@@ -55,7 +62,7 @@
     }
 
     @Override
-    public AUUID getPrimaryKeyValue() {
+    public String getPrimaryKeyValue() {
         return primaryKeyValue;
     }
 
diff --git a/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entitytupletranslators/DependencyTupleTranslator.java b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entitytupletranslators/DependencyTupleTranslator.java
index 77c1637..b59f661 100644
--- a/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entitytupletranslators/DependencyTupleTranslator.java
+++ b/asterix-graphix/src/main/java/org/apache/asterix/graphix/metadata/entitytupletranslators/DependencyTupleTranslator.java
@@ -25,7 +25,6 @@
 import static org.apache.asterix.metadata.bootstrap.MetadataRecordTypes.FIELD_NAME_DEPENDENCIES;
 import static org.apache.asterix.metadata.bootstrap.MetadataRecordTypes.FIELD_NAME_KIND;
 
-import java.io.IOException;
 import java.util.HashSet;
 import java.util.Set;
 
@@ -43,17 +42,14 @@
 import org.apache.asterix.graphix.metadata.entity.dependency.IEntityRequirements;
 import org.apache.asterix.graphix.metadata.entity.dependency.ViewRequirements;
 import org.apache.asterix.metadata.entitytupletranslators.AbstractTupleTranslator;
-import org.apache.asterix.om.base.AMutableUUID;
 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.AUUID;
 import org.apache.asterix.om.base.IACursor;
 import org.apache.asterix.om.base.IAObject;
 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.api.exceptions.ErrorCode;
 import org.apache.hyracks.api.exceptions.HyracksDataException;
 import org.apache.hyracks.dataflow.common.data.accessors.ITupleReference;
 
@@ -88,14 +84,7 @@
     protected IEntityRequirements createMetadataEntityFromARecord(ARecord requirements) throws AlgebricksException {
         // Read in our primary key value.
         IAObject primaryKeyValueObj = GRA_RECORD_DETAIL.getObjectForField(requirements, FIELD_NAME_DEPENDENCY_ID);
-        String primaryKeyValueString = ((AString) primaryKeyValueObj).getStringValue();
-        AMutableUUID primaryKeyValue = new AMutableUUID();
-        try {
-            primaryKeyValue.parseUUIDString(primaryKeyValueString.toCharArray(), 0, AUUID.UUID_CHARS);
-
-        } catch (HyracksDataException e) {
-            throw new AlgebricksException(ErrorCode.ILLEGAL_STATE, "Could not extract UUID bytes from ARecord.");
-        }
+        String primaryKeyValue = ((AString) primaryKeyValueObj).getStringValue();
 
         // Read in the dataverse name.
         IAObject dataverseNameObj = GRA_RECORD_DETAIL.getObjectForField(requirements, FIELD_NAME_DATAVERSE_NAME);
@@ -191,20 +180,9 @@
 
     @Override
     public ITupleReference getTupleFromMetadataEntity(IEntityRequirements requirements) throws HyracksDataException {
-        // TODO (GLENN): There is currently a bug where a metadata dataset index cannot have a UUID primary key field.
-        String primaryKeyValue;
-        try {
-            StringBuilder sb = new StringBuilder();
-            requirements.getPrimaryKeyValue().appendLiteralOnly(sb);
-            primaryKeyValue = sb.toString();
-
-        } catch (IOException e) {
-            throw new HyracksDataException(ErrorCode.ILLEGAL_STATE, "Could not extract UUID bytes from AUUID.");
-        }
-
-        // Write our primary key, which is an autogenerated UUID (we serialize this as a string for our tuple).
+        // Write our primary key.
         tupleBuilder.reset();
-        aString.setValue(primaryKeyValue);
+        aString.setValue(requirements.getPrimaryKeyValue());
         stringSerde.serialize(aString, tupleBuilder.getDataOutput());
         tupleBuilder.addFieldEndOffset();
 
@@ -213,7 +191,7 @@
 
         // Write our primary key.
         fieldValue.reset();
-        aString.setValue(primaryKeyValue);
+        aString.setValue(requirements.getPrimaryKeyValue());
         stringSerde.serialize(aString, fieldValue.getDataOutput());
         recordBuilder.addField(GRA_RECORD_DETAIL.getIndexForField(FIELD_NAME_DEPENDENCY_ID), fieldValue);