Tengo un prefijo trie. ¿Cuál es el esquema recomendado para representar esta estructura en una base de datos relacional? Necesito la coincidencia de subcadenas para seguir siendo eficiente.¿Cómo se almacena un trie en una base de datos relacional?
¿Qué tal el diseño Materialized Path?
CREATE TABLE trie (
path VARCHAR(<maxdepth>) PRIMARY KEY,
...other attributes of a tree node...
);
Para almacenar una palabra como "stackoverflow":
INSERT INTO trie (path) VALUES
('s'), ('st'), ('sta'), ('stac'), ('stack'),
('stacko'), ('stackov'), ('stackove'), ('stackover'),
('stackover'), ('stackoverf'), ('stackoverflo'),
('stackoverflow');
El camino materializado en el árbol es la secuencia prefijada de sí mismo caracteres. Esto también forma la clave principal. El tamaño de la columna varchar es la profundidad máxima de trie que desea almacenar.
No se me ocurre nada más simple y directo que eso, y conserva el almacenamiento y la búsqueda de cadenas eficientes.
El enlace redirige a nada de interés. Aquí hay una versión archivada: http://web.archive.org/web/20071019044908/http://www.dbazine.com/oracle/or-articles/tropashko4 – Howie
@Howie, gracias, respondí esto hace 5,5 años, por lo que no es una sorpresa que algunos enlaces se vuelvan obsoletos. –
Puede dar un ejemplo de cómo va a consultar esta tabla para decir "st" y hay más palabras como "stackoverflowone" – zengr
¿Alguna de sus entidades tiene alguna relación con alguna otra? Si no, es decir, no relacional, una tabla hash con una serialización lo haría.
Sí, trie no tree. Ver http://en.wikipedia.org/wiki/Trie – dkretz
¿Está almacenando y recuperando el trie de/desde DB para ser utilizado en su código? Porque para la búsqueda de bases de datos hay herramientas integradas, como la indexación de texto completo (basada en principios similares) –