diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/ActionGraphDump.java b/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/ActionGraphDump.java
index 03eada4..da21422 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/ActionGraphDump.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/ActionGraphDump.java
@@ -40,6 +40,7 @@
 import com.google.devtools.build.lib.rules.AliasConfiguredTarget;
 import com.google.devtools.build.lib.skyframe.AspectValue;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetValue;
+import com.google.devtools.build.lib.util.Pair;
 import java.util.HashMap;
 import java.util.List;
 import java.util.Map;
@@ -60,7 +61,7 @@
   private final KnownConfigurations knownConfigurations;
   private final KnownNestedSets knownNestedSets;
   private final KnownAspectDescriptors knownAspectDescriptors;
-  private final KnownRuleConfiguredTargets knownRuleConfiguredTargets;
+  private final KnownTargets knownTargets;
   private final AqueryActionFilter actionFilters;
   private final boolean includeActionCmdLine;
   private final boolean includeArtifacts;
@@ -108,8 +109,7 @@
     knownConfigurations = new KnownConfigurations(actionGraphBuilder);
     knownNestedSets = new KnownNestedSets(actionGraphBuilder, knownArtifacts);
     knownAspectDescriptors = new KnownAspectDescriptors(actionGraphBuilder);
-    knownRuleConfiguredTargets = new KnownRuleConfiguredTargets(actionGraphBuilder,
-        knownRuleClassStrings);
+    knownTargets = new KnownTargets(actionGraphBuilder, knownRuleClassStrings);
   }
 
   public ActionKeyContext getActionKeyContext() {
@@ -145,11 +145,14 @@
     }
 
     Preconditions.checkState(configuredTarget instanceof RuleConfiguredTarget);
-    RuleConfiguredTarget ruleConfiguredTarget = (RuleConfiguredTarget) configuredTarget;
+    Pair<String, String> targetIdentifier =
+        new Pair<>(
+            configuredTarget.getLabel().toString(),
+            ((RuleConfiguredTarget) configuredTarget).getRuleClassString());
     AnalysisProtos.Action.Builder actionBuilder =
         AnalysisProtos.Action.newBuilder()
             .setMnemonic(action.getMnemonic())
-            .setTargetId(knownRuleConfiguredTargets.dataToId(ruleConfiguredTarget));
+            .setTargetId(knownTargets.dataToId(targetIdentifier));
 
     if (action instanceof ActionExecutionMetadata) {
       ActionExecutionMetadata actionExecutionMetadata = (ActionExecutionMetadata) action;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/KnownRuleConfiguredTargets.java b/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/KnownTargets.java
similarity index 69%
rename from src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/KnownRuleConfiguredTargets.java
rename to src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/KnownTargets.java
index 12005f5..ccce75e 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/KnownRuleConfiguredTargets.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/KnownTargets.java
@@ -15,18 +15,19 @@
 
 import com.google.devtools.build.lib.analysis.AnalysisProtos;
 import com.google.devtools.build.lib.analysis.AnalysisProtos.ActionGraphContainer;
-import com.google.devtools.build.lib.analysis.configuredtargets.RuleConfiguredTarget;
-import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.util.Pair;
 
 /**
  * Cache for RuleConfiguredTargets in the action graph.
+ *
+ * <p>The cache maps a target identifier, which is a {@code Pair<String, String>} of
+ * (label, rule class string).
  */
-public class KnownRuleConfiguredTargets
-    extends BaseCache<RuleConfiguredTarget, AnalysisProtos.Target> {
+public class KnownTargets extends BaseCache<Pair<String, String>, AnalysisProtos.Target> {
 
   private final KnownRuleClassStrings knownRuleClassStrings;
 
-  KnownRuleConfiguredTargets(
+  KnownTargets(
       ActionGraphContainer.Builder actionGraphBuilder,
       KnownRuleClassStrings knownRuleClassStrings) {
     super(actionGraphBuilder);
@@ -34,12 +35,11 @@
   }
 
   @Override
-  AnalysisProtos.Target createProto(RuleConfiguredTarget ruleConfiguredTarget, String id) {
-    Label label = ruleConfiguredTarget.getLabel();
-    String ruleClassString = ruleConfiguredTarget.getRuleClassString();
-    AnalysisProtos.Target.Builder targetBuilder = AnalysisProtos.Target.newBuilder()
-        .setId(id)
-        .setLabel(label.toString());
+  AnalysisProtos.Target createProto(Pair<String, String> targetIdentifier, String id) {
+    String labelString = targetIdentifier.getFirst();
+    String ruleClassString = targetIdentifier.getSecond();
+    AnalysisProtos.Target.Builder targetBuilder =
+        AnalysisProtos.Target.newBuilder().setId(id).setLabel(labelString);
     if (ruleClassString != null) {
       targetBuilder.setRuleClassId(knownRuleClassStrings.dataToId(ruleClassString));
     }
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2/ActionGraphDump.java b/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2/ActionGraphDump.java
index 0301bf6..a787f89 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2/ActionGraphDump.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2/ActionGraphDump.java
@@ -39,6 +39,7 @@
 import com.google.devtools.build.lib.rules.AliasConfiguredTarget;
 import com.google.devtools.build.lib.skyframe.AspectValue;
 import com.google.devtools.build.lib.skyframe.ConfiguredTargetValue;
+import com.google.devtools.build.lib.util.Pair;
 import java.io.IOException;
 import java.util.HashMap;
 import java.util.List;
@@ -59,7 +60,7 @@
   private final KnownConfigurations knownConfigurations;
   private final KnownNestedSets knownNestedSets;
   private final KnownAspectDescriptors knownAspectDescriptors;
-  private final KnownRuleConfiguredTargets knownRuleConfiguredTargets;
+  private final KnownTargets knownTargets;
   private final AqueryActionFilter actionFilters;
   private final boolean includeActionCmdLine;
   private final boolean includeArtifacts;
@@ -102,8 +103,7 @@
     knownConfigurations = new KnownConfigurations(aqueryOutputHandler);
     knownNestedSets = new KnownNestedSets(aqueryOutputHandler, knownArtifacts);
     knownAspectDescriptors = new KnownAspectDescriptors(aqueryOutputHandler);
-    knownRuleConfiguredTargets =
-        new KnownRuleConfiguredTargets(aqueryOutputHandler, knownRuleClassStrings);
+    knownTargets = new KnownTargets(aqueryOutputHandler, knownRuleClassStrings);
   }
 
   public ActionKeyContext getActionKeyContext() {
@@ -139,12 +139,14 @@
     }
 
     Preconditions.checkState(configuredTarget instanceof RuleConfiguredTarget);
-    RuleConfiguredTarget ruleConfiguredTarget = (RuleConfiguredTarget) configuredTarget;
+    Pair<String, String> targetIdentifier =
+        new Pair<>(
+            configuredTarget.getLabel().toString(),
+            ((RuleConfiguredTarget) configuredTarget).getRuleClassString());
     AnalysisProtosV2.Action.Builder actionBuilder =
         AnalysisProtosV2.Action.newBuilder()
             .setMnemonic(action.getMnemonic())
-            .setTargetId(
-                knownRuleConfiguredTargets.dataToIdAndStreamOutputProto(ruleConfiguredTarget));
+            .setTargetId(knownTargets.dataToIdAndStreamOutputProto(targetIdentifier));
 
     if (action instanceof ActionExecutionMetadata) {
       ActionExecutionMetadata actionExecutionMetadata = (ActionExecutionMetadata) action;
diff --git a/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2/KnownRuleConfiguredTargets.java b/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2/KnownTargets.java
similarity index 71%
rename from src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2/KnownRuleConfiguredTargets.java
rename to src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2/KnownTargets.java
index 14675c2..a434e59 100644
--- a/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2/KnownRuleConfiguredTargets.java
+++ b/src/main/java/com/google/devtools/build/lib/skyframe/actiongraph/v2/KnownTargets.java
@@ -14,26 +14,30 @@
 package com.google.devtools.build.lib.skyframe.actiongraph.v2;
 
 import com.google.devtools.build.lib.analysis.AnalysisProtosV2.Target;
-import com.google.devtools.build.lib.analysis.configuredtargets.RuleConfiguredTarget;
-import com.google.devtools.build.lib.cmdline.Label;
+import com.google.devtools.build.lib.util.Pair;
 import java.io.IOException;
 
-/** Cache for RuleConfiguredTargets in the action graph. */
-public class KnownRuleConfiguredTargets extends BaseCache<RuleConfiguredTarget, Target> {
+/**
+ * Cache for RuleConfiguredTargets in the action graph.
+ *
+ * <p>The cache maps a target identifier, which is a {@code Pair<String, String>} of
+ * (label, rule class string).
+ * */
+public class KnownTargets extends BaseCache<Pair<String, String>, Target> {
 
   private final KnownRuleClassStrings knownRuleClassStrings;
 
-  KnownRuleConfiguredTargets(
+  KnownTargets(
       AqueryOutputHandler aqueryOutputHandler, KnownRuleClassStrings knownRuleClassStrings) {
     super(aqueryOutputHandler);
     this.knownRuleClassStrings = knownRuleClassStrings;
   }
 
   @Override
-  Target createProto(RuleConfiguredTarget ruleConfiguredTarget, int id) throws IOException {
-    Label label = ruleConfiguredTarget.getLabel();
-    String ruleClassString = ruleConfiguredTarget.getRuleClassString();
-    Target.Builder targetBuilder = Target.newBuilder().setId(id).setLabel(label.toString());
+  Target createProto(Pair<String, String> targetIdentifier, int id) throws IOException {
+    String labelString = targetIdentifier.getFirst();
+    String ruleClassString = targetIdentifier.getSecond();
+    Target.Builder targetBuilder = Target.newBuilder().setId(id).setLabel(labelString);
     if (ruleClassString != null) {
       targetBuilder.setRuleClassId(
           knownRuleClassStrings.dataToIdAndStreamOutputProto(ruleClassString));