Sync platform from Jetpack.

Included changes:
* caf5d9: Add a uri prefix to visibility store documents.
* 5b26a8: Minor comment fix in AppSearchSession
* 31b691: Add package visibility APIs for schema types.
* d36a2c: Require a package name in AppSearchImpl.

Bug: 169883602
Bug: 162450968
Test: Presubmit
Change-Id: I155145e4b14a271f3012cb7b5efbbe1b7ba27a18
diff --git a/framework/java/external/android/app/appsearch/PackageIdentifier.java b/framework/java/external/android/app/appsearch/PackageIdentifier.java
new file mode 100644
index 0000000..b567dee
--- /dev/null
+++ b/framework/java/external/android/app/appsearch/PackageIdentifier.java
@@ -0,0 +1,61 @@
+/*
+ * Copyright 2020 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 android.app.appsearch;
+
+import android.annotation.NonNull;
+
+import java.util.Arrays;
+import java.util.Objects;
+
+/**
+ * This class represents a uniquely identifiable package.
+ *
+ * @hide
+ */
+public class PackageIdentifier {
+    public final String packageName;
+    public final byte[] certificate;
+
+    /**
+     * Creates a unique identifier for a package.
+     *
+     * @param packageName Name of the package.
+     * @param certificate SHA256 certificate digest of the package.
+     */
+    public PackageIdentifier(@NonNull String packageName, @NonNull byte[] certificate) {
+        this.packageName = packageName;
+        this.certificate = certificate;
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj) {
+            return true;
+        }
+        if (obj == null || !(obj instanceof PackageIdentifier)) {
+            return false;
+        }
+        final PackageIdentifier other = (PackageIdentifier) obj;
+        return this.packageName.equals(other.packageName)
+                && Arrays.equals(this.certificate, other.certificate);
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(packageName, Arrays.hashCode(certificate));
+    }
+}
diff --git a/framework/java/external/android/app/appsearch/RemoveByUriRequest.java b/framework/java/external/android/app/appsearch/RemoveByUriRequest.java
index be6d157..a04da34 100644
--- a/framework/java/external/android/app/appsearch/RemoveByUriRequest.java
+++ b/framework/java/external/android/app/appsearch/RemoveByUriRequest.java
@@ -46,7 +46,7 @@
         return mNamespace;
     }
 
-    /** Returns the URIs to remove from the namespace. */
+    /** Returns the URIs of documents to remove from the namespace. */
     @NonNull
     public Set<String> getUris() {
         return Collections.unmodifiableSet(mUris);
diff --git a/framework/java/external/android/app/appsearch/SetSchemaRequest.java b/framework/java/external/android/app/appsearch/SetSchemaRequest.java
index 0e03131..4ef30c3 100644
--- a/framework/java/external/android/app/appsearch/SetSchemaRequest.java
+++ b/framework/java/external/android/app/appsearch/SetSchemaRequest.java
@@ -19,6 +19,7 @@
 import android.annotation.NonNull;
 import android.annotation.SuppressLint;
 import android.app.appsearch.exceptions.AppSearchException;
+import android.util.ArrayMap;
 import android.util.ArraySet;
 
 import com.android.internal.util.Preconditions;
@@ -28,6 +29,7 @@
 import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
+import java.util.Map;
 import java.util.Set;
 
 /**
@@ -38,14 +40,17 @@
 public final class SetSchemaRequest {
     private final Set<AppSearchSchema> mSchemas;
     private final Set<String> mSchemasNotPlatformSurfaceable;
+    private final Map<String, Set<PackageIdentifier>> mSchemasPackageAccessible;
     private final boolean mForceOverride;
 
     SetSchemaRequest(
             @NonNull Set<AppSearchSchema> schemas,
             @NonNull Set<String> schemasNotPlatformSurfaceable,
+            @NonNull Map<String, Set<PackageIdentifier>> schemasPackageAccessible,
             boolean forceOverride) {
         mSchemas = Preconditions.checkNotNull(schemas);
         mSchemasNotPlatformSurfaceable = Preconditions.checkNotNull(schemasNotPlatformSurfaceable);
+        mSchemasPackageAccessible = Preconditions.checkNotNull(schemasPackageAccessible);
         mForceOverride = forceOverride;
     }
 
@@ -65,6 +70,39 @@
         return Collections.unmodifiableSet(mSchemasNotPlatformSurfaceable);
     }
 
+    /**
+     * Returns a mapping of schema types to the set of packages that have access to that schema
+     * type. Each package is represented by a {@link PackageIdentifier}. name and byte[]
+     * certificate.
+     *
+     * <p>This method is inefficient to call repeatedly.
+     *
+     * @hide
+     */
+    @NonNull
+    public Map<String, Set<PackageIdentifier>> getSchemasPackageAccessible() {
+        Map<String, Set<PackageIdentifier>> copy = new ArrayMap<>();
+        for (String key : mSchemasPackageAccessible.keySet()) {
+            copy.put(key, new ArraySet<>(mSchemasPackageAccessible.get(key)));
+        }
+        return copy;
+    }
+
+    /**
+     * Returns a mapping of schema types to the set of packages that have access to that schema
+     * type. Each package is represented by a {@link PackageIdentifier}. name and byte[]
+     * certificate.
+     *
+     * <p>A more efficient version of {@code #getSchemasPackageAccessible}, but it returns a
+     * modifiable map. This is not meant to be unhidden and should only be used by internal classes.
+     *
+     * @hide
+     */
+    @NonNull
+    public Map<String, Set<PackageIdentifier>> getSchemasPackageAccessibleInternal() {
+        return mSchemasPackageAccessible;
+    }
+
     /** Returns whether this request will force the schema to be overridden. */
     public boolean isForceOverride() {
         return mForceOverride;
@@ -74,6 +112,8 @@
     public static final class Builder {
         private final Set<AppSearchSchema> mSchemas = new ArraySet<>();
         private final Set<String> mSchemasNotPlatformSurfaceable = new ArraySet<>();
+        private final Map<String, Set<PackageIdentifier>> mSchemasPackageAccessible =
+                new ArrayMap<>();
         private boolean mForceOverride = false;
         private boolean mBuilt = false;
 
@@ -102,32 +142,62 @@
         }
 
         /**
-         * Sets visibility on system UI surfaces for schema types.
+         * Sets visibility on system UI surfaces for the given {@code schemaType}.
          *
+         * @param schemaType The schema type to set visibility on.
+         * @param visible Whether the {@code schemaType} will be visible or not.
          * @hide
          */
         @NonNull
         public Builder setSchemaTypeVisibilityForSystemUi(
-                boolean visible, @NonNull String... schemaTypes) {
-            Preconditions.checkNotNull(schemaTypes);
-            return this.setSchemaTypeVisibilityForSystemUi(visible, Arrays.asList(schemaTypes));
+                @NonNull String schemaType, boolean visible) {
+            Preconditions.checkNotNull(schemaType);
+            Preconditions.checkState(!mBuilt, "Builder has already been used");
+
+            if (visible) {
+                mSchemasNotPlatformSurfaceable.remove(schemaType);
+            } else {
+                mSchemasNotPlatformSurfaceable.add(schemaType);
+            }
+            return this;
         }
 
         /**
-         * Sets visibility on system UI surfaces for schema types.
+         * Sets visibility for a package for the given {@code schemaType}.
          *
+         * @param schemaType The schema type to set visibility on.
+         * @param visible Whether the {@code schemaType} will be visible or not.
+         * @param packageIdentifier Represents the package that will be granted visibility.
          * @hide
          */
         @NonNull
-        public Builder setSchemaTypeVisibilityForSystemUi(
-                boolean visible, @NonNull Collection<String> schemaTypes) {
+        public Builder setSchemaTypeVisibilityForPackage(
+                @NonNull String schemaType,
+                boolean visible,
+                @NonNull PackageIdentifier packageIdentifier) {
+            Preconditions.checkNotNull(schemaType);
+            Preconditions.checkNotNull(packageIdentifier);
             Preconditions.checkState(!mBuilt, "Builder has already been used");
-            Preconditions.checkNotNull(schemaTypes);
+
+            Set<PackageIdentifier> packageIdentifiers = mSchemasPackageAccessible.get(schemaType);
             if (visible) {
-                mSchemasNotPlatformSurfaceable.removeAll(schemaTypes);
+                if (packageIdentifiers == null) {
+                    packageIdentifiers = new ArraySet<>();
+                }
+                packageIdentifiers.add(packageIdentifier);
+                mSchemasPackageAccessible.put(schemaType, packageIdentifiers);
             } else {
-                mSchemasNotPlatformSurfaceable.addAll(schemaTypes);
+                if (packageIdentifiers == null) {
+                    // Return early since there was nothing set to begin with.
+                    return this;
+                }
+                packageIdentifiers.remove(packageIdentifier);
+                if (packageIdentifiers.isEmpty()) {
+                    // Remove the entire key so that we don't have empty sets as values.
+                    mSchemasPackageAccessible.remove(schemaType);
+                }
             }
+
             return this;
         }
 
@@ -159,21 +229,24 @@
 
             // Verify that any schema types with visibility settings refer to a real schema.
             // Create a copy because we're going to remove from the set for verification purposes.
-            Set<String> schemasNotPlatformSurfaceableCopy =
-                    new ArraySet<>(mSchemasNotPlatformSurfaceable);
+            Set<String> referencedSchemas = new ArraySet<>(mSchemasNotPlatformSurfaceable);
+            referencedSchemas.addAll(mSchemasPackageAccessible.keySet());
+
             for (AppSearchSchema schema : mSchemas) {
-                schemasNotPlatformSurfaceableCopy.remove(schema.getSchemaType());
+                referencedSchemas.remove(schema.getSchemaType());
             }
-            if (!schemasNotPlatformSurfaceableCopy.isEmpty()) {
+            if (!referencedSchemas.isEmpty()) {
                 // We still have schema types that weren't seen in our mSchemas set. This means
                 // there wasn't a corresponding AppSearchSchema.
                 throw new IllegalArgumentException(
-                        "Schema types "
-                                + schemasNotPlatformSurfaceableCopy
-                                + " referenced, but were not added.");
+                        "Schema types " + referencedSchemas + " referenced, but were not added.");
             }
 
-            return new SetSchemaRequest(mSchemas, mSchemasNotPlatformSurfaceable, mForceOverride);
+            return new SetSchemaRequest(
+                    mSchemas,
+                    mSchemasNotPlatformSurfaceable,
+                    mSchemasPackageAccessible,
+                    mForceOverride);
         }
     }
 }
diff --git a/service/java/com/android/server/appsearch/AppSearchManagerService.java b/service/java/com/android/server/appsearch/AppSearchManagerService.java
index 1512825..d81b794 100644
--- a/service/java/com/android/server/appsearch/AppSearchManagerService.java
+++ b/service/java/com/android/server/appsearch/AppSearchManagerService.java
@@ -47,7 +47,6 @@
  */
 public class AppSearchManagerService extends SystemService {
     private static final String TAG = "AppSearchManagerService";
-    private static final char CALLING_NAME_DATABASE_DELIMITER = '$';
 
     public AppSearchManagerService(Context context) {
         super(context);
@@ -78,8 +77,9 @@
                     schemas.add(new AppSearchSchema(schemaBundles.get(i)));
                 }
                 AppSearchImpl impl = ImplInstanceManager.getInstance(getContext(), callingUserId);
-                databaseName = rewriteDatabaseNameWithUid(databaseName, callingUid);
-                impl.setSchema(databaseName, schemas, schemasNotPlatformSurfaceable, forceOverride);
+                String packageName = convertUidToPackageName(callingUid);
+                impl.setSchema(packageName, databaseName, schemas, schemasNotPlatformSurfaceable,
+                        forceOverride);
                 invokeCallbackOnResult(callback,
                         AppSearchResult.newSuccessfulResult(/*result=*/ null));
             } catch (Throwable t) {
@@ -100,8 +100,8 @@
             final long callingIdentity = Binder.clearCallingIdentity();
             try {
                 AppSearchImpl impl = ImplInstanceManager.getInstance(getContext(), callingUserId);
-                databaseName = rewriteDatabaseNameWithUid(databaseName, callingUid);
-                List<AppSearchSchema> schemas = impl.getSchema(databaseName);
+                String packageName = convertUidToPackageName(callingUid);
+                List<AppSearchSchema> schemas = impl.getSchema(packageName, databaseName);
                 List<Bundle> schemaBundles = new ArrayList<>(schemas.size());
                 for (int i = 0; i < schemas.size(); i++) {
                     schemaBundles.add(schemas.get(i).getBundle());
@@ -130,13 +130,13 @@
                 AppSearchBatchResult.Builder<String, Void> resultBuilder =
                         new AppSearchBatchResult.Builder<>();
                 AppSearchImpl impl = ImplInstanceManager.getInstance(getContext(), callingUserId);
-                databaseName = rewriteDatabaseNameWithUid(databaseName, callingUid);
+                String packageName = convertUidToPackageName(callingUid);
                 for (int i = 0; i < documentBundles.size(); i++) {
                     GenericDocument document = new GenericDocument(documentBundles.get(i));
                     try {
                         // TODO(b/173451571): reduce burden of binder thread by enqueue request onto
                         // a separate thread.
-                        impl.putDocument(databaseName, document);
+                        impl.putDocument(packageName, databaseName, document);
                         resultBuilder.setSuccess(document.getUri(), /*result=*/ null);
                     } catch (Throwable t) {
                         resultBuilder.setResult(document.getUri(), throwableToFailedResult(t));
@@ -165,11 +165,12 @@
                 AppSearchBatchResult.Builder<String, Bundle> resultBuilder =
                         new AppSearchBatchResult.Builder<>();
                 AppSearchImpl impl = ImplInstanceManager.getInstance(getContext(), callingUserId);
-                databaseName = rewriteDatabaseNameWithUid(databaseName, callingUid);
+                String packageName = convertUidToPackageName(callingUid);
                 for (int i = 0; i < uris.size(); i++) {
                     String uri = uris.get(i);
                     try {
-                        GenericDocument document = impl.getDocument(databaseName, namespace, uri);
+                        GenericDocument document = impl.getDocument(packageName, databaseName,
+                                namespace, uri);
                         resultBuilder.setSuccess(uri, document.getBundle());
                     } catch (Throwable t) {
                         resultBuilder.setResult(uri, throwableToFailedResult(t));
@@ -199,8 +200,9 @@
             final long callingIdentity = Binder.clearCallingIdentity();
             try {
                 AppSearchImpl impl = ImplInstanceManager.getInstance(getContext(), callingUserId);
-                databaseName = rewriteDatabaseNameWithUid(databaseName, callingUid);
+                String packageName = convertUidToPackageName(callingUid);
                 SearchResultPage searchResultPage = impl.query(
+                        packageName,
                         databaseName,
                         queryExpression,
                         new SearchSpec(searchSpecBundle));
@@ -283,15 +285,15 @@
             int callingUid = Binder.getCallingUidOrThrow();
             int callingUserId = UserHandle.getUserId(callingUid);
             final long callingIdentity = Binder.clearCallingIdentity();
-            AppSearchBatchResult.Builder<String, Void> resultBuilder =
-                    new AppSearchBatchResult.Builder<>();
             try {
+                AppSearchBatchResult.Builder<String, Void> resultBuilder =
+                        new AppSearchBatchResult.Builder<>();
                 AppSearchImpl impl = ImplInstanceManager.getInstance(getContext(), callingUserId);
-                databaseName = rewriteDatabaseNameWithUid(databaseName, callingUid);
+                String packageName = convertUidToPackageName(callingUid);
                 for (int i = 0; i < uris.size(); i++) {
                     String uri = uris.get(i);
                     try {
-                        impl.remove(databaseName, namespace, uri);
+                        impl.remove(packageName, databaseName, namespace, uri);
                         resultBuilder.setSuccess(uri, /*result= */null);
                     } catch (Throwable t) {
                         resultBuilder.setResult(uri, throwableToFailedResult(t));
@@ -320,8 +322,8 @@
             final long callingIdentity = Binder.clearCallingIdentity();
             try {
                 AppSearchImpl impl = ImplInstanceManager.getInstance(getContext(), callingUserId);
-                databaseName = rewriteDatabaseNameWithUid(databaseName, callingUid);
-                impl.removeByQuery(databaseName, queryExpression,
+                String packageName = convertUidToPackageName(callingUid);
+                impl.removeByQuery(packageName, databaseName, queryExpression,
                         new SearchSpec(searchSpecBundle));
                 invokeCallbackOnResult(callback, AppSearchResult.newSuccessfulResult(null));
             } catch (Throwable t) {
@@ -348,13 +350,13 @@
         }
 
         /**
-         * Rewrites the database name by adding a prefix of unique name for the given uid.
+         * Returns a package name for the given uid.
          *
          * <p>The current implementation returns the package name of the app with this uid in a
          * format like {@code com.example.package} or {@code com.example.sharedname:5678}.
          */
         @NonNull
-        private String rewriteDatabaseNameWithUid(String databaseName, int callingUid) {
+        private String convertUidToPackageName(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 = getContext().getPackageManager().getNameForUid(callingUid);
@@ -363,12 +365,12 @@
                 throw new IllegalStateException(
                         "Failed to look up package name for uid " + callingUid);
             }
-            return callingUidName + CALLING_NAME_DATABASE_DELIMITER + databaseName;
+            return callingUidName;
         }
 
-        /**  Invokes the {@link IAppSearchResultCallback} with the result. */
+        /** Invokes the {@link IAppSearchResultCallback} with the result. */
         private void invokeCallbackOnResult(IAppSearchResultCallback callback,
-                AppSearchResult result) {
+                AppSearchResult<?> result) {
             try {
                 callback.onResult(result);
             } catch (RemoteException e) {
@@ -376,9 +378,9 @@
             }
         }
 
-        /**  Invokes the {@link IAppSearchBatchResultCallback} with the result. */
+        /** Invokes the {@link IAppSearchBatchResultCallback} with the result. */
         private void invokeCallbackOnResult(IAppSearchBatchResultCallback callback,
-                AppSearchBatchResult result) {
+                AppSearchBatchResult<?, ?> result) {
             try {
                 callback.onResult(result);
             } catch (RemoteException e) {
@@ -387,9 +389,9 @@
         }
 
         /**
-         *  Invokes the {@link IAppSearchResultCallback} with an throwable.
+         * Invokes the {@link IAppSearchResultCallback} with an throwable.
          *
-         *  <p>The throwable is convert to a {@link AppSearchResult};
+         * <p>The throwable is convert to a {@link AppSearchResult};
          */
         private void invokeCallbackOnError(IAppSearchResultCallback callback, Throwable throwable) {
             try {
@@ -400,7 +402,7 @@
         }
 
         /**
-         *  Invokes the {@link IAppSearchBatchResultCallback} with an throwable.
+         * Invokes the {@link IAppSearchBatchResultCallback} with an unexpected internal throwable.
          *
          * <p>The throwable is converted to {@link ParcelableException}.
          */
diff --git a/service/java/com/android/server/appsearch/external/localstorage/AppSearchImpl.java b/service/java/com/android/server/appsearch/external/localstorage/AppSearchImpl.java
index 62b81d0..c806af5 100644
--- a/service/java/com/android/server/appsearch/external/localstorage/AppSearchImpl.java
+++ b/service/java/com/android/server/appsearch/external/localstorage/AppSearchImpl.java
@@ -75,15 +75,17 @@
  *
  * <p>Never create two instances using the same folder.
  *
- * <p>A single instance of {@link AppSearchImpl} can support all databases. Schemas and documents
- * are physically saved together in {@link IcingSearchEngine}, but logically isolated:
+ * <p>A single instance of {@link AppSearchImpl} can support all packages and databases. This is
+ * done by combining the package and database name into a unique prefix and prefixing the schemas
+ * and documents stored under that owner. Schemas and documents are physically saved together in
+ * {@link IcingSearchEngine}, but logically isolated:
  *
  * <ul>
- *   <li>Rewrite SchemaType in SchemaProto by adding database name prefix and save into SchemaTypes
- *       set in {@link #setSchema}.
- *   <li>Rewrite namespace and SchemaType in DocumentProto by adding database name prefix and save
- *       to namespaces set in {@link #putDocument}.
- *   <li>Remove database name prefix when retrieve documents in {@link #getDocument} and {@link
+ *   <li>Rewrite SchemaType in SchemaProto by adding the package-database prefix and save into
+ *       SchemaTypes set in {@link #setSchema}.
+ *   <li>Rewrite namespace and SchemaType in DocumentProto by adding package-database prefix and
+ *       save to namespaces set in {@link #putDocument}.
+ *   <li>Remove package-database prefix when retrieving documents in {@link #getDocument} and {@link
  *       #query}.
  *   <li>Rewrite filters in {@link SearchSpecProto} to have all namespaces and schema types of the
  *       queried database when user using empty filters in {@link #query}.
@@ -108,6 +110,8 @@
 
     @VisibleForTesting static final char DATABASE_DELIMITER = '/';
 
+    @VisibleForTesting static final char PACKAGE_DELIMITER = '$';
+
     @VisibleForTesting static final int OPTIMIZE_THRESHOLD_DOC_COUNT = 1000;
     @VisibleForTesting static final int OPTIMIZE_THRESHOLD_BYTES = 1_000_000; // 1MB
     @VisibleForTesting static final int CHECK_OPTIMIZE_INTERVAL = 100;
@@ -120,12 +124,14 @@
     @GuardedBy("mReadWriteLock")
     private final VisibilityStore mVisibilityStoreLocked;
 
-    // The map contains schemaTypes and namespaces for all database. All values in the map have
-    // the database name prefix.
+    // This map contains schemaTypes for all package-database prefixes. All values in the map are
+    // prefixed with the package-database prefix.
     // TODO(b/172360376): Check if this can be replaced with an ArrayMap
     @GuardedBy("mReadWriteLock")
     private final Map<String, Set<String>> mSchemaMapLocked = new HashMap<>();
 
+    // This map contains namespaces for all package-database prefixes. All values in the map are
+    // prefixed with the package-database prefix.
     // TODO(b/172360376): Check if this can be replaced with an ArrayMap
     @GuardedBy("mReadWriteLock")
     private final Map<String, Set<String>> mNamespaceMapLocked = new HashMap<>();
@@ -179,19 +185,13 @@
 
             // Populate schema map
             for (SchemaTypeConfigProto schema : schemaProto.getTypesList()) {
-                String qualifiedSchemaType = schema.getSchemaType();
-                addToMap(
-                        mSchemaMapLocked,
-                        getDatabaseName(qualifiedSchemaType),
-                        qualifiedSchemaType);
+                String prefixedSchemaType = schema.getSchemaType();
+                addToMap(mSchemaMapLocked, getPrefix(prefixedSchemaType), prefixedSchemaType);
             }
 
             // Populate namespace map
-            for (String qualifiedNamespace : getAllNamespacesResultProto.getNamespacesList()) {
-                addToMap(
-                        mNamespaceMapLocked,
-                        getDatabaseName(qualifiedNamespace),
-                        qualifiedNamespace);
+            for (String prefixedNamespace : getAllNamespacesResultProto.getNamespacesList()) {
+                addToMap(mNamespaceMapLocked, getPrefix(prefixedNamespace), prefixedNamespace);
             }
 
             // TODO(b/155939114): It's possible to optimize after init, which would reduce the time
@@ -225,6 +225,7 @@
      *
      * <p>This method belongs to mutate group.
      *
+     * @param packageName The package name that owns the schemas.
      * @param databaseName The name of the database where this schema lives.
      * @param schemas Schemas to set for this app.
      * @param schemasNotPlatformSurfaceable Schema types that should not be surfaced on platform
@@ -234,6 +235,7 @@
      * @throws AppSearchException on IcingSearchEngine error.
      */
     public void setSchema(
+            @NonNull String packageName,
             @NonNull String databaseName,
             @NonNull List<AppSearchSchema> schemas,
             @NonNull List<String> schemasNotPlatformSurfaceable,
@@ -250,10 +252,11 @@
                 newSchemaBuilder.addTypes(schemaTypeProto);
             }
 
-            // Combine the existing schema (which may have types from other databases) with this
-            // database's new schema. Modifies the existingSchemaBuilder.
+            String prefix = createPrefix(packageName, databaseName);
+            // Combine the existing schema (which may have types from other prefixes) with this
+            // prefix's new schema. Modifies the existingSchemaBuilder.
             RewrittenSchemaResults rewrittenSchemaResults =
-                    rewriteSchema(databaseName, existingSchemaBuilder, newSchemaBuilder.build());
+                    rewriteSchema(prefix, existingSchemaBuilder, newSchemaBuilder.build());
 
             // Apply schema
             SetSchemaResultProto setSchemaResultProto =
@@ -280,17 +283,15 @@
             }
 
             // Update derived data structures.
-            mSchemaMapLocked.put(databaseName, rewrittenSchemaResults.mRewrittenQualifiedTypes);
+            mSchemaMapLocked.put(prefix, rewrittenSchemaResults.mRewrittenPrefixedTypes);
 
-            String databasePrefix = getDatabasePrefix(databaseName);
-            Set<String> qualifiedSchemasNotPlatformSurfaceable =
+            Set<String> prefixedSchemasNotPlatformSurfaceable =
                     new ArraySet<>(schemasNotPlatformSurfaceable.size());
             for (int i = 0; i < schemasNotPlatformSurfaceable.size(); i++) {
-                qualifiedSchemasNotPlatformSurfaceable.add(
-                        databasePrefix + schemasNotPlatformSurfaceable.get(i));
+                prefixedSchemasNotPlatformSurfaceable.add(
+                        prefix + schemasNotPlatformSurfaceable.get(i));
             }
-            mVisibilityStoreLocked.setVisibility(
-                    databaseName, qualifiedSchemasNotPlatformSurfaceable);
+            mVisibilityStoreLocked.setVisibility(prefix, prefixedSchemasNotPlatformSurfaceable);
 
             // Determine whether to schedule an immediate optimize.
             if (setSchemaResultProto.getDeletedSchemaTypesCount() > 0
@@ -307,15 +308,17 @@
     }
 
     /**
-     * Retrieves the AppSearch schema for this database.
+     * Retrieves the AppSearch schema for this package name, database.
      *
      * <p>This method belongs to query group.
      *
+     * @param packageName Package name that owns this schema
      * @param databaseName The name of the database where this schema lives.
      * @throws AppSearchException on IcingSearchEngine error.
      */
     @NonNull
-    public List<AppSearchSchema> getSchema(@NonNull String databaseName) throws AppSearchException {
+    public List<AppSearchSchema> getSchema(
+            @NonNull String packageName, @NonNull String databaseName) throws AppSearchException {
         SchemaProto fullSchema;
         mReadWriteLock.readLock().lock();
         try {
@@ -324,16 +327,16 @@
             mReadWriteLock.readLock().unlock();
         }
 
+        String prefix = createPrefix(packageName, databaseName);
         List<AppSearchSchema> result = new ArrayList<>();
         for (int i = 0; i < fullSchema.getTypesCount(); i++) {
-            String typeDatabase = getDatabaseName(fullSchema.getTypes(i).getSchemaType());
-            if (!databaseName.equals(typeDatabase)) {
+            String typePrefix = getPrefix(fullSchema.getTypes(i).getSchemaType());
+            if (!prefix.equals(typePrefix)) {
                 continue;
             }
             // Rewrite SchemaProto.types.schema_type
             SchemaTypeConfigProto.Builder typeConfigBuilder = fullSchema.getTypes(i).toBuilder();
-            String newSchemaType =
-                    typeConfigBuilder.getSchemaType().substring(databaseName.length() + 1);
+            String newSchemaType = typeConfigBuilder.getSchemaType().substring(prefix.length());
             typeConfigBuilder.setSchemaType(newSchemaType);
 
             // Rewrite SchemaProto.types.properties.schema_type
@@ -344,9 +347,7 @@
                         typeConfigBuilder.getProperties(propertyIdx).toBuilder();
                 if (!propertyConfigBuilder.getSchemaType().isEmpty()) {
                     String newPropertySchemaType =
-                            propertyConfigBuilder
-                                    .getSchemaType()
-                                    .substring(databaseName.length() + 1);
+                            propertyConfigBuilder.getSchemaType().substring(prefix.length());
                     propertyConfigBuilder.setSchemaType(newPropertySchemaType);
                     typeConfigBuilder.setProperties(propertyIdx, propertyConfigBuilder);
                 }
@@ -363,21 +364,26 @@
      *
      * <p>This method belongs to mutate group.
      *
+     * @param packageName The package name that owns this document.
      * @param databaseName The databaseName this document resides in.
      * @param document The document to index.
      * @throws AppSearchException on IcingSearchEngine error.
      */
-    public void putDocument(@NonNull String databaseName, @NonNull GenericDocument document)
+    public void putDocument(
+            @NonNull String packageName,
+            @NonNull String databaseName,
+            @NonNull GenericDocument document)
             throws AppSearchException {
         DocumentProto.Builder documentBuilder =
                 GenericDocumentToProtoConverter.toDocumentProto(document).toBuilder();
-        addPrefixToDocument(documentBuilder, getDatabasePrefix(databaseName));
+        String prefix = createPrefix(packageName, databaseName);
+        addPrefixToDocument(documentBuilder, prefix);
 
         PutResultProto putResultProto;
         mReadWriteLock.writeLock().lock();
         try {
             putResultProto = mIcingSearchEngineLocked.put(documentBuilder.build());
-            addToMap(mNamespaceMapLocked, databaseName, documentBuilder.getNamespace());
+            addToMap(mNamespaceMapLocked, prefix, documentBuilder.getNamespace());
             // The existing documents with same URI will be deleted, so there maybe some resources
             // could be released after optimize().
             checkForOptimizeLocked(/* force= */ false);
@@ -392,6 +398,7 @@
      *
      * <p>This method belongs to query group.
      *
+     * @param packageName The package that owns this document.
      * @param databaseName The databaseName this document resides in.
      * @param namespace The namespace this document resides in.
      * @param uri The URI of the document to get.
@@ -400,20 +407,24 @@
      */
     @NonNull
     public GenericDocument getDocument(
-            @NonNull String databaseName, @NonNull String namespace, @NonNull String uri)
+            @NonNull String packageName,
+            @NonNull String databaseName,
+            @NonNull String namespace,
+            @NonNull String uri)
             throws AppSearchException {
         GetResultProto getResultProto;
         mReadWriteLock.readLock().lock();
         try {
             getResultProto =
-                    mIcingSearchEngineLocked.get(getDatabasePrefix(databaseName) + namespace, uri);
+                    mIcingSearchEngineLocked.get(
+                            createPrefix(packageName, databaseName) + namespace, uri);
         } finally {
             mReadWriteLock.readLock().unlock();
         }
         checkSuccess(getResultProto.getStatus());
 
         DocumentProto.Builder documentBuilder = getResultProto.getDocument().toBuilder();
-        removeDatabasesFromDocument(documentBuilder);
+        removePrefixesFromDocument(documentBuilder);
         return GenericDocumentToProtoConverter.toGenericDocument(documentBuilder.build());
     }
 
@@ -422,6 +433,7 @@
      *
      * <p>This method belongs to query group.
      *
+     * @param packageName The package name that is performing the query.
      * @param databaseName The databaseName this query for.
      * @param queryExpression Query String to search.
      * @param searchSpec Spec for setting filters, raw query etc.
@@ -431,20 +443,24 @@
      */
     @NonNull
     public SearchResultPage query(
+            @NonNull String packageName,
             @NonNull String databaseName,
             @NonNull String queryExpression,
             @NonNull SearchSpec searchSpec)
             throws AppSearchException {
         mReadWriteLock.readLock().lock();
         try {
-            return doQueryLocked(Collections.singleton(databaseName), queryExpression, searchSpec);
+            return doQueryLocked(
+                    Collections.singleton(createPrefix(packageName, databaseName)),
+                    queryExpression,
+                    searchSpec);
         } finally {
             mReadWriteLock.readLock().unlock();
         }
     }
 
     /**
-     * Executes a global query, i.e. over all permitted databases, against the AppSearch index and
+     * Executes a global query, i.e. over all permitted prefixes, against the AppSearch index and
      * returns results.
      *
      * <p>This method belongs to query group.
@@ -464,9 +480,15 @@
         //  verified.
         mReadWriteLock.readLock().lock();
         try {
-            // We use the mNamespaceMap.keySet here because it's the smaller set of valid databases
+            // We use the mNamespaceMap.keySet here because it's the smaller set of valid prefixes
             // that could exist.
-            return doQueryLocked(mNamespaceMapLocked.keySet(), queryExpression, searchSpec);
+            Set<String> prefixes = mNamespaceMapLocked.keySet();
+
+            // Filter out any VisibilityStore documents which are AppSearch-internal only.
+            prefixes.remove(
+                    createPrefix(VisibilityStore.PACKAGE_NAME, VisibilityStore.DATABASE_NAME));
+
+            return doQueryLocked(prefixes, queryExpression, searchSpec);
         } finally {
             mReadWriteLock.readLock().unlock();
         }
@@ -474,7 +496,7 @@
 
     @GuardedBy("mReadWriteLock")
     private SearchResultPage doQueryLocked(
-            @NonNull Set<String> databases,
+            @NonNull Set<String> prefixes,
             @NonNull String queryExpression,
             @NonNull SearchSpec searchSpec)
             throws AppSearchException {
@@ -486,12 +508,10 @@
         ScoringSpecProto scoringSpec = SearchSpecToProtoConverter.toScoringSpecProto(searchSpec);
         SearchResultProto searchResultProto;
 
-        // rewriteSearchSpecForDatabases will return false if none of the databases that the
+        // rewriteSearchSpecForPrefixesLocked will return false if none of the prefixes that the
         // client is trying to search on exist, so we can return an empty SearchResult and skip
         // sending request to Icing.
-        // We use the mNamespaceMap.keySet here because it's the smaller set of valid databases
-        // that could exist.
-        if (!rewriteSearchSpecForDatabasesLocked(searchSpecBuilder, databases)) {
+        if (!rewriteSearchSpecForPrefixesLocked(searchSpecBuilder, prefixes)) {
             return new SearchResultPage(Bundle.EMPTY);
         }
         searchResultProto =
@@ -546,18 +566,23 @@
      *
      * <p>This method belongs to mutate group.
      *
+     * @param packageName The package name that owns the document.
      * @param databaseName The databaseName the document is in.
      * @param namespace Namespace of the document to remove.
      * @param uri URI of the document to remove.
      * @throws AppSearchException on IcingSearchEngine error.
      */
-    public void remove(@NonNull String databaseName, @NonNull String namespace, @NonNull String uri)
+    public void remove(
+            @NonNull String packageName,
+            @NonNull String databaseName,
+            @NonNull String namespace,
+            @NonNull String uri)
             throws AppSearchException {
-        String qualifiedNamespace = getDatabasePrefix(databaseName) + namespace;
+        String prefixedNamespace = createPrefix(packageName, databaseName) + namespace;
         DeleteResultProto deleteResultProto;
         mReadWriteLock.writeLock().lock();
         try {
-            deleteResultProto = mIcingSearchEngineLocked.delete(qualifiedNamespace, uri);
+            deleteResultProto = mIcingSearchEngineLocked.delete(prefixedNamespace, uri);
             checkForOptimizeLocked(/* force= */ false);
         } finally {
             mReadWriteLock.writeLock().unlock();
@@ -570,12 +595,14 @@
      *
      * <p>This method belongs to mutate group.
      *
+     * @param packageName The package name that owns the documents.
      * @param databaseName The databaseName the document is in.
      * @param queryExpression Query String to search.
      * @param searchSpec Defines what and how to remove
      * @throws AppSearchException on IcingSearchEngine error.
      */
     public void removeByQuery(
+            @NonNull String packageName,
             @NonNull String databaseName,
             @NonNull String queryExpression,
             @NonNull SearchSpec searchSpec)
@@ -586,11 +613,12 @@
         DeleteResultProto deleteResultProto;
         mReadWriteLock.writeLock().lock();
         try {
-            // Only rewrite SearchSpec for non empty database.
-            // rewriteSearchSpecForNonEmptyDatabase will return false for empty database, we
+            // Only rewrite SearchSpec for non empty prefixes.
+            // rewriteSearchSpecForPrefixesLocked will return false for empty prefixes, we
             // should skip sending request to Icing and return in here.
-            if (!rewriteSearchSpecForDatabasesLocked(
-                    searchSpecBuilder, Collections.singleton(databaseName))) {
+            if (!rewriteSearchSpecForPrefixesLocked(
+                    searchSpecBuilder,
+                    Collections.singleton(createPrefix(packageName, databaseName)))) {
                 return;
             }
             deleteResultProto = mIcingSearchEngineLocked.deleteByQuery(searchSpecBuilder.build());
@@ -605,7 +633,7 @@
     }
 
     /**
-     * Clears documents and schema across all databaseNames.
+     * Clears documents and schema across all packages and databaseNames.
      *
      * <p>This method belongs to mutate group.
      *
@@ -632,33 +660,30 @@
     /** Wrapper around schema changes */
     @VisibleForTesting
     static class RewrittenSchemaResults {
-        // Any database-qualified types that used to exist in the schema, but are deleted in the
-        // new one.
-        final Set<String> mDeletedQualifiedTypes = new ArraySet<>();
+        // Any prefixed types that used to exist in the schema, but are deleted in the new one.
+        final Set<String> mDeletedPrefixedTypes = new ArraySet<>();
 
-        // Database-qualified types that were part of the new schema.
-        final Set<String> mRewrittenQualifiedTypes = new ArraySet<>();
+        // Prefixed types that were part of the new schema.
+        final Set<String> mRewrittenPrefixedTypes = new ArraySet<>();
     }
 
     /**
      * Rewrites all types mentioned in the given {@code newSchema} to prepend {@code prefix}.
      * Rewritten types will be added to the {@code existingSchema}.
      *
-     * @param databaseName The name of the database where this schema lives.
-     * @param existingSchema A schema that may contain existing types from across all database
-     *     instances. Will be mutated to contain the properly rewritten schema types from {@code
-     *     newSchema}.
+     * @param prefix The full prefix to prepend to the schema.
+     * @param existingSchema A schema that may contain existing types from across all prefixes. Will
+     *     be mutated to contain the properly rewritten schema types from {@code newSchema}.
      * @param newSchema Schema with types to add to the {@code existingSchema}.
-     * @return a RewrittenSchemaResults contains all qualified schema type names in the given
-     *     database as well as a set of schema types that were deleted from the database.
+     * @return a RewrittenSchemaResults that contains all prefixed schema type names in the given
+     *     prefix as well as a set of schema types that were deleted.
      */
     @VisibleForTesting
     static RewrittenSchemaResults rewriteSchema(
-            @NonNull String databaseName,
+            @NonNull String prefix,
             @NonNull SchemaProto.Builder existingSchema,
             @NonNull SchemaProto newSchema)
             throws AppSearchException {
-        String prefix = getDatabasePrefix(databaseName);
         HashMap<String, SchemaTypeConfigProto> newTypesToProto = new HashMap<>();
         // Rewrite the schema type to include the typePrefix.
         for (int typeIdx = 0; typeIdx < newSchema.getTypesCount(); typeIdx++) {
@@ -687,10 +712,10 @@
 
         // newTypesToProto is modified below, so we need a copy first
         RewrittenSchemaResults rewrittenSchemaResults = new RewrittenSchemaResults();
-        rewrittenSchemaResults.mRewrittenQualifiedTypes.addAll(newTypesToProto.keySet());
+        rewrittenSchemaResults.mRewrittenPrefixedTypes.addAll(newTypesToProto.keySet());
 
-        // Combine the existing schema (which may have types from other databases) with this
-        // database's new schema. Modifies the existingSchemaBuilder.
+        // Combine the existing schema (which may have types from other prefixes) with this
+        // prefix's new schema. Modifies the existingSchemaBuilder.
         // Check if we need to replace any old schema types with the new ones.
         for (int i = 0; i < existingSchema.getTypesCount(); i++) {
             String schemaType = existingSchema.getTypes(i).getSchemaType();
@@ -698,11 +723,11 @@
             if (newProto != null) {
                 // Replacement
                 existingSchema.setTypes(i, newProto);
-            } else if (databaseName.equals(getDatabaseName(schemaType))) {
+            } else if (prefix.equals(getPrefix(schemaType))) {
                 // All types existing before but not in newSchema should be removed.
                 existingSchema.removeTypes(i);
                 --i;
-                rewrittenSchemaResults.mDeletedQualifiedTypes.add(schemaType);
+                rewrittenSchemaResults.mDeletedPrefixedTypes.add(schemaType);
             }
         }
         // We've been removing existing types from newTypesToProto, so everything that remains is
@@ -749,17 +774,16 @@
     }
 
     /**
-     * Removes any database names from types and namespaces mentioned anywhere in {@code
-     * documentBuilder}.
+     * Removes any prefixes from types and namespaces mentioned anywhere in {@code documentBuilder}.
      *
      * @param documentBuilder The document to mutate
      */
     @VisibleForTesting
-    static void removeDatabasesFromDocument(@NonNull DocumentProto.Builder documentBuilder)
+    static void removePrefixesFromDocument(@NonNull DocumentProto.Builder documentBuilder)
             throws AppSearchException {
         // Rewrite the type name and namespace to remove the prefix.
-        documentBuilder.setSchema(removeDatabasePrefix(documentBuilder.getSchema()));
-        documentBuilder.setNamespace(removeDatabasePrefix(documentBuilder.getNamespace()));
+        documentBuilder.setSchema(removePrefix(documentBuilder.getSchema()));
+        documentBuilder.setNamespace(removePrefix(documentBuilder.getNamespace()));
 
         // Recurse into derived documents
         for (int propertyIdx = 0;
@@ -772,7 +796,7 @@
                 for (int documentIdx = 0; documentIdx < documentCount; documentIdx++) {
                     DocumentProto.Builder derivedDocumentBuilder =
                             propertyBuilder.getDocumentValues(documentIdx).toBuilder();
-                    removeDatabasesFromDocument(derivedDocumentBuilder);
+                    removePrefixesFromDocument(derivedDocumentBuilder);
                     propertyBuilder.setDocumentValues(documentIdx, derivedDocumentBuilder);
                 }
                 documentBuilder.setProperties(propertyIdx, propertyBuilder);
@@ -781,27 +805,25 @@
     }
 
     /**
-     * Rewrites the schemaTypeFilters and namespacesFilters that exist in {@code databaseNames}.
+     * Rewrites the schemaTypeFilters and namespacesFilters that exist with {@code prefixes}.
      *
-     * <p>If the searchSpec has empty filter lists, all existing databases from {@code
-     * databaseNames} will be added.
+     * <p>If the searchSpec has empty filter lists, all prefixes filters will be added.
      *
      * <p>This method should be only called in query methods and get the READ lock to keep thread
      * safety.
      *
-     * @return false if none of the requested databases exist.
+     * @return false if none of the requested prefixes exist.
      */
     @VisibleForTesting
     @GuardedBy("mReadWriteLock")
-    boolean rewriteSearchSpecForDatabasesLocked(
-            @NonNull SearchSpecProto.Builder searchSpecBuilder,
-            @NonNull Set<String> databaseNames) {
+    boolean rewriteSearchSpecForPrefixesLocked(
+            @NonNull SearchSpecProto.Builder searchSpecBuilder, @NonNull Set<String> prefixes) {
         // Create a copy since retainAll() modifies the original set.
-        Set<String> existingDatabases = new ArraySet<>(mNamespaceMapLocked.keySet());
-        existingDatabases.retainAll(databaseNames);
+        Set<String> existingPrefixes = new ArraySet<>(mNamespaceMapLocked.keySet());
+        existingPrefixes.retainAll(prefixes);
 
-        if (existingDatabases.isEmpty()) {
-            // None of the databases exist, empty query.
+        if (existingPrefixes.isEmpty()) {
+            // None of the prefixes exist, empty query.
             return false;
         }
 
@@ -812,33 +834,32 @@
         List<String> namespaceFilters = searchSpecBuilder.getNamespaceFiltersList();
         searchSpecBuilder.clearNamespaceFilters();
 
-        // Rewrite filters to include a database prefix.
-        for (String databaseName : existingDatabases) {
-            Set<String> existingSchemaTypes = mSchemaMapLocked.get(databaseName);
-            String databaseNamePrefix = getDatabasePrefix(databaseName);
+        // Rewrite filters to include a prefix.
+        for (String prefix : existingPrefixes) {
+            Set<String> existingSchemaTypes = mSchemaMapLocked.get(prefix);
             if (schemaTypeFilters.isEmpty()) {
                 // Include all schema types
                 searchSpecBuilder.addAllSchemaTypeFilters(existingSchemaTypes);
             } else {
-                // Qualify the given schema types
+                // Add the prefix to the given schema types
                 for (int i = 0; i < schemaTypeFilters.size(); i++) {
-                    String qualifiedType = databaseNamePrefix + schemaTypeFilters.get(i);
-                    if (existingSchemaTypes.contains(qualifiedType)) {
-                        searchSpecBuilder.addSchemaTypeFilters(qualifiedType);
+                    String prefixedType = prefix + schemaTypeFilters.get(i);
+                    if (existingSchemaTypes.contains(prefixedType)) {
+                        searchSpecBuilder.addSchemaTypeFilters(prefixedType);
                     }
                 }
             }
 
-            Set<String> existingNamespaces = mNamespaceMapLocked.get(databaseName);
+            Set<String> existingNamespaces = mNamespaceMapLocked.get(prefix);
             if (namespaceFilters.isEmpty()) {
                 // Include all namespaces
                 searchSpecBuilder.addAllNamespaceFilters(existingNamespaces);
             } else {
-                // Qualify the given namespaces.
+                // Prefix the given namespaces.
                 for (int i = 0; i < namespaceFilters.size(); i++) {
-                    String qualifiedNamespace = databaseNamePrefix + namespaceFilters.get(i);
-                    if (existingNamespaces.contains(qualifiedNamespace)) {
-                        searchSpecBuilder.addNamespaceFilters(qualifiedNamespace);
+                    String prefixedNamespace = prefix + namespaceFilters.get(i);
+                    if (existingNamespaces.contains(prefixedNamespace)) {
+                        searchSpecBuilder.addNamespaceFilters(prefixedNamespace);
                     }
                 }
             }
@@ -857,36 +878,41 @@
         return schemaProto.getSchema();
     }
 
-    /** Returns true if {@code databaseName} has a {@code schemaType} */
+    /**
+     * Returns true if the {@code packageName} and {@code databaseName} has the {@code schemaType}
+     */
     @GuardedBy("mReadWriteLock")
-    boolean hasSchemaTypeLocked(@NonNull String databaseName, @NonNull String schemaType) {
+    boolean hasSchemaTypeLocked(
+            @NonNull String packageName, @NonNull String databaseName, @NonNull String schemaType) {
+        Preconditions.checkNotNull(packageName);
         Preconditions.checkNotNull(databaseName);
         Preconditions.checkNotNull(schemaType);
 
-        Set<String> schemaTypes = mSchemaMapLocked.get(databaseName);
+        String prefix = createPrefix(packageName, databaseName);
+        Set<String> schemaTypes = mSchemaMapLocked.get(prefix);
         if (schemaTypes == null) {
             return false;
         }
 
-        return schemaTypes.contains(getDatabasePrefix(databaseName) + schemaType);
+        return schemaTypes.contains(prefix + schemaType);
     }
 
-    /** Returns a set of all databases AppSearchImpl knows about. */
+    /** Returns a set of all prefixes AppSearchImpl knows about. */
     @GuardedBy("mReadWriteLock")
     @NonNull
-    Set<String> getDatabasesLocked() {
+    Set<String> getPrefixesLocked() {
         return mSchemaMapLocked.keySet();
     }
 
     @NonNull
-    private static String getDatabasePrefix(@NonNull String databaseName) {
-        // TODO(b/170370381): Reconsider the way we separate database names for security reasons.
-        return databaseName + DATABASE_DELIMITER;
+    static String createPrefix(@NonNull String packageName, @NonNull String databaseName) {
+        return packageName + PACKAGE_DELIMITER + databaseName + DATABASE_DELIMITER;
     }
 
     @NonNull
-    private static String removeDatabasePrefix(@NonNull String prefixedString)
-            throws AppSearchException {
+    private static String removePrefix(@NonNull String prefixedString) throws AppSearchException {
+        // The prefix is made up of the package, then the database. So we only need to find the
+        // database cutoff.
         int delimiterIndex;
         if ((delimiterIndex = prefixedString.indexOf(DATABASE_DELIMITER)) != -1) {
             // Add 1 to include the char size of the DATABASE_DELIMITER
@@ -898,22 +924,24 @@
     }
 
     @NonNull
-    private static String getDatabaseName(@NonNull String prefixedValue) throws AppSearchException {
-        int delimiterIndex = prefixedValue.indexOf(DATABASE_DELIMITER);
-        if (delimiterIndex == -1) {
+    private static String getPrefix(@NonNull String prefixedString) throws AppSearchException {
+        int databaseDelimiterIndex = prefixedString.indexOf(DATABASE_DELIMITER);
+        if (databaseDelimiterIndex == -1) {
             throw new AppSearchException(
                     AppSearchResult.RESULT_UNKNOWN_ERROR,
                     "The databaseName prefixed value doesn't contains a valid database name.");
         }
-        return prefixedValue.substring(0, delimiterIndex);
+
+        // Add 1 to include the char size of the DATABASE_DELIMITER
+        return prefixedString.substring(0, databaseDelimiterIndex + 1);
     }
 
     private static void addToMap(
-            Map<String, Set<String>> map, String databaseName, String prefixedValue) {
-        Set<String> values = map.get(databaseName);
+            Map<String, Set<String>> map, String prefix, String prefixedValue) {
+        Set<String> values = map.get(prefix);
         if (values == null) {
             values = new ArraySet<>();
-            map.put(databaseName, values);
+            map.put(prefix, values);
         }
         values.add(prefixedValue);
     }
@@ -994,7 +1022,7 @@
                 SearchResultProto.ResultProto.Builder resultBuilder =
                         searchResultProto.getResults(i).toBuilder();
                 DocumentProto.Builder documentBuilder = resultBuilder.getDocument().toBuilder();
-                removeDatabasesFromDocument(documentBuilder);
+                removePrefixesFromDocument(documentBuilder);
                 resultBuilder.setDocument(documentBuilder);
                 resultsBuilder.setResults(i, resultBuilder);
             }
diff --git a/service/java/com/android/server/appsearch/external/localstorage/VisibilityStore.java b/service/java/com/android/server/appsearch/external/localstorage/VisibilityStore.java
index 0b68ebc..411da2f 100644
--- a/service/java/com/android/server/appsearch/external/localstorage/VisibilityStore.java
+++ b/service/java/com/android/server/appsearch/external/localstorage/VisibilityStore.java
@@ -51,24 +51,58 @@
  * this class. Take care to not cause any circular dependencies.
  */
 class VisibilityStore {
-    // Schema type for documents that hold AppSearch's metadata, e.g. visibility settings
+    /** Schema type for documents that hold AppSearch's metadata, e.g. visibility settings */
     @VisibleForTesting static final String SCHEMA_TYPE = "Visibility";
 
-    // Property that holds the list of platform-hidden schemas, as part of the visibility
-    // settings.
+    /**
+     * Property that holds the list of platform-hidden schemas, as part of the visibility settings.
+     */
     @VisibleForTesting
     static final String NOT_PLATFORM_SURFACEABLE_PROPERTY = "notPlatformSurfaceable";
-    // Database name to prefix all visibility schemas and documents with. Special-cased to
-    // minimize the chance of collision with a client-supplied database.
 
-    @VisibleForTesting static final String DATABASE_NAME = "$$__AppSearch__Database";
+    /** Schema for the VisibilityStore's docuemnts. */
+    @VisibleForTesting
+    static final AppSearchSchema SCHEMA =
+            new AppSearchSchema.Builder(SCHEMA_TYPE)
+                    .addProperty(
+                            new AppSearchSchema.PropertyConfig.Builder(
+                                            NOT_PLATFORM_SURFACEABLE_PROPERTY)
+                                    .setDataType(AppSearchSchema.PropertyConfig.DATA_TYPE_STRING)
+                                    .setCardinality(
+                                            AppSearchSchema.PropertyConfig.CARDINALITY_REPEATED)
+                                    .build())
+                    .build();
 
-    // Namespace of documents that contain visibility settings
-    private static final String NAMESPACE = "namespace";
+    /**
+     * These cannot have any of the special characters used by AppSearchImpl (e.g. {@link
+     * AppSearchImpl#PACKAGE_DELIMITER} or {@link AppSearchImpl#DATABASE_DELIMITER}.
+     */
+    static final String PACKAGE_NAME = "VS#Pkg";
+
+    static final String DATABASE_NAME = "VS#Db";
+
+    /**
+     * Prefix that AppSearchImpl creates for the VisibilityStore based on our package name and
+     * database name. Tracked here to tell when we're looking at our own prefix when looking through
+     * AppSearchImpl.
+     */
+    private static final String VISIBILITY_STORE_PREFIX =
+            AppSearchImpl.createPrefix(PACKAGE_NAME, DATABASE_NAME);
+
+    /** Namespace of documents that contain visibility settings */
+    private static final String NAMESPACE = GenericDocument.DEFAULT_NAMESPACE;
+
+    /**
+     * Prefix to add to all visibility document uri's. IcingSearchEngine doesn't allow empty uri's.
+     */
+    private static final String URI_PREFIX = "uri:";
+
     private final AppSearchImpl mAppSearchImpl;
 
-    // The map contains schemas that are platform-hidden for each database. All schemas in the map
-    // have a database name prefix.
+    /**
+     * Maps prefixes to the set of schemas that are platform-hidden within that prefix. All schemas
+     * in the map are prefixed.
+     */
     private final Map<String, Set<String>> mNotPlatformSurfaceableMap = new ArrayMap<>();
 
     /**
@@ -92,42 +126,36 @@
      * @throws AppSearchException AppSearchException on AppSearchImpl error.
      */
     public void initialize() throws AppSearchException {
-        if (!mAppSearchImpl.hasSchemaTypeLocked(DATABASE_NAME, SCHEMA_TYPE)) {
+        if (!mAppSearchImpl.hasSchemaTypeLocked(PACKAGE_NAME, DATABASE_NAME, SCHEMA_TYPE)) {
             // Schema type doesn't exist yet. Add it.
             mAppSearchImpl.setSchema(
+                    PACKAGE_NAME,
                     DATABASE_NAME,
-                    Collections.singletonList(
-                            new AppSearchSchema.Builder(SCHEMA_TYPE)
-                                    .addProperty(
-                                            new AppSearchSchema.PropertyConfig.Builder(
-                                                            NOT_PLATFORM_SURFACEABLE_PROPERTY)
-                                                    .setDataType(
-                                                            AppSearchSchema.PropertyConfig
-                                                                    .DATA_TYPE_STRING)
-                                                    .setCardinality(
-                                                            AppSearchSchema.PropertyConfig
-                                                                    .CARDINALITY_REPEATED)
-                                                    .build())
-                                    .build()),
+                    Collections.singletonList(SCHEMA),
                     /*schemasNotPlatformSurfaceable=*/ Collections.emptyList(),
                     /*forceOverride=*/ false);
         }
 
-        // Populate visibility settings map
-        for (String database : mAppSearchImpl.getDatabasesLocked()) {
-            if (database.equals(DATABASE_NAME)) {
-                // Our own database. Skip
+        // Populate visibility settings set
+        mNotPlatformSurfaceableMap.clear();
+        for (String prefix : mAppSearchImpl.getPrefixesLocked()) {
+            if (prefix.equals(VISIBILITY_STORE_PREFIX)) {
+                // Our own prefix. Skip
                 continue;
             }
 
             try {
-                // Note: We use the other clients' database names as uris
+                // Note: We use the other clients' prefixed names as uris
                 GenericDocument document =
-                        mAppSearchImpl.getDocument(DATABASE_NAME, NAMESPACE, /*uri=*/ database);
+                        mAppSearchImpl.getDocument(
+                                PACKAGE_NAME,
+                                DATABASE_NAME,
+                                NAMESPACE,
+                                /*uri=*/ addUriPrefix(prefix));
 
                 String[] schemas =
                         document.getPropertyStringArray(NOT_PLATFORM_SURFACEABLE_PROPERTY);
-                mNotPlatformSurfaceableMap.put(database, new ArraySet<>(Arrays.asList(schemas)));
+                mNotPlatformSurfaceableMap.put(prefix, new ArraySet<>(Arrays.asList(schemas)));
             } catch (AppSearchException e) {
                 if (e.getResultCode() == AppSearchResult.RESULT_NOT_FOUND) {
                     // TODO(b/172068212): This indicates some desync error. We were expecting a
@@ -142,51 +170,46 @@
     }
 
     /**
-     * Sets visibility settings for {@code databaseName}. Any previous visibility settings will be
+     * Sets visibility settings for {@code prefix}. Any previous visibility settings will be
      * overwritten.
      *
-     * @param databaseName Database name that owns the {@code schemasNotPlatformSurfaceable}.
-     * @param schemasNotPlatformSurfaceable Set of database-qualified schemas that should be hidden
-     *     from the platform.
+     * @param prefix Prefix that identifies who owns the {@code schemasNotPlatformSurfaceable}.
+     * @param schemasNotPlatformSurfaceable Set of prefixed schemas that should be hidden from the
+     *     platform.
      * @throws AppSearchException on AppSearchImpl error.
      */
     public void setVisibility(
-            @NonNull String databaseName, @NonNull Set<String> schemasNotPlatformSurfaceable)
+            @NonNull String prefix, @NonNull Set<String> schemasNotPlatformSurfaceable)
             throws AppSearchException {
-        Preconditions.checkNotNull(databaseName);
+        Preconditions.checkNotNull(prefix);
         Preconditions.checkNotNull(schemasNotPlatformSurfaceable);
 
         // Persist the document
         GenericDocument.Builder visibilityDocument =
-                new GenericDocument.Builder(/*uri=*/ databaseName, SCHEMA_TYPE)
+                new GenericDocument.Builder(/*uri=*/ addUriPrefix(prefix), SCHEMA_TYPE)
                         .setNamespace(NAMESPACE);
         if (!schemasNotPlatformSurfaceable.isEmpty()) {
             visibilityDocument.setPropertyString(
                     NOT_PLATFORM_SURFACEABLE_PROPERTY,
                     schemasNotPlatformSurfaceable.toArray(new String[0]));
         }
-        mAppSearchImpl.putDocument(DATABASE_NAME, visibilityDocument.build());
+        mAppSearchImpl.putDocument(PACKAGE_NAME, DATABASE_NAME, visibilityDocument.build());
 
         // Update derived data structures.
-        mNotPlatformSurfaceableMap.put(databaseName, schemasNotPlatformSurfaceable);
+        mNotPlatformSurfaceableMap.put(prefix, schemasNotPlatformSurfaceable);
     }
 
-    /**
-     * Returns the set of database-qualified schemas in {@code databaseName} that are hidden from
-     * the platform.
-     *
-     * @param databaseName Database name to retrieve schemas for
-     * @return Set of database-qualified schemas that are hidden from the platform. Empty set if
-     *     none exist.
-     */
+    /** Returns if the schema is surfaceable by the platform. */
     @NonNull
-    public Set<String> getSchemasNotPlatformSurfaceable(@NonNull String databaseName) {
-        Preconditions.checkNotNull(databaseName);
-        Set<String> schemasNotPlatformSurfaceable = mNotPlatformSurfaceableMap.get(databaseName);
-        if (schemasNotPlatformSurfaceable == null) {
-            return Collections.emptySet();
+    public boolean isSchemaPlatformSurfaceable(
+            @NonNull String prefix, @NonNull String prefixedSchema) {
+        Preconditions.checkNotNull(prefix);
+        Preconditions.checkNotNull(prefixedSchema);
+        Set<String> notPlatformSurfaceableSchemas = mNotPlatformSurfaceableMap.get(prefix);
+        if (notPlatformSurfaceableSchemas == null) {
+            return true;
         }
-        return schemasNotPlatformSurfaceable;
+        return !notPlatformSurfaceableSchemas.contains(prefixedSchema);
     }
 
     /**
@@ -199,4 +222,14 @@
         mNotPlatformSurfaceableMap.clear();
         initialize();
     }
+
+    /**
+     * Adds a uri prefix to create a visibility store document's uri.
+     *
+     * @param uri Non-prefixed uri
+     * @return Prefixed uri
+     */
+    private static String addUriPrefix(String uri) {
+        return URI_PREFIX + uri;
+    }
 }
diff --git a/synced_jetpack_changeid.txt b/synced_jetpack_changeid.txt
index 57c48d8..5a7ab1d 100644
--- a/synced_jetpack_changeid.txt
+++ b/synced_jetpack_changeid.txt
@@ -1 +1 @@
-If5fd2bd705d5507d044706701a94b2e1496ef1df
+Ia04e81bb574831fa7e8a26c725e53133b39ee3ef
diff --git a/testing/coretests/src/android/app/appsearch/external/app/SetSchemaRequestTest.java b/testing/coretests/src/android/app/appsearch/external/app/SetSchemaRequestTest.java
index e03cea3..879aa09 100644
--- a/testing/coretests/src/android/app/appsearch/external/app/SetSchemaRequestTest.java
+++ b/testing/coretests/src/android/app/appsearch/external/app/SetSchemaRequestTest.java
@@ -16,28 +16,54 @@
 
 package android.app.appsearch;
 
+import static android.app.appsearch.AppSearchSchema.PropertyConfig.INDEXING_TYPE_PREFIXES;
+import static android.app.appsearch.AppSearchSchema.PropertyConfig.TOKENIZER_TYPE_PLAIN;
+
 import static com.google.common.truth.Truth.assertThat;
 
 import static org.testng.Assert.expectThrows;
 
+import android.util.ArrayMap;
+
 import org.junit.Test;
 
+import java.util.Collections;
+import java.util.Map;
+import java.util.Set;
+
 public class SetSchemaRequestTest {
 
     @Test
-    public void testInvalidSchemaReferences() {
+    public void testInvalidSchemaReferences_fromSystemUiVisibility() {
         IllegalArgumentException expected =
                 expectThrows(
                         IllegalArgumentException.class,
                         () ->
                                 new SetSchemaRequest.Builder()
-                                        .setSchemaTypeVisibilityForSystemUi(false, "InvalidSchema")
+                                        .setSchemaTypeVisibilityForSystemUi("InvalidSchema", false)
                                         .build());
         assertThat(expected).hasMessageThat().contains("referenced, but were not added");
     }
 
     @Test
-    public void testSchemaTypeVisibilityForSystemUi_Visible() {
+    public void testInvalidSchemaReferences_fromPackageVisibility() {
+        IllegalArgumentException expected =
+                expectThrows(
+                        IllegalArgumentException.class,
+                        () ->
+                                new SetSchemaRequest.Builder()
+                                        .setSchemaTypeVisibilityForPackage(
+                                                "InvalidSchema",
+                                                /*visible=*/ true,
+                                                new PackageIdentifier(
+                                                        "com.foo.package",
+                                                        /*certificate=*/ new byte[] {}))
+                                        .build());
+        assertThat(expected).hasMessageThat().contains("referenced, but were not added");
+    }
+
+    @Test
+    public void testSchemaTypeVisibilityForSystemUi_visible() {
         AppSearchSchema schema = new AppSearchSchema.Builder("Schema").build();
 
         // By default, the schema is visible.
@@ -47,19 +73,106 @@
         request =
                 new SetSchemaRequest.Builder()
                         .addSchema(schema)
-                        .setSchemaTypeVisibilityForSystemUi(true, "Schema")
+                        .setSchemaTypeVisibilityForSystemUi("Schema", true)
                         .build();
         assertThat(request.getSchemasNotPlatformSurfaceable()).isEmpty();
     }
 
     @Test
-    public void testSchemaTypeVisibilityForSystemUi_NotVisible() {
+    public void testSchemaTypeVisibilityForSystemUi_notVisible() {
         AppSearchSchema schema = new AppSearchSchema.Builder("Schema").build();
         SetSchemaRequest request =
                 new SetSchemaRequest.Builder()
                         .addSchema(schema)
-                        .setSchemaTypeVisibilityForSystemUi(false, "Schema")
+                        .setSchemaTypeVisibilityForSystemUi("Schema", false)
                         .build();
         assertThat(request.getSchemasNotPlatformSurfaceable()).containsExactly("Schema");
     }
+
+    @Test
+    public void testSchemaTypeVisibilityForPackage_visible() {
+        AppSearchSchema schema = new AppSearchSchema.Builder("Schema").build();
+
+        // By default, the schema is not visible.
+        SetSchemaRequest request = new SetSchemaRequest.Builder().addSchema(schema).build();
+        assertThat(request.getSchemasPackageAccessible()).isEmpty();
+
+        PackageIdentifier packageIdentifier =
+                new PackageIdentifier("com.package.foo", new byte[] {100});
+        Map<String, Set<PackageIdentifier>> expectedPackageVisibleMap = new ArrayMap<>();
+        expectedPackageVisibleMap.put("Schema", Collections.singleton(packageIdentifier));
+
+        request =
+                new SetSchemaRequest.Builder()
+                        .addSchema(schema)
+                        .setSchemaTypeVisibilityForPackage(
+                                "Schema", /*visible=*/ true, packageIdentifier)
+                        .build();
+        assertThat(request.getSchemasPackageAccessible())
+                .containsExactlyEntriesIn(expectedPackageVisibleMap);
+    }
+
+    @Test
+    public void testSchemaTypeVisibilityForPackage_notVisible() {
+        AppSearchSchema schema = new AppSearchSchema.Builder("Schema").build();
+
+        SetSchemaRequest request =
+                new SetSchemaRequest.Builder()
+                        .addSchema(schema)
+                        .setSchemaTypeVisibilityForPackage(
+                                "Schema",
+                                /*visible=*/ false,
+                                new PackageIdentifier(
+                                        "com.package.foo", /*certificate=*/ new byte[] {}))
+                        .build();
+        assertThat(request.getSchemasPackageAccessible()).isEmpty();
+    }
+
+    @Test
+    public void testSchemaTypeVisibilityForPackage_deduped() throws Exception {
+        AppSearchSchema schema = new AppSearchSchema.Builder("Schema").build();
+
+        PackageIdentifier packageIdentifier =
+                new PackageIdentifier("com.package.foo", new byte[] {100});
+        Map<String, Set<PackageIdentifier>> expectedPackageVisibleMap = new ArrayMap<>();
+        expectedPackageVisibleMap.put("Schema", Collections.singleton(packageIdentifier));
+
+        SetSchemaRequest request =
+                new SetSchemaRequest.Builder()
+                        .addSchema(schema)
+                        // Set it visible for "Schema"
+                        .setSchemaTypeVisibilityForPackage(
+                                "Schema", /*visible=*/ true, packageIdentifier)
+                        // Set it visible for "Schema" again, which should be a no-op
+                        .setSchemaTypeVisibilityForPackage(
+                                "Schema", /*visible=*/ true, packageIdentifier)
+                        .build();
+        assertThat(request.getSchemasPackageAccessible())
+                .containsExactlyEntriesIn(expectedPackageVisibleMap);
+    }
+
+    @Test
+    public void testSchemaTypeVisibilityForPackage_removed() throws Exception {
+        AppSearchSchema schema = new AppSearchSchema.Builder("Schema").build();
+
+        SetSchemaRequest request =
+                new SetSchemaRequest.Builder()
+                        .addSchema(schema)
+                        // First set it as visible
+                        .setSchemaTypeVisibilityForPackage(
+                                "Schema",
+                                /*visible=*/ true,
+                                new PackageIdentifier(
+                                        "com.package.foo", /*certificate=*/ new byte[] {100}))
+                        // Then make it not visible
+                        .setSchemaTypeVisibilityForPackage(
+                                "Schema",
+                                /*visible=*/ false,
+                                new PackageIdentifier(
+                                        "com.package.foo", /*certificate=*/ new byte[] {100}))
+                        .build();
+
+        // Nothing should be visible.
+        assertThat(request.getSchemasPackageAccessible()).isEmpty();
+    }
 }
diff --git a/testing/servicestests/src/com/android/server/appsearch/external/localstorage/AppSearchImplTest.java b/testing/servicestests/src/com/android/server/appsearch/external/localstorage/AppSearchImplTest.java
index f38def8..f36ed4b 100644
--- a/testing/servicestests/src/com/android/server/appsearch/external/localstorage/AppSearchImplTest.java
+++ b/testing/servicestests/src/com/android/server/appsearch/external/localstorage/AppSearchImplTest.java
@@ -58,22 +58,21 @@
     public void setUp() throws Exception {
         mAppSearchImpl = AppSearchImpl.create(mTemporaryFolder.newFolder());
 
-        AppSearchSchema visibilityAppSearchSchema =
+        AppSearchSchema visibilitySchema = VisibilityStore.SCHEMA;
+
+        // We need to rewrite the schema type to follow AppSearchImpl's prefixing scheme.
+        AppSearchSchema.Builder rewrittenVisibilitySchema =
                 new AppSearchSchema.Builder(
-                                VisibilityStore.DATABASE_NAME
-                                        + AppSearchImpl.DATABASE_DELIMITER
-                                        + VisibilityStore.SCHEMA_TYPE)
-                        .addProperty(
-                                new AppSearchSchema.PropertyConfig.Builder(
-                                                VisibilityStore.NOT_PLATFORM_SURFACEABLE_PROPERTY)
-                                        .setDataType(
-                                                AppSearchSchema.PropertyConfig.DATA_TYPE_STRING)
-                                        .setCardinality(
-                                                AppSearchSchema.PropertyConfig.CARDINALITY_REPEATED)
-                                        .build())
-                        .build();
+                        AppSearchImpl.createPrefix(
+                                        VisibilityStore.PACKAGE_NAME, VisibilityStore.DATABASE_NAME)
+                                + VisibilityStore.SCHEMA_TYPE);
+        List<AppSearchSchema.PropertyConfig> visibilityProperties =
+                visibilitySchema.getProperties();
+        for (AppSearchSchema.PropertyConfig property : visibilityProperties) {
+            rewrittenVisibilitySchema.addProperty(property);
+        }
         mVisibilitySchemaProto =
-                SchemaToProtoConverter.toSchemaTypeConfigProto(visibilityAppSearchSchema);
+                SchemaToProtoConverter.toSchemaTypeConfigProto(rewrittenVisibilitySchema.build());
     }
 
     /**
@@ -87,7 +86,7 @@
                 SchemaProto.newBuilder()
                         .addTypes(
                                 SchemaTypeConfigProto.newBuilder()
-                                        .setSchemaType("existingDatabase/Foo")
+                                        .setSchemaType("package$existingDatabase/Foo")
                                         .build());
 
         // Create a copy so we can modify it.
@@ -135,22 +134,25 @@
                         .build();
 
         AppSearchImpl.RewrittenSchemaResults rewrittenSchemaResults =
-                mAppSearchImpl.rewriteSchema("newDatabase", existingSchemaBuilder, newSchema);
+                mAppSearchImpl.rewriteSchema(
+                        AppSearchImpl.createPrefix("package", "newDatabase"),
+                        existingSchemaBuilder,
+                        newSchema);
 
         // We rewrote all the new types that were added. And nothing was removed.
-        assertThat(rewrittenSchemaResults.mRewrittenQualifiedTypes)
-                .containsExactly("newDatabase/Foo", "newDatabase/TestType");
-        assertThat(rewrittenSchemaResults.mDeletedQualifiedTypes).isEmpty();
+        assertThat(rewrittenSchemaResults.mRewrittenPrefixedTypes)
+                .containsExactly("package$newDatabase/Foo", "package$newDatabase/TestType");
+        assertThat(rewrittenSchemaResults.mDeletedPrefixedTypes).isEmpty();
 
         SchemaProto expectedSchema =
                 SchemaProto.newBuilder()
                         .addTypes(
                                 SchemaTypeConfigProto.newBuilder()
-                                        .setSchemaType("newDatabase/Foo")
+                                        .setSchemaType("package$newDatabase/Foo")
                                         .build())
                         .addTypes(
                                 SchemaTypeConfigProto.newBuilder()
-                                        .setSchemaType("newDatabase/TestType")
+                                        .setSchemaType("package$newDatabase/TestType")
                                         .addProperties(
                                                 PropertyConfigProto.newBuilder()
                                                         .setPropertyName("subject")
@@ -180,7 +182,8 @@
                                                         .setCardinality(
                                                                 PropertyConfigProto.Cardinality.Code
                                                                         .OPTIONAL)
-                                                        .setSchemaType("newDatabase/RefType")
+                                                        .setSchemaType(
+                                                                "package$newDatabase/RefType")
                                                         .build())
                                         .build())
                         .build();
@@ -199,7 +202,7 @@
                 SchemaProto.newBuilder()
                         .addTypes(
                                 SchemaTypeConfigProto.newBuilder()
-                                        .setSchemaType("existingDatabase/Foo")
+                                        .setSchemaType("package$existingDatabase/Foo")
                                         .build());
 
         SchemaProto newSchema =
@@ -208,12 +211,15 @@
                         .build();
 
         AppSearchImpl.RewrittenSchemaResults rewrittenSchemaResults =
-                mAppSearchImpl.rewriteSchema("existingDatabase", existingSchemaBuilder, newSchema);
+                mAppSearchImpl.rewriteSchema(
+                        AppSearchImpl.createPrefix("package", "existingDatabase"),
+                        existingSchemaBuilder,
+                        newSchema);
 
         // Nothing was removed, but the method did rewrite the type name.
-        assertThat(rewrittenSchemaResults.mRewrittenQualifiedTypes)
-                .containsExactly("existingDatabase/Foo");
-        assertThat(rewrittenSchemaResults.mDeletedQualifiedTypes).isEmpty();
+        assertThat(rewrittenSchemaResults.mRewrittenPrefixedTypes)
+                .containsExactly("package$existingDatabase/Foo");
+        assertThat(rewrittenSchemaResults.mDeletedPrefixedTypes).isEmpty();
 
         // Same schema since nothing was added.
         SchemaProto expectedSchema = existingSchemaBuilder.build();
@@ -231,7 +237,7 @@
                 SchemaProto.newBuilder()
                         .addTypes(
                                 SchemaTypeConfigProto.newBuilder()
-                                        .setSchemaType("existingDatabase/Foo")
+                                        .setSchemaType("package$existingDatabase/Foo")
                                         .build());
 
         SchemaProto newSchema =
@@ -240,21 +246,24 @@
                         .build();
 
         AppSearchImpl.RewrittenSchemaResults rewrittenSchemaResults =
-                mAppSearchImpl.rewriteSchema("existingDatabase", existingSchemaBuilder, newSchema);
+                mAppSearchImpl.rewriteSchema(
+                        AppSearchImpl.createPrefix("package", "existingDatabase"),
+                        existingSchemaBuilder,
+                        newSchema);
 
         // Bar type was rewritten, but Foo ended up being deleted since it wasn't included in the
         // new schema.
-        assertThat(rewrittenSchemaResults.mRewrittenQualifiedTypes)
-                .containsExactly("existingDatabase/Bar");
-        assertThat(rewrittenSchemaResults.mDeletedQualifiedTypes)
-                .containsExactly("existingDatabase/Foo");
+        assertThat(rewrittenSchemaResults.mRewrittenPrefixedTypes)
+                .containsExactly("package$existingDatabase/Bar");
+        assertThat(rewrittenSchemaResults.mDeletedPrefixedTypes)
+                .containsExactly("package$existingDatabase/Foo");
 
         // Same schema since nothing was added.
         SchemaProto expectedSchema =
                 SchemaProto.newBuilder()
                         .addTypes(
                                 SchemaTypeConfigProto.newBuilder()
-                                        .setSchemaType("existingDatabase/Bar")
+                                        .setSchemaType("package$existingDatabase/Bar")
                                         .build())
                         .build();
 
@@ -281,21 +290,22 @@
         DocumentProto expectedInsideDocument =
                 DocumentProto.newBuilder()
                         .setUri("inside-uri")
-                        .setSchema("databaseName/type")
-                        .setNamespace("databaseName/namespace")
+                        .setSchema("package$databaseName/type")
+                        .setNamespace("package$databaseName/namespace")
                         .build();
         DocumentProto expectedDocumentProto =
                 DocumentProto.newBuilder()
                         .setUri("uri")
-                        .setSchema("databaseName/type")
-                        .setNamespace("databaseName/namespace")
+                        .setSchema("package$databaseName/type")
+                        .setNamespace("package$databaseName/namespace")
                         .addProperties(
                                 PropertyProto.newBuilder()
                                         .addDocumentValues(expectedInsideDocument))
                         .build();
 
         DocumentProto.Builder actualDocument = documentProto.toBuilder();
-        mAppSearchImpl.addPrefixToDocument(actualDocument, "databaseName/");
+        mAppSearchImpl.addPrefixToDocument(
+                actualDocument, AppSearchImpl.createPrefix("package", "databaseName"));
         assertThat(actualDocument.build()).isEqualTo(expectedDocumentProto);
     }
 
@@ -304,14 +314,14 @@
         DocumentProto insideDocument =
                 DocumentProto.newBuilder()
                         .setUri("inside-uri")
-                        .setSchema("databaseName1/type")
-                        .setNamespace("databaseName2/namespace")
+                        .setSchema("package$databaseName1/type")
+                        .setNamespace("package$databaseName2/namespace")
                         .build();
         DocumentProto documentProto =
                 DocumentProto.newBuilder()
                         .setUri("uri")
-                        .setSchema("databaseName2/type")
-                        .setNamespace("databaseName3/namespace")
+                        .setSchema("package$databaseName2/type")
+                        .setNamespace("package$databaseName3/namespace")
                         .addProperties(PropertyProto.newBuilder().addDocumentValues(insideDocument))
                         .build();
 
@@ -321,7 +331,7 @@
                         .setSchema("type")
                         .setNamespace("namespace")
                         .build();
-        // Since we don't pass in "databaseName3/" as a prefix to remove, it stays on the Document.
+
         DocumentProto expectedDocumentProto =
                 DocumentProto.newBuilder()
                         .setUri("uri")
@@ -333,7 +343,7 @@
                         .build();
 
         DocumentProto.Builder actualDocument = documentProto.toBuilder();
-        mAppSearchImpl.removeDatabasesFromDocument(actualDocument);
+        mAppSearchImpl.removePrefixesFromDocument(actualDocument);
         assertThat(actualDocument.build()).isEqualTo(expectedDocumentProto);
     }
 
@@ -343,6 +353,7 @@
         List<AppSearchSchema> schemas =
                 Collections.singletonList(new AppSearchSchema.Builder("type").build());
         mAppSearchImpl.setSchema(
+                "package",
                 "database",
                 schemas,
                 /*schemasNotPlatformSurfaceable=*/ Collections.emptyList(),
@@ -358,7 +369,7 @@
                     new GenericDocument.Builder<>("uri" + i, "type")
                             .setNamespace("namespace")
                             .build();
-            mAppSearchImpl.putDocument("database", document);
+            mAppSearchImpl.putDocument("package", "database", document);
         }
 
         // Check optimize() will release 0 docs since there is no deletion.
@@ -368,7 +379,7 @@
         // delete 999 documents , we will reach the threshold to trigger optimize() in next
         // deletion.
         for (int i = 0; i < AppSearchImpl.OPTIMIZE_THRESHOLD_DOC_COUNT - 1; i++) {
-            mAppSearchImpl.remove("database", "namespace", "uri" + i);
+            mAppSearchImpl.remove("package", "database", "namespace", "uri" + i);
         }
 
         // optimize() still not be triggered since we are in the interval to call getOptimizeInfo()
@@ -382,7 +393,7 @@
                         < AppSearchImpl.OPTIMIZE_THRESHOLD_DOC_COUNT
                                 + AppSearchImpl.CHECK_OPTIMIZE_INTERVAL;
                 i++) {
-            mAppSearchImpl.remove("database", "namespace", "uri" + i);
+            mAppSearchImpl.remove("package", "database", "namespace", "uri" + i);
         }
 
         // Verify optimize() is triggered
@@ -399,6 +410,7 @@
         List<AppSearchSchema> schemas =
                 Collections.singletonList(new AppSearchSchema.Builder("type").build());
         mAppSearchImpl.setSchema(
+                "package",
                 "database",
                 schemas,
                 /*schemasNotPlatformSurfaceable=*/ Collections.emptyList(),
@@ -407,13 +419,16 @@
         // Insert document
         GenericDocument document =
                 new GenericDocument.Builder<>("uri", "type").setNamespace("namespace").build();
-        mAppSearchImpl.putDocument("database", document);
+        mAppSearchImpl.putDocument("package", "database", document);
 
         // Rewrite SearchSpec
-        mAppSearchImpl.rewriteSearchSpecForDatabasesLocked(
-                searchSpecProto, Collections.singleton("database"));
-        assertThat(searchSpecProto.getSchemaTypeFiltersList()).containsExactly("database/type");
-        assertThat(searchSpecProto.getNamespaceFiltersList()).containsExactly("database/namespace");
+        mAppSearchImpl.rewriteSearchSpecForPrefixesLocked(
+                searchSpecProto,
+                Collections.singleton(AppSearchImpl.createPrefix("package", "database")));
+        assertThat(searchSpecProto.getSchemaTypeFiltersList())
+                .containsExactly("package$database/type");
+        assertThat(searchSpecProto.getNamespaceFiltersList())
+                .containsExactly("package$database/namespace");
     }
 
     @Test
@@ -426,11 +441,13 @@
                         new AppSearchSchema.Builder("typeA").build(),
                         new AppSearchSchema.Builder("typeB").build());
         mAppSearchImpl.setSchema(
+                "package",
                 "database1",
                 schemas,
                 /*schemasNotPlatformSurfaceable=*/ Collections.emptyList(),
                 /*forceOverride=*/ false);
         mAppSearchImpl.setSchema(
+                "package",
                 "database2",
                 schemas,
                 /*schemasNotPlatformSurfaceable=*/ Collections.emptyList(),
@@ -439,27 +456,34 @@
         // Insert documents
         GenericDocument document1 =
                 new GenericDocument.Builder<>("uri", "typeA").setNamespace("namespace").build();
-        mAppSearchImpl.putDocument("database1", document1);
+        mAppSearchImpl.putDocument("package", "database1", document1);
 
         GenericDocument document2 =
                 new GenericDocument.Builder<>("uri", "typeB").setNamespace("namespace").build();
-        mAppSearchImpl.putDocument("database2", document2);
+        mAppSearchImpl.putDocument("package", "database2", document2);
 
         // Rewrite SearchSpec
-        mAppSearchImpl.rewriteSearchSpecForDatabasesLocked(
-                searchSpecProto, ImmutableSet.of("database1", "database2"));
+        mAppSearchImpl.rewriteSearchSpecForPrefixesLocked(
+                searchSpecProto,
+                ImmutableSet.of(
+                        AppSearchImpl.createPrefix("package", "database1"),
+                        AppSearchImpl.createPrefix("package", "database2")));
         assertThat(searchSpecProto.getSchemaTypeFiltersList())
                 .containsExactly(
-                        "database1/typeA", "database1/typeB", "database2/typeA", "database2/typeB");
+                        "package$database1/typeA",
+                        "package$database1/typeB",
+                        "package$database2/typeA",
+                        "package$database2/typeB");
         assertThat(searchSpecProto.getNamespaceFiltersList())
-                .containsExactly("database1/namespace", "database2/namespace");
+                .containsExactly("package$database1/namespace", "package$database2/namespace");
     }
 
     @Test
     public void testQueryEmptyDatabase() throws Exception {
         SearchSpec searchSpec =
                 new SearchSpec.Builder().setTermMatch(TermMatchType.Code.PREFIX_VALUE).build();
-        SearchResultPage searchResultPage = mAppSearchImpl.query("EmptyDatabase", "", searchSpec);
+        SearchResultPage searchResultPage =
+                mAppSearchImpl.query("package", "EmptyDatabase", "", searchSpec);
         assertThat(searchResultPage.getResults()).isEmpty();
     }
 
@@ -467,7 +491,7 @@
     public void testGlobalQueryEmptyDatabase() throws Exception {
         SearchSpec searchSpec =
                 new SearchSpec.Builder().setTermMatch(TermMatchType.Code.PREFIX_VALUE).build();
-        SearchResultPage searchResultPage = mAppSearchImpl.query("EmptyDatabase", "", searchSpec);
+        SearchResultPage searchResultPage = mAppSearchImpl.globalQuery("", searchSpec);
         assertThat(searchResultPage.getResults()).isEmpty();
     }
 
@@ -478,17 +502,17 @@
                         .addSchemaType("FakeType")
                         .setTermMatch(TermMatchType.Code.PREFIX_VALUE)
                         .build();
-        mAppSearchImpl.removeByQuery("EmptyDatabase", "", searchSpec);
+        mAppSearchImpl.removeByQuery("package", "EmptyDatabase", "", searchSpec);
 
         searchSpec =
                 new SearchSpec.Builder()
                         .addNamespace("FakeNamespace")
                         .setTermMatch(TermMatchType.Code.PREFIX_VALUE)
                         .build();
-        mAppSearchImpl.removeByQuery("EmptyDatabase", "", searchSpec);
+        mAppSearchImpl.removeByQuery("package", "EmptyDatabase", "", searchSpec);
 
         searchSpec = new SearchSpec.Builder().setTermMatch(TermMatchType.Code.PREFIX_VALUE).build();
-        mAppSearchImpl.removeByQuery("EmptyDatabase", "", searchSpec);
+        mAppSearchImpl.removeByQuery("package", "EmptyDatabase", "", searchSpec);
     }
 
     @Test
@@ -497,6 +521,7 @@
                 Collections.singletonList(new AppSearchSchema.Builder("Email").build());
         // Set schema Email to AppSearch database1
         mAppSearchImpl.setSchema(
+                "package",
                 "database1",
                 schemas,
                 /*schemasNotPlatformSurfaceable=*/ Collections.emptyList(),
@@ -506,7 +531,8 @@
         SchemaProto expectedProto =
                 SchemaProto.newBuilder()
                         .addTypes(
-                                SchemaTypeConfigProto.newBuilder().setSchemaType("database1/Email"))
+                                SchemaTypeConfigProto.newBuilder()
+                                        .setSchemaType("package$database1/Email"))
                         .build();
 
         List<SchemaTypeConfigProto> expectedTypes = new ArrayList<>();
@@ -518,7 +544,9 @@
 
     @Test
     public void testSetSchema_existingSchemaRetainsVisibilitySetting() throws Exception {
+        String prefix = AppSearchImpl.createPrefix("package", "database");
         mAppSearchImpl.setSchema(
+                "package",
                 "database",
                 Collections.singletonList(new AppSearchSchema.Builder("schema1").build()),
                 /*schemasNotPlatformSurfaceable=*/ Collections.singletonList("schema1"),
@@ -528,11 +556,12 @@
         assertThat(
                         mAppSearchImpl
                                 .getVisibilityStoreLocked()
-                                .getSchemasNotPlatformSurfaceable("database"))
-                .containsExactly("database/schema1");
+                                .isSchemaPlatformSurfaceable(prefix, prefix + "schema1"))
+                .isFalse();
 
         // Add a new schema, and include the already-existing "schema1"
         mAppSearchImpl.setSchema(
+                "package",
                 "database",
                 ImmutableList.of(
                         new AppSearchSchema.Builder("schema1").build(),
@@ -545,8 +574,13 @@
         assertThat(
                         mAppSearchImpl
                                 .getVisibilityStoreLocked()
-                                .getSchemasNotPlatformSurfaceable("database"))
-                .containsExactly("database/schema1");
+                                .isSchemaPlatformSurfaceable(prefix, prefix + "schema1"))
+                .isFalse();
+        assertThat(
+                        mAppSearchImpl
+                                .getVisibilityStoreLocked()
+                                .isSchemaPlatformSurfaceable(prefix, prefix + "schema2"))
+                .isTrue();
     }
 
     @Test
@@ -557,6 +591,7 @@
                         new AppSearchSchema.Builder("Document").build());
         // Set schema Email and Document to AppSearch database1
         mAppSearchImpl.setSchema(
+                "package",
                 "database1",
                 schemas,
                 /*schemasNotPlatformSurfaceable=*/ Collections.emptyList(),
@@ -566,10 +601,11 @@
         SchemaProto expectedProto =
                 SchemaProto.newBuilder()
                         .addTypes(
-                                SchemaTypeConfigProto.newBuilder().setSchemaType("database1/Email"))
+                                SchemaTypeConfigProto.newBuilder()
+                                        .setSchemaType("package$database1/Email"))
                         .addTypes(
                                 SchemaTypeConfigProto.newBuilder()
-                                        .setSchemaType("database1/Document"))
+                                        .setSchemaType("package$database1/Document"))
                         .build();
 
         // Check both schema Email and Document saved correctly.
@@ -587,15 +623,17 @@
                         AppSearchException.class,
                         () ->
                                 mAppSearchImpl.setSchema(
+                                        "package",
                                         "database1",
                                         finalSchemas,
                                         /*schemasNotPlatformSurfaceable=*/ Collections.emptyList(),
                                         /*forceOverride=*/ false));
         assertThat(e).hasMessageThat().contains("Schema is incompatible");
-        assertThat(e).hasMessageThat().contains("Deleted types: [database1/Document]");
+        assertThat(e).hasMessageThat().contains("Deleted types: [package$database1/Document]");
 
         // ForceOverride to delete.
         mAppSearchImpl.setSchema(
+                "package",
                 "database1",
                 finalSchemas,
                 /*schemasNotPlatformSurfaceable=*/ Collections.emptyList(),
@@ -605,7 +643,8 @@
         expectedProto =
                 SchemaProto.newBuilder()
                         .addTypes(
-                                SchemaTypeConfigProto.newBuilder().setSchemaType("database1/Email"))
+                                SchemaTypeConfigProto.newBuilder()
+                                        .setSchemaType("package$database1/Email"))
                         .build();
 
         expectedTypes = new ArrayList<>();
@@ -625,11 +664,13 @@
 
         // Set schema Email and Document to AppSearch database1 and 2
         mAppSearchImpl.setSchema(
+                "package",
                 "database1",
                 schemas,
                 /*schemasNotPlatformSurfaceable=*/ Collections.emptyList(),
                 /*forceOverride=*/ false);
         mAppSearchImpl.setSchema(
+                "package",
                 "database2",
                 schemas,
                 /*schemasNotPlatformSurfaceable=*/ Collections.emptyList(),
@@ -639,15 +680,17 @@
         SchemaProto expectedProto =
                 SchemaProto.newBuilder()
                         .addTypes(
-                                SchemaTypeConfigProto.newBuilder().setSchemaType("database1/Email"))
+                                SchemaTypeConfigProto.newBuilder()
+                                        .setSchemaType("package$database1/Email"))
                         .addTypes(
                                 SchemaTypeConfigProto.newBuilder()
-                                        .setSchemaType("database1/Document"))
-                        .addTypes(
-                                SchemaTypeConfigProto.newBuilder().setSchemaType("database2/Email"))
+                                        .setSchemaType("package$database1/Document"))
                         .addTypes(
                                 SchemaTypeConfigProto.newBuilder()
-                                        .setSchemaType("database2/Document"))
+                                        .setSchemaType("package$database2/Email"))
+                        .addTypes(
+                                SchemaTypeConfigProto.newBuilder()
+                                        .setSchemaType("package$database2/Document"))
                         .build();
 
         // Check Email and Document is saved in database 1 and 2 correctly.
@@ -660,6 +703,7 @@
         // Save only Email to database1 this time.
         schemas = Collections.singletonList(new AppSearchSchema.Builder("Email").build());
         mAppSearchImpl.setSchema(
+                "package",
                 "database1",
                 schemas,
                 /*schemasNotPlatformSurfaceable=*/ Collections.emptyList(),
@@ -670,12 +714,14 @@
         expectedProto =
                 SchemaProto.newBuilder()
                         .addTypes(
-                                SchemaTypeConfigProto.newBuilder().setSchemaType("database1/Email"))
-                        .addTypes(
-                                SchemaTypeConfigProto.newBuilder().setSchemaType("database2/Email"))
+                                SchemaTypeConfigProto.newBuilder()
+                                        .setSchemaType("package$database1/Email"))
                         .addTypes(
                                 SchemaTypeConfigProto.newBuilder()
-                                        .setSchemaType("database2/Document"))
+                                        .setSchemaType("package$database2/Email"))
+                        .addTypes(
+                                SchemaTypeConfigProto.newBuilder()
+                                        .setSchemaType("package$database2/Document"))
                         .build();
 
         // Check nothing changed in database2.
@@ -688,7 +734,9 @@
 
     @Test
     public void testRemoveSchema_removedFromVisibilityStore() throws Exception {
+        String prefix = AppSearchImpl.createPrefix("package", "database");
         mAppSearchImpl.setSchema(
+                "package",
                 "database",
                 Collections.singletonList(new AppSearchSchema.Builder("schema1").build()),
                 /*schemasNotPlatformSurfaceable=*/ Collections.singletonList("schema1"),
@@ -698,11 +746,12 @@
         assertThat(
                         mAppSearchImpl
                                 .getVisibilityStoreLocked()
-                                .getSchemasNotPlatformSurfaceable("database"))
-                .containsExactly("database/schema1");
+                                .isSchemaPlatformSurfaceable(prefix, prefix + "schema1"))
+                .isFalse();
 
         // Remove "schema1" by force overriding
         mAppSearchImpl.setSchema(
+                "package",
                 "database",
                 Collections.emptyList(),
                 /*schemasNotPlatformSurfaceable=*/ Collections.emptyList(),
@@ -712,12 +761,13 @@
         assertThat(
                         mAppSearchImpl
                                 .getVisibilityStoreLocked()
-                                .getSchemasNotPlatformSurfaceable("database"))
-                .isEmpty();
+                                .isSchemaPlatformSurfaceable(prefix, prefix + "schema1"))
+                .isTrue();
 
         // Add "schema1" back, it gets default visibility settings which means it's not platform
         // hidden.
         mAppSearchImpl.setSchema(
+                "package",
                 "database",
                 Collections.singletonList(new AppSearchSchema.Builder("schema1").build()),
                 /*schemasNotPlatformSurfaceable=*/ Collections.emptyList(),
@@ -725,13 +775,15 @@
         assertThat(
                         mAppSearchImpl
                                 .getVisibilityStoreLocked()
-                                .getSchemasNotPlatformSurfaceable("database"))
-                .isEmpty();
+                                .isSchemaPlatformSurfaceable(prefix, prefix + "schema1"))
+                .isTrue();
     }
 
     @Test
     public void testSetSchema_defaultPlatformVisible() throws Exception {
+        String prefix = AppSearchImpl.createPrefix("package", "database");
         mAppSearchImpl.setSchema(
+                "package",
                 "database",
                 Collections.singletonList(new AppSearchSchema.Builder("Schema").build()),
                 /*schemasNotPlatformSurfaceable=*/ Collections.emptyList(),
@@ -739,13 +791,15 @@
         assertThat(
                         mAppSearchImpl
                                 .getVisibilityStoreLocked()
-                                .getSchemasNotPlatformSurfaceable("database"))
-                .isEmpty();
+                                .isSchemaPlatformSurfaceable(prefix, prefix + "Schema"))
+                .isTrue();
     }
 
     @Test
     public void testSetSchema_platformHidden() throws Exception {
+        String prefix = AppSearchImpl.createPrefix("package", "database");
         mAppSearchImpl.setSchema(
+                "package",
                 "database",
                 Collections.singletonList(new AppSearchSchema.Builder("Schema").build()),
                 /*schemasNotPlatformSurfaceable=*/ Collections.singletonList("Schema"),
@@ -753,47 +807,60 @@
         assertThat(
                         mAppSearchImpl
                                 .getVisibilityStoreLocked()
-                                .getSchemasNotPlatformSurfaceable("database"))
-                .containsExactly("database/Schema");
+                                .isSchemaPlatformSurfaceable(prefix, prefix + "Schema"))
+                .isFalse();
     }
 
     @Test
     public void testHasSchemaType() throws Exception {
         // Nothing exists yet
-        assertThat(mAppSearchImpl.hasSchemaTypeLocked("database", "Schema")).isFalse();
+        assertThat(mAppSearchImpl.hasSchemaTypeLocked("package", "database", "Schema")).isFalse();
 
         mAppSearchImpl.setSchema(
+                "package",
                 "database",
                 Collections.singletonList(new AppSearchSchema.Builder("Schema").build()),
                 /*schemasNotPlatformSurfaceable=*/ Collections.emptyList(),
                 /*forceOverride=*/ false);
-        assertThat(mAppSearchImpl.hasSchemaTypeLocked("database", "Schema")).isTrue();
+        assertThat(mAppSearchImpl.hasSchemaTypeLocked("package", "database", "Schema")).isTrue();
 
-        assertThat(mAppSearchImpl.hasSchemaTypeLocked("database", "UnknownSchema")).isFalse();
+        assertThat(mAppSearchImpl.hasSchemaTypeLocked("package", "database", "UnknownSchema"))
+                .isFalse();
     }
 
     @Test
     public void testGetDatabases() throws Exception {
         // No client databases exist yet, but the VisibilityStore's does
-        assertThat(mAppSearchImpl.getDatabasesLocked())
-                .containsExactly(VisibilityStore.DATABASE_NAME);
+        assertThat(mAppSearchImpl.getPrefixesLocked())
+                .containsExactly(
+                        AppSearchImpl.createPrefix(
+                                VisibilityStore.PACKAGE_NAME, VisibilityStore.DATABASE_NAME));
 
         // Has database1
         mAppSearchImpl.setSchema(
+                "package",
                 "database1",
                 Collections.singletonList(new AppSearchSchema.Builder("schema").build()),
                 /*schemasNotPlatformSurfaceable=*/ Collections.emptyList(),
                 /*forceOverride=*/ false);
-        assertThat(mAppSearchImpl.getDatabasesLocked())
-                .containsExactly(VisibilityStore.DATABASE_NAME, "database1");
+        assertThat(mAppSearchImpl.getPrefixesLocked())
+                .containsExactly(
+                        AppSearchImpl.createPrefix(
+                                VisibilityStore.PACKAGE_NAME, VisibilityStore.DATABASE_NAME),
+                        AppSearchImpl.createPrefix("package", "database1"));
 
         // Has both databases
         mAppSearchImpl.setSchema(
+                "package",
                 "database2",
                 Collections.singletonList(new AppSearchSchema.Builder("schema").build()),
                 /*schemasNotPlatformSurfaceable=*/ Collections.emptyList(),
                 /*forceOverride=*/ false);
-        assertThat(mAppSearchImpl.getDatabasesLocked())
-                .containsExactly(VisibilityStore.DATABASE_NAME, "database1", "database2");
+        assertThat(mAppSearchImpl.getPrefixesLocked())
+                .containsExactly(
+                        AppSearchImpl.createPrefix(
+                                VisibilityStore.PACKAGE_NAME, VisibilityStore.DATABASE_NAME),
+                        AppSearchImpl.createPrefix("package", "database1"),
+                        AppSearchImpl.createPrefix("package", "database2"));
     }
 }
diff --git a/testing/servicestests/src/com/android/server/appsearch/external/localstorage/VisibilityStoreTest.java b/testing/servicestests/src/com/android/server/appsearch/external/localstorage/VisibilityStoreTest.java
index a1f575a..415c1f5 100644
--- a/testing/servicestests/src/com/android/server/appsearch/external/localstorage/VisibilityStoreTest.java
+++ b/testing/servicestests/src/com/android/server/appsearch/external/localstorage/VisibilityStoreTest.java
@@ -18,13 +18,14 @@
 
 import static com.google.common.truth.Truth.assertThat;
 
+import com.google.common.collect.ImmutableSet;
+
 import org.junit.Before;
 import org.junit.Rule;
 import org.junit.Test;
 import org.junit.rules.TemporaryFolder;
 
 import java.util.Collections;
-import java.util.Set;
 
 public class VisibilityStoreTest {
 
@@ -38,22 +39,78 @@
         mVisibilityStore = mAppSearchImpl.getVisibilityStoreLocked();
     }
 
+    /**
+     * Make sure that we don't conflict with any special characters that AppSearchImpl has reserved.
+     */
+    @Test
+    public void testValidPackageName() {
+        assertThat(VisibilityStore.PACKAGE_NAME)
+                .doesNotContain(
+                        "" + AppSearchImpl.PACKAGE_DELIMITER); // Convert the chars to CharSequences
+        assertThat(VisibilityStore.PACKAGE_NAME)
+                .doesNotContain(
+                        ""
+                                + AppSearchImpl
+                                        .DATABASE_DELIMITER); // Convert the chars to CharSequences
+    }
+
+    /**
+     * Make sure that we don't conflict with any special characters that AppSearchImpl has reserved.
+     */
+    @Test
+    public void testValidDatabaseName() {
+        assertThat(VisibilityStore.DATABASE_NAME)
+                .doesNotContain(
+                        "" + AppSearchImpl.PACKAGE_DELIMITER); // Convert the chars to CharSequences
+        assertThat(VisibilityStore.DATABASE_NAME)
+                .doesNotContain(
+                        ""
+                                + AppSearchImpl
+                                        .DATABASE_DELIMITER); // Convert the chars to CharSequences
+    }
+
     @Test
     public void testSetVisibility() throws Exception {
         mVisibilityStore.setVisibility(
-                "database", /*schemasNotPlatformSurfaceable=*/ Set.of("schema1", "schema2"));
-        assertThat(mVisibilityStore.getSchemasNotPlatformSurfaceable("database"))
-                .containsExactly("schema1", "schema2");
+                "prefix",
+                /*schemasNotPlatformSurfaceable=*/ ImmutableSet.of(
+                        "prefix/schema1", "prefix/schema2"));
+        assertThat(mVisibilityStore.isSchemaPlatformSurfaceable("prefix", "prefix/schema1"))
+                .isFalse();
+        assertThat(mVisibilityStore.isSchemaPlatformSurfaceable("prefix", "prefix/schema2"))
+                .isFalse();
 
         // New .setVisibility() call completely overrides previous visibility settings. So
-        // "schema1" isn't preserved.
+        // "schema2" isn't preserved.
         mVisibilityStore.setVisibility(
-                "database", /*schemasNotPlatformSurfaceable=*/ Set.of("schema1", "schema3"));
-        assertThat(mVisibilityStore.getSchemasNotPlatformSurfaceable("database"))
-                .containsExactly("schema1", "schema3");
+                "prefix",
+                /*schemasNotPlatformSurfaceable=*/ ImmutableSet.of(
+                        "prefix/schema1", "prefix/schema3"));
+        assertThat(mVisibilityStore.isSchemaPlatformSurfaceable("prefix", "prefix/schema1"))
+                .isFalse();
+        assertThat(mVisibilityStore.isSchemaPlatformSurfaceable("prefix", "prefix/schema2"))
+                .isTrue();
+        assertThat(mVisibilityStore.isSchemaPlatformSurfaceable("prefix", "prefix/schema3"))
+                .isFalse();
 
         mVisibilityStore.setVisibility(
-                "database", /*schemasNotPlatformSurfaceable=*/ Collections.emptySet());
-        assertThat(mVisibilityStore.getSchemasNotPlatformSurfaceable("database")).isEmpty();
+                "prefix", /*schemasNotPlatformSurfaceable=*/ Collections.emptySet());
+        assertThat(mVisibilityStore.isSchemaPlatformSurfaceable("prefix", "prefix/schema1"))
+                .isTrue();
+        assertThat(mVisibilityStore.isSchemaPlatformSurfaceable("prefix", "prefix/schema2"))
+                .isTrue();
+        assertThat(mVisibilityStore.isSchemaPlatformSurfaceable("prefix", "prefix/schema3"))
+                .isTrue();
+    }
+
+    @Test
+    public void testEmptyPrefix() throws Exception {
+        mVisibilityStore.setVisibility(
+                /*prefix=*/ "",
+                /*schemasNotPlatformSurfaceable=*/ ImmutableSet.of("schema1", "schema2"));
+        assertThat(mVisibilityStore.isSchemaPlatformSurfaceable(/*prefix=*/ "", "schema1"))
+                .isFalse();
+        assertThat(mVisibilityStore.isSchemaPlatformSurfaceable(/*prefix=*/ "", "schema2"))
+                .isFalse();
     }
 }