Dopuszczalne heurystyki można również wyprowadzić z kosztu rozwiązania podproblemu danego problemu. Na przykład rysunek 3 podproblem instancji 8-puzzli . Podproblem polega na umieszczeniu płytek 1, 2, 3, 4 i półwyrobu we właściwych pozycjach. Oczywiście koszt optymalnego rozwiązania tego podproblemu jest dolną granicą kosztu całego problemu. W niektórych przypadkach okazuje się to dokładniejsze niż odległość Manhattanu.
Ideą baz danych wzorców jest przechowywanie tych dokładnych kosztów rozwiązania dla każdego możliwego wystąpienia podproblemu – w naszym przykładzie, każdej możliwej konfiguracji czterech płytek i pustego miejsca. (W bazie danych będzie 9 x8x7 x 6 x 5 = 15 120 wzorców. Tożsamości pozostałych czterech płytek są nieistotne dla celów rozwiązania podproblemu, ale ruchy tych płytek wliczają się do kosztu rozwiązania podproblemu.) Następnie obliczamy dopuszczalną heurystyczną bazę hdDB dla każdego stanu napotkanego podczas wyszukiwania, po prostu wyszukując odpowiednią konfigurację podproblemu w bazie danych. Sama baza danych jest konstruowana poprzez wyszukiwanie wstecz od celu i rejestrowanie kosztu każdego nowego napotkanego wzorca; koszt tych poszukiwań jest amortyzowany w kolejnych wystąpieniach problemów, a więc ma sens, jeśli oczekujemy, że zostaniemy poproszeni o rozwiązanie wielu problemów. Wybór płytek 1-2-3-4 pasujących do blanku jest dość arbitralny; moglibyśmy również skonstruować bazy danych dla 5-6-7-8, dla 2-4-6-8 i tak dalej. Każda baza danych daje dopuszczalną heurystykę, a te heurystyki można łączyć, jak wyjaśniono wcześniej, przyjmując maksymalną wartość. Połączona heurystyka tego rodzaju jest znacznie dokładniejsza niż odległość Manhattanu; liczba węzłów generowanych podczas rozwiązywania przypadkowych 15-zagadek może zostać zmniejszona o współczynnik 1000. Jednak z każdą dodatkową bazą danych maleją zyski i rosną koszty pamięci i obliczeń. Można się zastanawiać, czy można dodać heurystyki uzyskane z bazy danych 1-2-3-4 i 5-6-7-8, ponieważ te dwa podproblemy wydają się nie pokrywać. Czy to nadal dałoby dopuszczalną heurystykę? Odpowiedź brzmi nie, ponieważ rozwiązania podproblemu 1-2-3-4 i podproblemu 5-6-7-8 dla danego stanu prawie na pewno podzielą niektóre ruchy – jest mało prawdopodobne, aby 1-2-3-4 można przenieść na miejsce bez dotykania 5-6-7-8 i na odwrót. Ale co, jeśli nie liczymy tych ruchów – co, jeśli nie abstrahujemy pozostałych płytek do gwiazd, ale raczej sprawimy, że znikną? Oznacza to, że rejestrujemy nie całkowity koszt rozwiązania podproblemu 1-2-3-4, ale tylko liczbę ruchów obejmujących 1-2-3-4. Wtedy suma tych dwóch kosztów jest nadal dolną granicą kosztu rozwiązania całego problemu. To jest idea rozłącznych baz danych wzorców. Dzięki takim bazom danych możliwe jest rozwiązywanie przypadkowych 15-zagadek w ciągu kilku milisekund — liczba generowanych węzłów jest zmniejszona o współczynnik 10 000 w porównaniu z wykorzystaniem odległości Manhattan. W przypadku 24 zagadek można uzyskać przyspieszenie rzędu miliona. Rozłączne bazy danych wzorców sprawdzają się w przypadku łamigłówek z przesuwanymi płytkami, ponieważ problem można podzielić w taki sposób, że każdy ruch wpływa tylko na jeden podproblem – ponieważ tylko jedna płytka jest przesuwana na raz.