Czy (podstawowe) zapytania SQL są semantycznie równoważne funkcjom wyższego rzędu?

12

Czy SQL jest w zasadzie specyficznym dla domeny wystąpieniem map + fold + filter?

Wydaje mi się, że następujący SQL:

SELECT name
FROM fruits
WHERE calories < 100 

to tylko cukier syntaktyczny dla następującej operacji map + filter + fold:

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; });

Czy to przypadek, czy też istnieje rozsądna równoważność semantyczna, którą można udowodnić? Z grubsza jak?

Wiem, że w praktyce SQL ma wiele dzwonków i gwizdków, ale czy jego rdzeniem jest po prostu operacja składania map?

Istotny jest następujący artykuł: http://blogs.msdn.com/b/doriancorompt/archive/2013/01/21/bringing-the-querying-power-of-sql-to-javascript.aspx

Sridhar Sarnobat
źródło
1
Jak modelowałbyś klauzulę JOIN lub GROUP BY?
Ixrec
1
@Ixrec: Tak
Mason Wheeler,
2
komar - jeśli przeczytasz drugi post, zobaczysz, że powiedzieli mi, że pytanie jest nieodpowiednie dla Stackoverflow, więc potem opublikowałem tutaj. Czasami nie można wygrać z Stackoverflow. Albo post zostanie zamknięty, ponieważ jest nieodpowiedni, na niewłaściwym forum lub zbyt skomplikowany, więc nieodpowiedni dla tej witryny, lub jest tak łatwy, że powinieneś po prostu użyć Google.
Sridhar Sarnobat
1
Och, mam usunąć drugi post. Gotowy.
Sridhar Sarnobat,
1
@ Sridhar-Sarnobat: Zwykle, gdy grupa użytkowników głosuje za przeniesieniem pytania do Programmers.SE, zostanie ono automatycznie migrowane. Pytanie zostało zamknięte, zanim osiągnęło wymagane 5 głosów.
Brian

Odpowiedzi:

6

Spójrz na LINQ , który bierze podstawowe pojęcia za SQL i uogólnia go na programowanie obiektowe. WhereOperatora jest Bog-standardowy filtr, Selectoperator jest występ / Mapa, i tak dalej. Wszystkie podstawowe operacje zapytania SQL są reprezentowane w LINQ, zaimplementowane przy użyciu funkcji wyższego rzędu, więc tak, masz rację w intuicyjnym rozumieniu SQL.

Dużą różnicą między twoim przykładem a sposobem działania relacyjnej bazy danych jest to, że SQL jest zaprojektowany z bardzo ograniczonym zestawem poleceń. Nie jest to kompletna metoda Turinga, a projektanci baz danych wiedzą, co mogą, a czego nie mogą zrobić, co znacznie ułatwia im zaprojektowanie systemu w celu zoptymalizowania zapytań w znacznie większym stopniu, niż byłoby to możliwe przy prostym Mapwyliczeniu zestawu danych element po elemencie.

Mason Wheeler
źródło
To tylko pokazuje, że funkcje wyższego rzędu mogą być używane do realizacji operacji SQL, a nie, że oba są ze sobą w ogóle powiązane.
Bart van Ingen Schenau
1
@ Bart: Zatem pytanie brzmiało: „czy istnieje dźwiękowa równoważność semantyczna, którą można udowodnić?” Wdrożenie jednej rzeczy w kategoriach drugiej jest uświęconą techniką dowodzenia równoważności w informatyce. Na przykład, jednym ze sposobów udowodnienia, że ​​język jest kompletny w Turinga, używając go do implementacji innego języka, który jest już znany jako Turing-kompletny.
Mason Wheeler,
Dla równoważności semantycznej spodziewałbym się, że można to pokazać w obu kierunkach. Zarówno kwerendy SQL można wyrazić w funkcjach wyższego rzędu, jak i funkcję wyższego rzędu w składni SQL.
Bart van Ingen Schenau
2
Może nie sformułowałem pytania wystarczająco formalnie. Chyba nie muszę być dwukierunkowo równoważne w 100% przypadków. Wystarczy, że typowe zapytania za pomocą jednego podejścia można przepisać jako inne.
Sridhar Sarnobat,
2
Aby być uczciwym, OP sformułował pytanie jako „czy zapytania SQL są równoważne funkcjom wyższego rzędu”, a nie „to język SQL równoważny funkcjonalnemu językowi programowania”, więc żadna odpowiedź nie jest błędna.
Ixrec
10

SQL oparty jest na relacyjnej algebrze i Tuple Relational Calculus, a nie funkcjach wyższego rzędu ani programowaniu funkcjonalnym. Podczas gdy SELECT, FROM i WHERE mają analogiczne funkcje w innych językach, sam SQL nie obsługuje uogólnionych funkcji wyższego rzędu, ale tylko te funkcje „wyższego rzędu”, które sam język definiuje.

Ponieważ SQL nie pozwala na pisanie własnych niestandardowych funkcji wyższego rzędu, nie można powiedzieć z żadnym autorytetem, że język obsługuje funkcje wyższego rzędu.

Robert Harvey
źródło
Czy algebra / rachunek relacyjny jest w ogóle związany z programowaniem funkcjonalnym? Myślę, że języki relacyjne wywodzą się z teorii mnogości, ale nie jestem pewien, czy to czyni je funkcjonalnymi.
Sridhar Sarnobat,
1
Właśnie dlatego „wyższego rzędu” są przerażające.
Robert Harvey,