Skyline operatör

Skyline- operatören är föremål för ett optimeringsproblem , som används i en fråga för att filtrera resultat från en databas för att bara behålla de objekt som inte är värre än något annat.

Denna operatör är en utökning av SQL föreslagen av Börzsönyi et al. Ett klassiskt exempel på tillämpning av skylineoperatören innebär att välja ett hotell för en semester. Användaren vill att hotellet ska vara både billigt och nära stranden. Men hotell som ligger nära stranden kan också vara dyra. I det här fallet skulle skylineoperatören bara presentera de hotell som inte är sämre än något annat hotell i både pris och avstånd till stranden.

Föreslagen syntax

För att ge ett exempel i SQL: Börzsönyi et al. föreslog följande syntax för skyline-operatören:

     
    
        
                       
   VÄLJ  ...  FRÅN  ...  VAR  ...  GRUPPERA  EFTER  ...  ATT HA  ...  SKYLINE  AV  [  DISTINKT  ]  d1  [  MIN  |  MAX  |  DIFF  ],  ...,  dm  [  MIN  |  MAX  |  DIFF  ]  BESTÄLL  AV  ...

där d ₁ , ... d _m anger dimensionerna för horisonten och MIN, MAX och DIFF anger om värdet i den dimensionen ska minimeras, maximeras eller helt enkelt vara annorlunda.

Genomförande

Skyline-operatorn kan implementeras direkt i SQL med nuvarande SQL-konstruktioner, men detta har visat sig vara mycket långsamt. Andra algoritmer har föreslagits som använder dividera och erövra, index, MapReduce och generell datoranvändning på grafikkort . Skyline-förfrågningar på dataströmmar (dvs. kontinuerliga skyline-förfrågningar) har studerats i samband med parallell frågebehandling på flera kärnor, på grund av deras breda spridning i beslutsfattande i realtid och dataströmningsanalys.

Se även

^ ^a ^b ^c ^d Borzsonyi, Stephan; Kossmann, Donald; Stocker, Konrad (2001). "The Skyline Operator". Proceedings 17th International Conference on Data Engineering : 421–430. doi : 10.1109/ICDE.2001.914855 . ISBN 0-7695-1001-9 . S2CID 5812098 .
^ Mullesgaard, Kasper; Pedersen, Jens Laurits; Lu, Hua; Zhou, Yongluan (2014). "Effektiv skylineberäkning i MapReduce" (PDF) . Proc. 17:e internationella konferensen om utvidgning av databasteknik (EDBT) : 37–48.
^ Bøgh, Kenneth S; Samtycke, Ira; Magnani, Matteo (2013). "Effektiv GPU-baserad skylineberäkning". Proceedings of the Ninth International Workshop on Data Management on New Hardware : 5:1–5:6. doi : 10.1145/2485278.2485283 . ISBN 9781450321969 . S2CID 13195757 .
^ De Matteis, Tiziano; Di Girolamo, Salvatore; Mencagli, Gabriele (25 augusti 2016). "Kontinuerliga skylinefrågor på flerkärniga arkitekturer" . Samtidighet och beräkning: övning och erfarenhet . 28 (12): 3503–3522. doi : 10.1002/cpe.3866 . S2CID 6562372 .

[borzsony2001skyline-1] Borzsonyi, Stephan; Kossmann, Donald; Stocker, Konrad (2001). "The Skyline Operator". Proceedings 17th International Conference on Data Engineering : 421–430. doi : 10.1109/ICDE.2001.914855 . ISBN 0-7695-1001-9 . S2CID 5812098 .

[2] Mullesgaard, Kasper; Pedersen, Jens Laurits; Lu, Hua; Zhou, Yongluan (2014). "Effektiv skylineberäkning i MapReduce" (PDF) . Proc. 17:e internationella konferensen om utvidgning av databasteknik (EDBT) : 37–48.

[3] Bøgh, Kenneth S; Samtycke, Ira; Magnani, Matteo (2013). "Effektiv GPU-baserad skylineberäkning". Proceedings of the Ninth International Workshop on Data Management on New Hardware : 5:1–5:6. doi : 10.1145/2485278.2485283 . ISBN 9781450321969 . S2CID 13195757 .

[4] De Matteis, Tiziano; Di Girolamo, Salvatore; Mencagli, Gabriele (25 augusti 2016). "Kontinuerliga skylinefrågor på flerkärniga arkitekturer" . Samtidighet och beräkning: övning och erfarenhet . 28 (12): 3503–3522. doi : 10.1002/cpe.3866 . S2CID 6562372 .