Características del lenguaje para implementar el álgebra relacional

Question

He intentado codificar un álgebra relacional en Scala (que según mi conocimiento tiene uno de los sistemas de tipos más avanzados) y simplemente no encuentro una manera de llegar a donde quiero .

Como no soy tan experimentado en el campo académico del diseño de lenguaje de programación, realmente no sé qué función buscar.

Entonces, ¿qué características del lenguaje se necesitarían, y qué idioma tienen esas características, para implementar un álgebra relacional estáticamente verificada?

Algunos de los requisitos: A Tuple es una función que asigna nombres desde un conjunto estáticamente definido de nombres válidos para la tupla en cuestión a valores del tipo especificado por el nombre. Permite llamar a este tipo de nombre establecer el dominio.

una relación es un conjunto de tuplas con el mismo dominio de tal manera que el rango de cualquier tupla es uniqe en el Conjunto

Hasta ahora el modelo eaisly puede ser modelado en Scala simplemente por

trait Tuple 
trait Relation[T<Tuple] extends Set[T] 

El vals, vars y defs en Tuple es el conjunto de nombre de tipo definido anteriormente. Pero no debería haber dos defs en Tuple con el mismo nombre. También vars y definiciones impuras probablemente también deberían estar restringidas.

Ahora viene la parte difícil:

Una combinación de dos relaciones es una relación donde el dominio de las tuplas es la unión de los dominios de las tuplas operandos. De modo que solo se conservan las tuplas que tienen los mismos rangos para la intersección de sus dominios.

def join(r1:Relation[T1],r2:Relation[T2]):Relation[T1 with T2] 

deberían hacer el truco.

Una proyección de una relación es una relación en la que el dominio de las tuplas es un subconjunto del dominio de tuplas de operandos.

def project[T2](r:Relation[T],?1):Relation[T2>:T] 

Aquí es donde no estoy seguro de si es posible encontrar una solución. ¿Qué piensas? ¿Qué características del lenguaje se necesitan para definir el proyecto?

Implicado por encima del curso es que la API tiene que ser utilizable. Capas y capas de texto repetitivo no son aceptables.

Answer 1

Lo que usted solicita es poder definir estructuralmente un tipo como diferencia de otros dos tipos (la relación original y la definición de proyección). Honestamente, no puedo pensar en ningún lenguaje que te permita hacer eso. Los tipos pueden ser estructuralmente acumulativos (A with B) ya que A with B es un subtipo estructural de A y B. Sin embargo, si lo piensa, una operación de tipo A less B sería en realidad un supertipo de A, en lugar de un subtipo. Está pidiendo una relación de tipeo arbitraria y contravariante en tipos covariantes naturales. Ni siquiera se ha demostrado que ese tipo de cosas son sólidas con los tipos existenciales nominales, y mucho menos con los tipos estructurales de puntos de declaración.

He trabajado en este tipo de modelado antes, y la ruta que tomé fue a la restricción proyecciones a uno de los tres dominios: P == T, P == {F} where F in T, P == {$_1} where $_1 anonymous. El primero es donde la proyección es equivalente al tipo de entrada, lo que significa que es un no-op (SELECT *). El segundo es decir que la proyección es un solo campo contenido dentro del tipo de entrada. El tercero es el complicado. Está diciendo que está permitiendo la declaración de algún tipo anónimo $_1 que no tiene relación estática con el tipo de entrada. Es de suponer que consistirá en campos que deleguen en el tipo de entrada, pero no podemos hacer cumplir eso. Esta es aproximadamente la estrategia que toma LINQ.

Lo siento, no podría ser más útil. Ojalá fuera posible hacer lo que me pides, abriría muchas posibilidades muy buenas.

Answer 2

Tutorial D es tan simple y tan estrechamente alineado con la teoría relacional que un lenguaje puede tener.

Answer 3

Creo que me he decidido por utilizar las instalaciones normales para la recopilación de mapas para la parte del proyecto. El cliente solo especifica una función [T<:Tuple](t:T) => P

Con algunos trucos de Java para llegar a la clase de P, debería ser capaz de usar la reflexión para implementar la lógica de consulta.

Para la unión probablemente use DynamicProxy para implementar la función de mapeo.

Como una bonificación, podría obtener la API para poder usarla con la sintaxis especial de Scalas.

Answer 4

HaskellDB tiene algunas ideas sobre cómo crear álgebra relacional de tipo seguro DSL, puede que le resulte útil.

Answer 5

Tal vez encuentre algo bajo útil a partir de aquí: http://research.microsoft.com/en-us/um/people/simonpj/papers/list-comp/list-comp.pdf

que muestra cómo agregar "grupo por" y "ordenar por" a las listas por comprensión.