Les requêtes SQL (de base) sont-elles sémantiquement équivalentes aux fonctions d'ordre supérieur?

11

SQL est-il fondamentalement une instance spécifique au domaine de map + fold + filter?

Il me semble que le SQL suivant:

SELECT name
FROM fruits
WHERE calories < 100 

est juste du sucre syntaxique pour l'opération map + filtre + fold suivante:

var fruits = [{id : 1, name: 'orange', calories : 100},
    {id : 2, name : 'banana',  calories : 150},
    {id : 3, name: 'apple', calories : '50'}];

fruits.map(function(fruit) { return { name : fruit.name, calories : fruit.calories })
    .filter(function(obj) { return obj.calories < 100 })
    .reduce(function (accumulator, obj) { accumulator + "\n" + val.name; });

Est-ce une coïncidence ou existe-t-il une équivalence sémantique solide qui peut être prouvée? Comment, en gros?

Je sais que dans la pratique, SQL a beaucoup de cloches et de sifflets, mais au fond, est-ce simplement une opération de filtrage de carte?

L'article suivant est pertinent: http://blogs.msdn.com/b/doriancorompt/archive/2013/01/21/bringing-the-querying-power-of-sql-to-javascript.aspx

Sridhar Sarnobat
la source
1
Comment modéliseriez-vous une clause JOIN ou GROUP BY?
Ixrec
1
@Ixrec: Comme ça
Mason Wheeler
2
gnat - Si vous lisez l'autre article, vous verrez qu'ils m'ont dit que la question n'était pas appropriée pour Stackoverflow, alors j'ai posté ici. Parfois, vous ne pouvez pas gagner avec Stackoverflow. Soit le message est fermé pour être inapproprié, dans le mauvais forum ou trop complexe, donc ne convient pas à ce site, ou c'est si facile que vous auriez dû utiliser Google.
Sridhar Sarnobat
1
Oh, je suis censé supprimer l'autre message. Terminé.
Sridhar Sarnobat
1
@ Sridhar-Sarnobat: Normalement, lorsqu'un groupe d'utilisateurs vote pour migrer votre question vers Programmers.SE, elle sera automatiquement migrée. Vous avez clos votre question avant qu'elle n'atteigne les 5 voix requises.
Brian

Réponses:

6

Jetez un oeil à LINQ , qui prend les concepts de base derrière SQL et le généralise à la programmation orientée objet. L' Whereopérateur est un filtre standard, l' Selectopérateur est une projection / carte, etc. Toutes les opérations de requête SQL de base sont représentées dans LINQ, implémentées à l'aide de fonctions d'ordre supérieur, donc oui, vous avez raison dans votre compréhension intuitive de SQL.

La grande différence entre l'exemple que vous avez et le fonctionnement d'une base de données relationnelle est que SQL est conçu avec un ensemble très limité de commandes à l'esprit. Ce n'est pas Turing-complete et les concepteurs de bases de données savent ce qu'il peut et ne peut pas faire, ce qui leur permet de concevoir le système beaucoup plus facilement pour optimiser les requêtes beaucoup plus que ce qui serait possible avec une simple Mapénumération d'un ensemble de données élément par élément.

Mason Wheeler
la source
Cela démontre seulement que des fonctions d'ordre supérieur peuvent être utilisées pour réaliser des opérations SQL, et non que les deux sont liées les unes aux autres en général.
Bart van Ingen Schenau
1
@Bart: La question était alors "y a-t-il une équivalence sémantique solide qui peut être prouvée?" Mettre en œuvre une chose en termes d'une autre est une technique de longue date pour prouver l'équivalence en informatique. Par exemple, une façon de prouver qu'une langue est Turing-complete en l'utilisant pour implémenter une autre langue qui est déjà connue pour être Turing-complete.
Mason Wheeler
Pour une équivalence sémantique, je m'attendrais à ce que vous puissiez la montrer dans les deux sens. Tant que les requêtes SQL peuvent être exprimées dans des fonctions d'ordre supérieur et que vous pouvez exprimer une fonction d'ordre supérieur dans la syntaxe SQL.
Bart van Ingen Schenau
2
Peut-être que je n'ai pas formulé la question de manière assez formelle. Je suppose que je n'ai pas besoin qu'il soit bidirectionnellement équivalent dans 100% des cas. Juste que les requêtes typiques à travers une approche peuvent être réécrites comme une autre.
Sridhar Sarnobat
2
Pour être honnête, l'OP a formulé la question comme "les requêtes SQL sont-elles équivalentes à des fonctions d'ordre supérieur", et non "est le langage SQL équivalent à un langage de programmation fonctionnel", donc aucune des réponses n'est fausse.
Ixrec
9

SQL est basé sur l'algèbre relationnelle et le calcul relationnel tuple, et non sur des fonctions d'ordre supérieur ou une programmation fonctionnelle. Alors que SELECT, FROM et WHERE ont des fonctions analogues dans d'autres langages, SQL lui-même ne prend pas en charge les fonctions d'ordre supérieur généralisées, mais uniquement les fonctions "d'ordre supérieur" que le langage lui-même définit.

Étant donné que SQL ne vous permet pas d'écrire vos propres fonctions personnalisées d'ordre supérieur, il ne peut être dit avec aucune autorité que le langage prend en charge les fonctions d'ordre supérieur.

Robert Harvey
la source
L'algèbre / calcul relationnel est-il lié à la programmation fonctionnelle? Je pense que les langages relationnels sont dérivés de la théorie des ensembles mais je ne sais pas si cela les rend fonctionnels.
Sridhar Sarnobat
1
C'est pourquoi «ordre supérieur» est entre guillemets effrayants.
Robert Harvey