diff --git a/service/Android.bp b/service/Android.bp
index 7327231..04f385e 100644
--- a/service/Android.bp
+++ b/service/Android.bp
@@ -20,6 +20,5 @@
         "framework-appsearch",
         "services.core",
     ],
-    static_libs: ["icing-java-proto-lite"],
     apex_available: ["com.android.appsearch"],
 }
diff --git a/service/java/com/android/server/appsearch/AppSearchManagerService.java b/service/java/com/android/server/appsearch/AppSearchManagerService.java
index 042f051..ce7e04c 100644
--- a/service/java/com/android/server/appsearch/AppSearchManagerService.java
+++ b/service/java/com/android/server/appsearch/AppSearchManagerService.java
@@ -17,9 +17,14 @@
 
 import android.app.appsearch.IAppSearchManager;
 import android.content.Context;
+import android.os.Binder;
+import android.os.UserHandle;
 
 import com.android.internal.infra.AndroidFuture;
+import com.android.internal.util.Preconditions;
 import com.android.server.SystemService;
+import com.android.server.appsearch.impl.AppSearchImpl;
+import com.android.server.appsearch.impl.ImplInstanceManager;
 
 import com.google.android.icing.proto.SchemaProto;
 
@@ -40,12 +45,20 @@
     private class Stub extends IAppSearchManager.Stub {
         @Override
         public void setSchema(byte[] schemaBytes, AndroidFuture callback) {
+            Preconditions.checkNotNull(schemaBytes);
+            Preconditions.checkNotNull(callback);
+            int callingUid = Binder.getCallingUidOrThrow();
+            int callingUserId = UserHandle.getUserId(callingUid);
+            long callingIdentity = Binder.clearCallingIdentity();
             try {
                 SchemaProto schema = SchemaProto.parseFrom(schemaBytes);
-                throw new UnsupportedOperationException("setSchema not yet implemented: " + schema);
-
+                AppSearchImpl impl = ImplInstanceManager.getInstance(getContext(), callingUserId);
+                impl.setSchema(callingUid, schema);
+                callback.complete(null);
             } catch (Throwable t) {
                 callback.completeExceptionally(t);
+            } finally {
+                Binder.restoreCallingIdentity(callingIdentity);
             }
         }
 
diff --git a/service/java/com/android/server/appsearch/impl/AppSearchImpl.java b/service/java/com/android/server/appsearch/impl/AppSearchImpl.java
new file mode 100644
index 0000000..7c97b0b
--- /dev/null
+++ b/service/java/com/android/server/appsearch/impl/AppSearchImpl.java
@@ -0,0 +1,110 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed 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 com.android.server.appsearch.impl;
+
+import android.annotation.NonNull;
+import android.annotation.UserIdInt;
+import android.content.Context;
+
+import com.android.internal.annotations.VisibleForTesting;
+
+import com.google.android.icing.proto.PropertyConfigProto;
+import com.google.android.icing.proto.SchemaProto;
+import com.google.android.icing.proto.SchemaTypeConfigProto;
+
+/**
+ * Manages interaction with {@link FakeIcing} and other components to implement AppSearch
+ * functionality.
+ */
+public final class AppSearchImpl {
+    private final Context mContext;
+    private final @UserIdInt int mUserId;
+    private final FakeIcing mFakeIcing = new FakeIcing();
+
+    AppSearchImpl(@NonNull Context context, @UserIdInt int userId) {
+        mContext = context;
+        mUserId = userId;
+    }
+
+    /**
+     * Updates the AppSearch schema for this app.
+     *
+     * @param callingUid The uid of the app calling AppSearch.
+     * @param origSchema The schema to set for this app.
+     */
+    public void setSchema(int callingUid, @NonNull SchemaProto origSchema) {
+        // Rewrite schema type names to include the calling app's package and uid.
+        String typePrefix = getTypePrefix(callingUid);
+        SchemaProto.Builder schemaBuilder = origSchema.toBuilder();
+        rewriteSchemaTypes(typePrefix, schemaBuilder);
+
+        // TODO(b/145635424): Save in schema type map
+        // TODO(b/145635424): Apply the schema to Icing and report results
+    }
+
+    /**
+     * Rewrites all types mentioned in the given {@code schemaBuilder} to prepend
+     * {@code typePrefix}.
+     *
+     * @param typePrefix The prefix to add
+     * @param schemaBuilder The schema to mutate
+     */
+    @VisibleForTesting
+    void rewriteSchemaTypes(
+            @NonNull String typePrefix, @NonNull SchemaProto.Builder schemaBuilder) {
+        for (int typeIdx = 0; typeIdx < schemaBuilder.getTypesCount(); typeIdx++) {
+            SchemaTypeConfigProto.Builder typeConfigBuilder =
+                    schemaBuilder.getTypes(typeIdx).toBuilder();
+
+            // Rewrite SchemaProto.types.schema_type
+            String newSchemaType = typePrefix + typeConfigBuilder.getSchemaType();
+            typeConfigBuilder.setSchemaType(newSchemaType);
+
+            // Rewrite SchemaProto.types.properties.schema_type
+            for (int propertyIdx = 0;
+                    propertyIdx < typeConfigBuilder.getPropertiesCount();
+                    propertyIdx++) {
+                PropertyConfigProto.Builder propertyConfigBuilder =
+                        typeConfigBuilder.getProperties(propertyIdx).toBuilder();
+                if (!propertyConfigBuilder.getSchemaType().isEmpty()) {
+                    String newPropertySchemaType =
+                            typePrefix + propertyConfigBuilder.getSchemaType();
+                    propertyConfigBuilder.setSchemaType(newPropertySchemaType);
+                    typeConfigBuilder.setProperties(propertyIdx, propertyConfigBuilder);
+                }
+            }
+
+            schemaBuilder.setTypes(typeIdx, typeConfigBuilder);
+        }
+    }
+
+    /**
+     * Returns a type prefix in a format like {@code com.example.package@1000/} or
+     * {@code com.example.sharedname:5678@1000/}.
+     */
+    @NonNull
+    private String getTypePrefix(int callingUid) {
+        // For regular apps, this call will return the package name. If callingUid is an
+        // android:sharedUserId, this value may be another type of name and have a :uid suffix.
+        String callingUidName = mContext.getPackageManager().getNameForUid(callingUid);
+        if (callingUidName == null) {
+            // Not sure how this is possible --- maybe app was uninstalled?
+            throw new IllegalStateException("Failed to look up package name for uid " + callingUid);
+        }
+        return callingUidName + "@" + mUserId + "/";
+    }
+}
diff --git a/service/java/com/android/server/appsearch/impl/ImplInstanceManager.java b/service/java/com/android/server/appsearch/impl/ImplInstanceManager.java
new file mode 100644
index 0000000..395e30e
--- /dev/null
+++ b/service/java/com/android/server/appsearch/impl/ImplInstanceManager.java
@@ -0,0 +1,56 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed 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 com.android.server.appsearch.impl;
+
+import android.annotation.NonNull;
+import android.annotation.UserIdInt;
+import android.content.Context;
+import android.util.SparseArray;
+
+/**
+ * Manages the lifecycle of instances of {@link AppSearchImpl}.
+ *
+ * <p>These instances are managed per unique device-user.
+ */
+public final class ImplInstanceManager {
+    private static final SparseArray<AppSearchImpl> sInstances = new SparseArray<>();
+
+    /**
+     * Gets an instance of AppSearchImpl for the given user.
+     *
+     * <p>If no AppSearchImpl instance exists for this user, Icing will be initialized and one will
+     * be created.
+     *
+     * @param context The Android context
+     * @param userId The multi-user userId of the device user calling AppSearch
+     * @return An initialized {@link AppSearchImpl} for this user
+     */
+    @NonNull
+    public static AppSearchImpl getInstance(@NonNull Context context, @UserIdInt int userId) {
+        AppSearchImpl instance = sInstances.get(userId);
+        if (instance == null) {
+            synchronized (ImplInstanceManager.class) {
+                instance = sInstances.get(userId);
+                if (instance == null) {
+                    instance = new AppSearchImpl(context, userId);
+                    sInstances.put(userId, instance);
+                }
+            }
+        }
+        return instance;
+    }
+}
diff --git a/testing/servicestests/src/com/android/server/appsearch/impl/AppSearchImplTest.java b/testing/servicestests/src/com/android/server/appsearch/impl/AppSearchImplTest.java
new file mode 100644
index 0000000..4195679
--- /dev/null
+++ b/testing/servicestests/src/com/android/server/appsearch/impl/AppSearchImplTest.java
@@ -0,0 +1,107 @@
+/*
+ * Copyright (C) 2019 The Android Open Source Project
+ *
+ * Licensed 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 com.android.server.appsearch.impl;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import static org.testng.Assert.expectThrows;
+
+import android.annotation.UserIdInt;
+import android.content.Context;
+import android.os.UserHandle;
+
+import androidx.test.InstrumentationRegistry;
+import androidx.test.runner.AndroidJUnit4;
+
+import com.google.android.icing.proto.IndexingConfig;
+import com.google.android.icing.proto.PropertyConfigProto;
+import com.google.android.icing.proto.SchemaProto;
+import com.google.android.icing.proto.SchemaTypeConfigProto;
+import com.google.android.icing.proto.TermMatchType;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+@RunWith(AndroidJUnit4.class)
+public class AppSearchImplTest {
+    private final Context mContext = InstrumentationRegistry.getContext();
+    private final @UserIdInt int mUserId = UserHandle.getCallingUserId();
+
+    @Test
+    public void testRewriteSchemaTypes() {
+        SchemaProto inSchema = SchemaProto.newBuilder()
+                .addTypes(SchemaTypeConfigProto.newBuilder()
+                        .setSchemaType("TestType")
+                        .addProperties(PropertyConfigProto.newBuilder()
+                                .setPropertyName("subject")
+                                .setDataType(PropertyConfigProto.DataType.Code.STRING)
+                                .setCardinality(PropertyConfigProto.Cardinality.Code.OPTIONAL)
+                                .setIndexingConfig(
+                                        IndexingConfig.newBuilder()
+                                                .setTokenizerType(
+                                                        IndexingConfig.TokenizerType.Code.PLAIN)
+                                                .setTermMatchType(TermMatchType.Code.PREFIX)
+                                                .build()
+                                ).build()
+                        ).addProperties(PropertyConfigProto.newBuilder()
+                                .setPropertyName("link")
+                                .setDataType(PropertyConfigProto.DataType.Code.DOCUMENT)
+                                .setCardinality(PropertyConfigProto.Cardinality.Code.OPTIONAL)
+                                .setSchemaType("RefType")
+                                .build()
+                        ).build()
+                ).build();
+
+        SchemaProto expectedSchema = SchemaProto.newBuilder()
+                .addTypes(SchemaTypeConfigProto.newBuilder()
+                        .setSchemaType("com.android.server.appsearch.impl@42:TestType")
+                        .addProperties(PropertyConfigProto.newBuilder()
+                                .setPropertyName("subject")
+                                .setDataType(PropertyConfigProto.DataType.Code.STRING)
+                                .setCardinality(PropertyConfigProto.Cardinality.Code.OPTIONAL)
+                                .setIndexingConfig(
+                                        IndexingConfig.newBuilder()
+                                                .setTokenizerType(
+                                                        IndexingConfig.TokenizerType.Code.PLAIN)
+                                                .setTermMatchType(TermMatchType.Code.PREFIX)
+                                                .build()
+                                ).build()
+                        ).addProperties(PropertyConfigProto.newBuilder()
+                                .setPropertyName("link")
+                                .setDataType(PropertyConfigProto.DataType.Code.DOCUMENT)
+                                .setCardinality(PropertyConfigProto.Cardinality.Code.OPTIONAL)
+                                .setSchemaType("com.android.server.appsearch.impl@42:RefType")
+                                .build()
+                        ).build()
+                ).build();
+
+        AppSearchImpl impl = new AppSearchImpl(mContext, mUserId);
+        SchemaProto.Builder actualSchema = inSchema.toBuilder();
+        impl.rewriteSchemaTypes("com.android.server.appsearch.impl@42:", actualSchema);
+
+        assertThat(actualSchema.build()).isEqualTo(expectedSchema);
+    }
+
+    @Test
+    public void testPackageNotFound() {
+        AppSearchImpl impl = new AppSearchImpl(mContext, mUserId);
+        IllegalStateException e = expectThrows(
+                IllegalStateException.class,
+                () -> impl.setSchema(
+                        /*callingUid=*/Integer.MAX_VALUE, SchemaProto.getDefaultInstance()));
+        assertThat(e).hasMessageThat().contains("Failed to look up package name");
+    }
+}