Samenvatting Internettechnologie
Daan Pape 3e bachelor informatica UGent 31 mei 2014
Internettechnologie
1
Daan Pape
Inleiding
1.1
Basisprincipes van netwerkgebaseerde computersystemen
Een systeem is opgebouwd uit verschillende interagerende deelsystemen die zelf opgebouwd zijn uit deelsystemen of atomaire componenten. De architectuur van een systeem is de structuur en organisatie van het systeem en deze bestaat uit 3 componenten: • Decompositie: het opsplitsen in deelsystemen zoals LAN, WAN, routers, hosts, . . . • Functionaliteit: de functionaliteit van een bepaalde server is bv. email • Interactie: hoe de communicatie tussen deelsystemen in elkaar zit.
1.2
Infrastructuur van netwerkgebaseerde systemen
De infrastructuur is een platform voor specifieke applicatiesoftware en verzorgt communicatie, opslag, dataverwerking en interactie met de gebruiker. De hardware en softwareinfrastructuur kan men zien als een gelaagd systeem: applicatie middleware (ipc library, databank abstractie software) besturingssysteem (netwerkstack, bestandssysteem) hardware (netwerk, opslag) Iedere host heeft een OS voor netwerk, GUI, opslag, . . . de middleware is echter optioneel. De communicatiediensten zijn vandaag zeer belangrijk en moeten rekening houden met verschillende soorten communicatie. Zo kan men communicatie hebben in LAN’s waarbij de servers op dezelfde fysieke locatie staan of WAN’s waarbij dit niet zo is. Ook zijn de communicatienetwerken niet homogeen zoals mobiele netwerken. Een netwerk interpreteert geen data maar er wordt onderzoek gedaan op cognitive networking. Men wil vandaag vooral dat er geen congestion optreed op punten zoals de internetlijn, serverbelasting, peering punten, . . . Het bestandssysteem verzorgt veel taken: • Organisatie van bestanden in directories • Centralisatie van gegevens in server hosts (fysisch of logisch) wat backuppen makkelijker maakt. • Het toekennen van permissies aan gebruikers • File sharing Vaak zijn bestandssystemen over meerdere fysieke hosts gespreid en men spreekt dan van Distributed File System of DFS. De gebruiker ziet dit niet en men kan replicatiesoftware gebruike nvoor backups en beveiligde netwerkcommunicatie toepassen. Het gebruik van een DFS zorgt voor een lagere Total Cost of Ownership of TCO omdat het beheer eenvoudig en dynamisch is waardoor alles effici¨enter kan. De meeste applicaties maken gebruik van databanken die met een DBMS worden beheerd zoals MySQL, MSSQL, PostgreSQL, SQLite, . . . en er bestaan standaardbewerkingen die alle DMBS systemen kunnen zoals opslag van nieuwe data, verwijderen van data, zoeken naar data (filters), . . . Het is niet wenselijk deze standaardbewerkingen voor elk DBMS opnieuw te implementeren en daarom kan men van een middleware softwarelaag gebruik maken. Dit is een API die DBMS, OS en programmeertaal onafhankelijk is, voorbeelden:
1
Internettechnologie
Daan Pape
• ODBC of Open DataBase Connectivity: initieel enkel voor Windows maar nu voor de meeste besturingssystemen en het wordt door veel DBMS leveranciers ondersteund. • JDBC of Java DataBase Connectivity: een software API voor Java en als de DBMS software geen JDBC gebruikt is er een ODBC naar JDBC bridge. De veelgehoorde term the cloud is nogal vaag en kan software, gegevensopslag of infrastructuur betreffen.
1.3
Client/Server architecturen
Deze architectuur is per definitie asymmetrisch wat wil zeggen dat vele clients ´e´en server aanspreken. De server is hierbij reactief omdat hij reageert op aanvragen van de clients die actief zijn. In dit soort architectuur wordt de business application gecentraliseerd en kan men zo goede beveiliging, onderhoud, bescherming, . . . aanbieden. De gebruiker heeft echter minder controle over de gebruikte versie van de software. Een server moet dus altijd beschikbaar zijn en weet niet wanneer een client een request zal sturen. Afhankelijk van wat de vereisten zijn voor de applicatie moet er dus aan redundantie gedacht worden en van aangepaste hardwareplatformen gebruik worden gemaakt. Clients mogen aan- en afgezet worden volgens behoefte van de gebruikers en we maken onderscheid tussen 3 soorten clients: 1. Fat client: zeer veel functionaliteit. 2. Thin client: uitsluitend presentatie en gebruikersinterface zoals een webbrowser. 3. Ultra-thin client: een apparaat enkel voor de grafische weergave van applicatieresultaten en verwerking van input van de gebruiker. Zoals remote desktop en Citrix. De presentatie wordt ook door de server gedaan. In een C/S architectuur hebben we typische verschillende lagen: • Presentation layer: de volledige gebruikerservaring met bv. een GUI zit hierin. Ook de formattering van data als die van de server wordt verkregen. De browser vervult meestal alle taken in de presentatielaag bij webtoepassingen. • Application layer: ook wel application logic of business logic. Deze laag omvat de applicatieservers die de applicatiefunctionaliteit implementeren, input ontvangen, beslissen welke acties er moeten worden ondernomen, data verwerken, . . . Veiligheid is zeer belangrijk in deze laag, zeker als men op het gevaarlijke internet moet. • Data layer: ook wel database layer of Enterprise Information System (EIS). Deze laag ontvangt en stockeert data uit de applicatielaag en verzorgt ook het opvragen en doorgeven van data terug aan de applicatielaag. Onder data verstaan we records, bestanden, . . . en voorbeelden zijn ERP systemen en andere MIS of Management Information System systemen. Men kan diverse lagen redundant uitvoeren. Zo kan men op de datalaag data repliceren en partitioneren met fileservers, DBMS systemen, ... Op de applicatielaag kan men gaan voor modulaire of redundante applicatielogica. Men kan zo een indeling van architecturen maken: • One tier: de 3 lagen zijn in 1 entiteit ge¨ıntegreerd en de clients zijn terminals die zowel presentatie, applicatie en data vanop de server benaderen. Typisch is dit een mainframe architectuur die zeer gecentraliseerd is wat onderhoud gemakkelijk en goedkoop maakt.
2
Internettechnologie
Daan Pape
• Two tier: De clients worden steeds krachtiger en de presentatielaag bevindt zich nu op de client. Op deze manier kunnen meer veeleisende presentatiemanieren worden gebruikt en het netwerk moet enkel nog data doorsturen. Een API (zoals REST) wordt mogelijk. Dit is voldoende voor veel netwerkgebaseerde systemen maar als informatie kritisch is, is dit systeem ontoerijkend. • Three tier: de drie lagen draaien nu elk op hun eigen machine. De presentatielaag bevindt zich bij de clients en zowel de applicatielaag als de datalaagdraaien op verschillende servers. Dit zorgt voor een hoge schaalbaarheid en beveiliging, de clients hebben namelijk geen rechtstreekse connectie met de datalaag. Ook kunnen verschillende applicaties dezelfde data gemakkelijk aanspreken. Men kan zowel logisch (firewall) als fysisch (verschillende datacenters) de data beveiligen. Men kan met contentnetwerken voor de data de performantie ook verbeteren. • Four tier: dit wordt gebruikt in webapplicaties. De applicatielaag wordt nu verder opgesplitst in: – Web layer of Integratielaag gericht op presentatie – Business logic zoals regels, sessiebeheer, . . . Grote webapplicaties hebben vaak deze architectuur en .NET en J2EE platformen hebben dit type architectuur. De Business logic gaat dan vaak via API invokatie terwijl de web layer in de browser draait. Interactie tussen de weblaag en business logic gebeurt met RMI of Remote Method Invokation. Dit laat toe dat gedistribueerde objecten met elkaar communiceren en er zijn heel wat techologie¨en zoals Java/RMI met Java Remote Method Protocol (JRMI), Distributed Component Object Model (DCOM) met Object Remote Procedure Call (ORPC), Common Object Request Broker Architecture (CORBA) met Internet InterORB Protocol (IIOP), .NET Remoting, . . . Onder business logic verstaan we: • Business objecten: bv. een cataloog, een winkelkarretje, een account, . . . • Business logic voor een object: bv. elke klant heeft een uniek account, een account bestaat uit naam, email en adres, . . . Soms spreken we van multi-tier als we de applicatielaag of middle tier verder opdelen. Een extra component is dan vaak de Data Access Layer (DAL). Het meerdere aantal lagen laat gemakkelijker onderhoud toe met een lagere TCO. Dit wordt typisch voor complexe software gebruikt waar meerdere personen onderhoud en beveiliging doen. De applicatieserver is dan vaak gedistribueerd en databankservers wordt door veel applicatieservers bevraagd. Een E-comerce platform zal typisch N-tier zijn opgebouwd.
1.4
Het opzetten en beheren van netwerkgebaseerde systemen
Bij het opzetten van een dergelijk systeem moet men met enkele parameters rekening houden: • Is het wenselijk een systeem netwerkgebaseerd te maken, vaak wel. • Schaalbaarheid : het systeem moet goed kunne nomgaan met veranderlijke capaciteit en activiteit. Meestal zijn hiervoor verschillende hosts nodig wat de applicatie dus netwerkgebaseerd maakt. • Administratie: er is nood aan automatisatie om alles op orde te houden. Netwerkgebaseerd kan men dit gespecialiseerd doen door een goede scheiding van de componenten.
3
Internettechnologie
Daan Pape
Men moet dan een architectuur ontwerpen. Informatie is het basisproduct welke door data wordt voorgesteld. Men moet bij het ontwerp van de architectuur gemengt decompositie en assemblage toepassen. Decompositie is het opsplitsen in deelsystemen waarbij elk systeem onafhankelijk kan worden ontwikkelt en assemblage is de aanschaf en integratie van bestaande deelsystemen. Hoe meer deelsystemen hoe modulairder het systeem is. Bij het beslissen over de locatie van de data en de dataverwerking moet men rekening houden met 4 fundamentele taken qua data: 1. Verwerven 2. Opslaan 3. Verwerken 4. Presenteren Het toekennen van welke taken door welke host worden gedaan zal de performantie en communicatie bepalen. Steeds moet men zich afvragen hoe dicht de data zich bevindt, hoeveel gebruikers er zullen zijn, hoe veranderlijk de data is, . . .
1.5
Hoe Google werkt
Het doel van Google is om het internet doorzoekbaar te maken en reclame te verkopen met AdWords en AdSense. Het werd opgericht door Larry Page en Sergey Brin na hun onderzoek aan Stanford University. Het google zoekmodel is gebaseerd op meer dan 100 verschillende parameters maar de belangrijkste is PageRank: • Gebaseerd op ’citations’ wat wil zeggen dat men kijkt hoe populair een url is door het aantal verwijzingen te tellen. • Het is een maat voor de waarschijnlijkheid dat een willekeurige surfer op die pagina terecht komt. De PageRank P R(A) van een webpagina A wordt als volgt berekent: P R(Tn ) P R(T1 ) + ··· + P R(A) = (1 − d) + d C(T1 ) C(Tn )
(1)
waarin: • T1 , . . . , Tn : deze pagina’s bevaten een hyperlink naar A, de citations. • d: de ’damping factor’: dit is de waarschijnlijkheid dat een gebruiker een bepaalde pagina verlaat voor een andere, meestal d = 0.85. • C(x): het aantal linken dat vanuit pagina x vertrekt naar een andere pagina Er is steeds behoud van PageRank vanuit een bepaalde pagina. De berekening van PageRank is een iteratief proces en er zijn tools op het web die de PageRank kunnen berekenen. Soms gebeurt deze berekening via theoretische modellen of simulaties of soms is het gewoon een look-up service bij Google. Om te vermijden dat er SEO wanpraktijken gebeuren is niet bekend hoe de echte PageRank wordt berekend. Vanuit SEO standpunt wil men zoveel mogelijk inkomende links, citations. Hoe minder uitgaande links in de pagina die verwijzen naar je webpagina hoe beter, want de citations moeten uniek zijn.
4
Internettechnologie
Daan Pape
PageRank is uiteraard niet het enige criterium en moet gezien worden als een vermenigvuldigingsfactor in het hele zoekproces. De meeste zoekmachienes associeerden de tekst van een hyperlink, de anchor text, enkel met de pagina waarop hij voorkomt. Google associeert de anchor text ook met de webpagina waarnaar hij verwijst. Dit omdat anchors vaak goede beschrijvingen bevatten. Ook kunnen links naar afbeeldingen, video of audio wijzen die anders niet tekstgebaseerd kunnen worden geanaliseerd. Het is de enige manier om te crawlen op sommige dingen. Het gebruik van anchor text houdt ook risico’s in zoals een Google Bom. De gebruikers registreren veel domeinen die allemaal naar een site verwijzen met dezelfde anchortekst ”xyz”. Als men dan de term ”xyz¨ıntikt in Google is de kans groot dat men op die pagina terecht komt. Als veel gebruikers samenspannen kan dit effect ook optreden. Een voorbeeld zijn de woorden ”miserable failure”. Naast de anchor text wordt ook de volledige raw HTML van een pagina bijgehouden en de visuele presentatie van de woorden. Algemeen gebeuren volgende 4 stappen bij een zoekopdracht: 1. Zoek alle webpagina’s die de trefwoorden van de zoekactie bevatten. 2. Rangschik volgens de features per pagina zoals trefwoorden en opmaak ervan. 3. Breng het principe van anchor text in rekening. 4. Pas PageRank toe als vermenigvuldigingsfactor. Google gebruikt dus een zeer sterk gelaagde architectuur omdat men een goede kwaliteit wil aanbieden met een zeer goede performantie. Er is een instantaan resultaat voor zoekacties in een systeem met honderden miljoenen webpagina’s. Het Google-datacenter in Belgi¨e zorgt voor enkele milliseconden betere performantie in Europa. We bekijken nu de verschillende lagen: 1. Crawling: de GoogleBot download automatisch webpagina’s en kan dit snel en effici¨ent doen. Een URL server stuurt een lijst van de te downloaden URL’s naar de crawlers. De gedownloade pagina’s krijgen een unieke ID en worden gecomprimeert opgeslagen. 2. Indexing en Sorting: elk document wordt omgezet in een set van hits die in barrels of databases worden opgeslagen. Een hit is een woord met metadata zoals opmaak. Alle hyperlinks worden geparsed en in een ”Anchors’ database opgeslagen met de oorsprong, het doel en de anchor text. De sorter sorteert de inhoud van de barrels zodat de docID’s en wordID’s gemakkelijk gevonden kunnen worden. 3. Interne operaties: de URL resolver haalt URL’s uit de anchor databae en converteert ze naar absolute URL’s waarna ze aan de docID’s in de barrels worden gelinkt. Er wordt dan een database met alle docID’s opgebouwd en er wordt een checksum berekend van de URL’s gelinkt aan de docID’s en daarop wordt gesorteerd. Zoeken kan nu met binary search worden gedaan. Een database met alle links wordt gebouwd wat dus een verzameling van paren docID’s is, daaruit wordt dan de PageRank berekend. 4. Searching: het Google Query Evaluation Process verloopt in 5 stappen: (a) Interpreteer de query. (b) Zet zoekwoorden om in wordID’s. (c) zoek in de documentenlijst naar docID’s die alle zoektermen bevatten. (d) Bepaal pagina rank op basis van hit-types (title, anchor, ...) met hun gewicht. (e) Combineer het resultaat met PageRank.
5
Internettechnologie
1.6
Daan Pape
Hoe Amazon werkt
Amazon wil een plaats zijn waar mensen alles kunnen vinden. Ze werken daarvoor samen met e-commerce partners en bieden vele diensten aan. Amazon heeft ook andere diensten zoals IMDB. De Amazon Web Services of AWS zijn cloud diensten: • EC2 of Elastic Compute Cloud: dit is aanpasbare rekencapaciteit aangerekend in CPUuur en dataverkeer. Er kunnen binnen minuuten servers aangemaakt worden met AMI’s of Amazon Machine Images. Je kan publieke gebruiken met linux of windows, private met eigen app’s of betalende door third party. • S3 of Simple Storage Service: men kan objecten tot 5Gb opslaan in de cloud. Dit kan zowel publiek en privaat door URL met ACL (Acces Control List). Er is een hoge beschikbaarheid van 99,99% en ondersteuning voor BitTorrent en verschillende API’s. De objecten zitten in buckets. • SimpleDB • SQS of Simple Queue Service: een schaalbare berichtenservice die zeer betrouwbaar is en tot miljoenen berichten per dag kan gaan. Inter Process Communicatie, buffering, . . . zijn mogelijkheden en er is een simpele 10 methoden platformonafhankelijke API. • Mechanical Turk: sommige taken zijn moeilijk voor een computer maar makkelijk voor een mens zoals beeldherkenning, spraakverwerking, . . . . De Mechanical Turk API stelt ontwikkelaars in staat gemakkelijk menselijke intelligentie toe te passen. De developer geeft een Human Intelligence Task op die aan echte mensen worden overgelaten. Voorbeelden zijn vertalingen, the sheep market, . . . Deze diensten worden aangeboden om de rompslomp en kosten van web development weg te namen. Het beheer van servers, voorzien van koeling, bandbreedte, stroom en het voorbereiden op schaalvergroting is vaak moeilijk en duur. Men moet grote investeringen doen op voorhand indien men wil voorbereid zijn. Obstakels zijn schaalvergroting zoals een continue stijging in gebruik (youtube, facebook). Andere opstakels zijn pieken zoals Slashdot of de jaarlijkse belastingsaangifte. De oplossing is Web-scale computing waarbij vaste kosten voor een hoge capaciteit variabel worden omdat er schaalbaarheid op aanvraag is. Er is een hoge beschikbaarheid en betrouwbaarheid. En de envoudige API’s en lage TTM (Time To Market) maken het kost-effectief. Amazon bekijkt welke delen van zijn techologie het aan ontwikkelaars kan aanbieden, dan worden obstakels om ermee aan de slag te gaan verwijderd of verkleind en zo bekomt men een verzameling API’s en businessmodellen voor Amazon services. Ze bieden zowel data aan, infrastructuur (SQS, S3, EC2), zoeken tot zelfs mensen.
1.7
Energieverbruik
Webapplicaties vereisen veel rekenkracht en dus moeten meer machines worden ingezet. Datacenters zetten daarom massaal in op groene energie en datacenters worden strategisch geplaatst in koude gebieden dicht bij water.
2
Clustering
Bij de karakterisering van de werklast bij een goede capaciteitsplanning is clustering zeer belangrijk. Deze algoritmen kunnen het optimaal aantal basiscomponenten bepalen en ze geven waarden voor de parameters die deze basiscomponenten karakteriseren. We vermelden hier twee basisprincipes MST of Minimum Spanning Tree en het k-gemiddelden algoritme. 6
Internettechnologie
2.1
Daan Pape
MST-algoritme
Dit is een hi¨erarchisch algoritme dat start met het beschouwen v an alle individuele gebeurtenissen als zijnde clusters. Twee clusters die het dichtst bij elkaar liggen worden dan samengevoegd tot een nieuwe cluster totdat het gewenst aantal bereikt is. Meer formeel: 1. Als de performantiedata van P gebeurtenissen gekend is waarbij elk meetpunt uit K metingen bestaat. We hebben danP meetpunten van de vorm (Dp1 , Dp2 , . . . , DpK ) met p = 1, . . . , P . 2. Kies J als het gewenste aantal clusters. 3. Stel het actuele aantal clusters j gelijk aan het aantal meetpunten, dus j = P . 4. Herhaal volgende stappen totdat j = J: (a) Bepaal de parameterwaarden van de centro¨ıden C1 , . . . , Cj voor elk van de j actuele clusters. Deze zijn gemiddelden van de parameterwaarden van alle meetpunten van de cluster. (b) Bereken de (bv. euclidische afstand) tussen elk paar centro¨ıden en bouw de j × jinterclusterafstandsmatrix op. Element (m, ) stelt dan de afstand voor tussen clusters m en n. (c) Bepaal het minimale van nul verschillende element (q, r) in de interclusterafstandsmatrix. (d) Voeg de clusters q en r samen en verminder het actuele aantal clusters j met 1.
2.2
k-means
Het k-gemiddeldenalgoritme is een niet-hi¨erarchisch clusteringsalgoritme dat start met het kiezen van J meetpunten/gebeurtenissen. Deze worden als beginschatting gebruikt voor de centro¨ıden van de J clusters die moeten worden gevonden. De andere meetpunten worden toegevoegd aan de dichtstbijzijnde clusters. Deze allocatieprocedure wordt iteratief uitgevoerd totdat geen enkel meetpunt meer van cluster verandert, of tot een vooraf vastgelegd maximum aantal iteraties is bereikt. Meer formeel: 1. Als de performantiedata van P gebeurtenissen gekend is waarbij elk meetpunt uit K metingen bestaat. We hebben danP meetpunten van de vorm (Dp1 , Dp2 , . . . , DpK ) met p = 1, . . . , P . 2. Kies J als het gewenste aantal clusters. 3. Kies I het maximum aantal iteraties. 4. Kies J startpunten die zullen gebruikt worden als initi¨ele schattingen voor de clustercentro¨ıden. Men kan bv. de eerste J meetpunten kiezen of de J meetpunten die zich mutueel het verst van elkaar bevinden. 5. Beschouw elk meetpunt en vloeg het toe aan de cluster met de dichtstbijzeijnde centro¨ıde. Herbereken de parameterwaarden van deze centro¨ıde met het nieuwe meetpunt erbij. 6. Herhaal iteratiestap 4 tot geen enkele meetpunt meer van cluster verandert of tot I iteraties werden gedaan. Voor een voorbeeld van het clusteringalgoritme zie het bijbehorende clusterdocument.
7
Internettechnologie
3
Daan Pape
Operationele aspecten
3.1
Performantie van webgebaseerde toepassingen
Bij het meten van de tijd die verstrijkt om een webrequest te beantwoorde zijn 3 componenten belangrijk: 1. Client (browser): de eidgebruiker klikt op de link waarna de browser in lokale cache kijkt. Indien de pagina gevonden werd is de antwoordtijd Rc . Anders moet er een IP-adres aan de DNS server worden gevraagd, een TCP connectei gemaakt worden en een HTTP request verzonden en ontvanen worden. 2. Newerk: transport van de data 3. Server (webserver): de server ontvangt de HTTP-vraag en voert deze uit waarna het antwoord wordt verstuurd en afhankelijk van persistent of niet de connectie wordt gesloten. Er zijn dus heel wat verschillende tijden om te meten: • Rr : de totale antwoordtijd • RN 1 : de transfer van de HTTP-vraag (client naar server) • RN 2 : de transfer van het HTTP-antwoord (server naar client) • RS : de server residentietijd (tijd voor serveractiviteit) • RC : de client residentietijd (tijd voor clientactiviteit) Als we stellen dat RN = RN 1 + RN 2 dan geldt: Rr = RC + RN + RS
(2)
Hierbij is RC << RN + RS . Indien we met caching te maken waarbij hebben we: pC =
NC NP
(3)
met pC de succesrate wat het aantal cache hits gedeeld door het totaal aantal aanvragen is. De totale antwoordtijd Rr wordt nu dus: Rr = pC RC + (1 − p)Rr
(4)
De cachegrootte heeft dus een grote impact op de browsesnelheid. Een succesvolle webtoepassing heeft een sterke verhoging van het aantal clients en servers. Schaalbaarheid is dus zeer belangrijk zeker als men weet dat de globale performantie wordt beperkt door de traagste component in het systeem. Een bottleneck is een deelsysteem dat de globale performantie beperkt en identificatie daarvan is zeer belangrijk en deze moeten het eerst worden aangepast bij upscaling. Het is belangrijk om een inschatting te kunnen maken van de benodigde resources. Zo kan men schatten heoveel objecten en welk type er zullen worden opgeslagen, hoeveel requests met welke omvang er zullen zijn, . . . Voor een publieke applicatie is dit veel moeilijker dan voor een interne applicatie. Voor een systeemadministrator is performantie gelijk aan de verreiste bandbreedte, de gegarandeerde uptime, . . . voor gebruikers is dat de beschikbaarheid, de snelheid van antwoorden, . . . Hoe performant een applicatie is, is ook grotendeels perceptie en er moeten dus kwantitatieve performantiematen zijn. Bij webtoepassingen heb je niet steeds alles onder controle (flash crowds, 8
Internettechnologie
Daan Pape
slechte verbindingen, . . . ) Enkele belangrijke performantiematen zijn de volgende: • Throughput: de verwerkingscapaciteit vande connectie tussen client en server. Dit wordt in aantal HTTP-requests/sec of bps uitgedrukt. • Latency: de tijd die de server nodig heeft om antwoord te formuleren. De totale antwoordtijd hnagt af van de latency en de throughput en de verwerkingstijd van de clients. Afgeleide maten zijn packet loss in procent wat het aantal fouten per seconde betekent. De populariteit van de toepassing komt overeen met het aantal gevraagde connecties met de server. Service Levels zijn niveau’s die aangeven welke mate van dienstverleningskwaliteit wordt geleverd. Periodiek wordt gemeten wat de performantiematen zijn om adequate capaciteitsplanning te kunnen uitvoeren op piekmomenten. Een SLA of Service Level Agreement is een overeenkomst tussen provider en afnemer over de geleverde kwaliteit. Gebruikers ervaren 0.1 seconde als instantaan, 1 seconde als traag maar doenbaar en vanaf 10 seconden is het zeer slecht. Proxy servers die dichter bij de user staan kunen latency korter maken en bandbreedtevereisten verlagen door ze te spreiden. De Content Delivery Netwerken of CDN’s doen dit. De proxy server is nu een client en server tegelijk met een lokale cache. Voor een proxyserver kan men volgende performantiematen gebruiken: • De succesverhouding pC =
NC NP :
dit zecht niets over de bandbreedte.
• De byte-succesverhouding: dit zegt wel iets over de bandbreedte. • Hoeveelheid getransfereerde data: het totaal aantal verstuurde bytes uit de cache. Scripting voegt veel functionaliteit toe en maakt websites dynamisch. De keuze over welke scripts op de server lopen en welke op de client kan een grote impact hebben op de globale performantie. De distributie van de te verwerken objecten (bv. bestandsgrootte) en de populariteit ervan zijn twee belangrijke aspecten van de performantie. De invloed van de bestandsgrootte-distributie (of bijhorende verwerkingstijd) heeft volgende aandachtspunten: • Een niet te verwaarlozen staart wat wil zeggen dat de kans op zeer grote bestanden niet te verwaarlozen is. • Afgeleide grootheden zoals gemiddelde vertonen grote variabiliteit. • De betekenis van individuele performantiemetingen op basis van bestandsgrootte moeten geminimaliseerd worden. De verwerkingstijd van bestandsgrootte-distributie of bijhorende verwerkingstijd volgt veelal een pareto-distributie:
9
Internettechnologie
Daan Pape
We kunnen de CPU-belasting indelen in klassen en dan daarover het gewogen gemiddelde nemen. Stel volgende verdeling van de CPU-tijd van 10 HTTP-requests reeds gesorteerd: 0.3
0.4
0.6 0.7 t < 1s
0.9
1.4
1.5 1.5 t ≤ 6s
1.7
18.1 t ≥ 6s
De gemiddelde CPU tijd over alle klassen is dan 6,7s. De algemeen gewogen CPU tijd wordt echter: 5 ∗ 0.58 + 4 ∗ 1.53 + 18.1 = 2.71 10 De 2,71 seconden is nu wel de meest relevante waarde. Niet enkel de bestandsgrootte is belangrijk maar ook de populariteit van de objecten. Dit is ook een goed gedocumenteerd fenomeen en er bestaat de wet van Zipf die stelt dat hoe groter de populariteitsrang p hoe minder populair (f = frequentie van optreden) het object is: f∼
1 p
(5)
De populariteitsrang is gewoon het volgnummer van de pagina indien deze op dalende populariteit worden gesorteert. Stel dat je paginas A en B hebt waarbij pagina B 100 bezoekers per dag heeft en pagina A 10 bezoekers, dan krijgt pagina B populariteitsrang 1 en pagina A populariteitsrang 2. Ter volledigheid geven we nog eens de netwerkkarakteristieken weer: • Latentie of vertraging: dit is de tijd nodig om ´e´en pakket van client naar server of omgekeerd te transfereren. De Round Trip Time of RTT is een maat om latentie uit te drukken in seconde en telt de totale tijd voor een pakket om aangevraagd en teruggezonden te worden. • Bandbreedte: een paat voor de snelheid waarmee data kan worden verzonden, in bps uitgedrukt. • Bandbreedte-latentieproduct een capaciteit voor datatransfer van de client naar de server of omgekeerd in aantal bit of byte. Er is altijd een groot verschil tussen gemiddelde activiteit en piekactiviteit, daarom is het aan te raden om met percentielen te werken.
3.2
Capaciteitsplanning
Een belangrijk begrip bij capaciteitsplanning is adequate capaciteit en er is een methodologie nodig voor capaciteitsplanning met: • Effici¨ente (deel)systeemconfiguratie • Geschikte netwerk- of systeemconfiguratie • Kosteffici¨entie met personeel- en investeringskosten Een SLA is het contractueel vastleggen van performantievereisten zoals een server die minimum zoveel tijd beschikbaar moet zijn of zoveel requests per seconde moet aankunnen. Als er geen SLA is geldt een best-effort approuch waarbij men een zo goed mogelijke dienstverlening nastreeft. Bij het kiezen van de goede technologie speelt niet alleen de performantie een rol maar ook de kennis, de kost, . . . Hoe strenger de SLA is hoe hoger de kosten typisch zijn en er zijn 2 types kosten: • CAPEX: dit zijn de opstartkosten en omvatten hard- en software, installatie, personeel, . . . • OPEX: operationele kosten met administratie, onderhoud, telecomkosten 10
Internettechnologie
Daan Pape
Schaalbaarheid is belangrijk maar niet altijd eenvoudig te realiseren. De definitie van adequate capaciteit is nu dus: • Het continu realiseren van de SLA’s. • Dit gebruik makende van vooraf gedefinieerde technologie¨en/standaarden • De realisatie gebeurt binnen de beperkingen van de kosten. De heterogeniteit aan diverse deelsystemen maakt het soms moeilijk, zo zijn er veel OSen, hardwaresooften, . . . Er zijn 3 modellen om de adequate capaciteit bij C/S-gebaseerde systemen te bepalen: 1. Werklastmodel: dit model beschrijft de vraag naar middelen binnen een representatieve tijdsspanne. 2. Performantiemodel: dit voorspelt de systeemperformantie als functie van de systeembeschrijving en de werklastparameters. De antwoordtijden en verwerkingssnelheid komen dan uit het model en deze kunnen met de SLA vergeleken worden. 3. Kostenmodel: de kosten voor soft- en hardware, telecom en administratie van het systeem worden bekeken.
3.2.1
Werklastmodellen
De werklast wordt beschreven door een systeem in deelsystemen op te splitsen en deze dan met kwantitatieve parameters te beschrijven. Twee basisparameters zijn: • Workload Intensity (WI): een maat voor de globale load op het systeem. • Service Demand (SD): een maat voor tijd nodig voor elke resource component (bv. CPU, RAM). Veel parameters worden afgeleid of geschat omdat ze niet rechtstreeks kunnen worden gemeten. Bij een hoge werklast zijn er veel gebeurtenissen en alle individuele werklastparameters van de gebeurtenissen bekijken is dan niet altijd relevant. Daarom gebruiken we een compacte representatie, namelijk het werklastmodel. We splitsen door middel van clustering de werklast op en berekenen de gemiddelden van de clusters omdat het globaal gemiddelde niet veel zegt. Het aantal clusters be¨ınvloed de nauwkeurigheid van het werklastmodel en clusteringsalgoritmen berekenen 11
Internettechnologie
Daan Pape
het optimaal aantal clusters. Idealiter geven performantiemonitors een waarde aan voor elke werklastparameter. In de realiteit zijn er vaak geen goede performantiemonitors beschikbaar en noodgedwongen wordt er te weinig tijd aan performantiemonitoring besteed. Sommige monitors geven globale parameter waarden zoals het totaal aantal getransfereerde pakketten in LAN, totale CPU benutting, . . . opsplitsing is dan beter en vuistregels om dat te doen werken vaak al goed. Vaak is het afdoende enkel de performantieparameters van de bottlenecks te meten en deze dan te vertalen naar andere omstandigheden en types van hardware. Best kiest men een vastgelegde benchmark als maatstaf. Op die manier kan men een syntetisch model gebruiken om het model te calibreren indien het verschil tussen de syntetische en werkelijke werklast te groot wordt. Op basis van de huidige toestand en de historiek kan men de toekomstige werklast en pieken voorspellen. Op deze manier kan men een strategie uitstippelen en eventueel hardware aanpassen. Een correcte trendanalyse is dus zeer belangrijk. 3.2.2
Performantiemodellen
In dit model is het systeem een black box. Interne details worden niet gemodelleerd en enkel verwerkingscapaciteit wordt gemodelleerd met de verwerkingsfunctie of throughput function: X0 (k)
met k het aantal aanwezige aanvragen
(6)
Het toestandstransitiediagram (TDD) of State Transition Diagram (STD) bevat de mogelijke toestanden van (deel)systemen en de transities tussen toestanden waarin het systeem zich kan bevinden. Een alternatief is het modelleren van individuele componenten/deelsystemen. Het eerste servermodel gaat uit van een oneindige populatie en oneindige wachtlijn. We nemen nu een aantal parameters op in het model: • λ (aanvragen/s): de aankomstsnelheid van de aanvragen • X0 (k) = µ: we modelleren een homogene werklast waarbij alle aanvragen statistisch gelijk zijn en enkel het aantal een invloed heeft. We hebben dus een constate verwerkingsfunctie. De oneindige wachtlijn in het model zorgt ervoor dat alle aanvragen worden behandeld en er dus geen verloren gaan. We gaan dan ook uit van een operationeel overzicht waarbij het aantal aanvragen bij het begin van de observatie gelijk is aan dat van het einde van de observatie. Tijdens de observatie kan het wel schommelen. We hebben dus: λ (aanvr/s) aankomst request server
→
aanvraag in wachtlijn
→
µ (aanvr/s) aanvraag wordt behandeld
Het model berekent: • Het model moet nu pk berekenen, dat is de fractie van de tijd dat er k aanvragen in de server aanwezig zijn. • Het gemiddeld aantal aanwezig aanvragen. • De gemiddelde response tijd. • De benuttiging van de server. • De verwerkingssnelheid van de server.
12
Internettechnologie
Daan Pape
De toestand van de server wordt door 1 parameter gekarakteriseerd, namelijk het aantal aanvragen aanwezig in de server. Dit heeft als gevolg dat het gedrag onafhankelijk is van de manier waarop de toestand werd bereikt en dat het gedrag onafhankelijk is van de huidige toestand. We hebben een geheugenloos of Markov -systeem met een aftelbaar oneindig aantal toestanden k en kunnen dit in een TTD voorstellen:
Het operationeel evenwicht stelt nu dat de flow in en uit elke toestand (de pijlen) gelijk is, dit noemen we het global balance principle. Dit geeft ons een evenwichtsvoorwaarde aan de grenzen: λp0 = µp1 (λ + µ)p1 = λp0 + µp2 (λ + µ)p2 = λp1 + µp3 ···
→ → →
µp1 µp2 µp3 ··· µpk
= λp0 = λp1 = λp2 = λpk−1
Dit heeft als gevolg: k λ pk = p0 µ
met k = 0, 1, 2, . . .
(7)
en dus is p0 de fractie van de tijd dat het systeem idle is. Het systeem bevindt zich steeds in een toestand en dus: " ∞ #−1 k ∞ ∞ X λ k X X λ λ = 1 ⇒ p0 = =1− (8) pk = p0 µ µ µ k=0
k=0
k=0
De voorwaarde voor convergentie is nu dat de snelheid van de aankomst van de vragen λ kleinder is dan de verwerkingssnelheid µ en dus: λ<µ De benuttiging U van de server wordt gegeven door: U = 1 − p0 =
λ µ
⇒
pk = (1 − U )U k
(9)
De toestandsdistributie is dus enkel afhankelijk van de benuttiging en niet van de individuele waarden. Het gemiddeld aantal aanvragen in de server is nu dus gelijk aan: N=
∞ X k=0
kpk = (1 − U )
∞ X
kU k = (1 − U )
k=0
U U = 2 (1 − U ) 1−U
(10)
en de gemiddelde verwerkingssnelheid van de server is dus gelijk aan: X = U µ + (1 − U ) · 0 = λ 13
(11)
Internettechnologie
Daan Pape
De gemiddelde verwerkingssnelheid is dus de gemiddlede aankomstsnelheid. Dit is logisch aangezien er geen aanvragen verloren gaan. We kunnen nu ook de gemiddelde antwoordtijd gaan berekenen: U/λ 1/µ U 1 S N = RX ⇒ R = = = = 1−U λ 1−U 1−U 1−U
(12)
waarbij S de gemiddelde verwerkingstijd per aanvraag is. Als U laag is (naar 0 gaat) dan is de gemiddelde antwoordtijd de gemiddelde verwerkingstijd per aanvraag en is er geen verlies ten gevolg van wachten. Als U hoog is (naar 1 gaat) dan is de antwoordtijd oneindig lang en is er dus veel tijdsverlies ten gevolg van wachten in de wachtlijn. Het tweede servermodel heeft een oneindige populatie maar een eindige wachtlijn. Net zoals in het eerste model is er dus een zeer groot aantal gebruikers maar de server heeft een beperking op het aantal aanvragen dat kan worden behandeld en qua geheugen en opslag. Niet alle inkomende aanvragen kunnen in de wachtlijn worden gezet: k≤W
(k = 0, 1, 2, . . . , W )
We passen het model nu aan om hiermee rekening te houden. De toestand van de server wordt nog atlijd door n parameter beschreven met de bijkomende voorwaarde dat er een eindig aantal toestanden zijn:
De evenwichtsvoorwaarde aan de grenzen is dus: k λ pk = p0 k = 0, 1, 2, . . . , W µ Om p0 te berekenen weten we dat het systeem zich in ’een’ toestand bevindt: # " k W W W +1 −1 X X 1 − (λ/µ) 1 − λ/µ λ = 1 ⇒ p = pk = p0 = p0 0 W +1 µ 1 − λ/µ 1 − (λ/µ) k=0
(13)
(14)
k=0
De benuttiging van de server wordt gegeven door: h i W (λ/µ) 1 − (λ/µ) U = 1 − p0 =
1 − (λ/µ)
(15)
W +1
en de fractie verloren aanvragen is dan pverlies = pW . Op een gegeven punt heeft het verlengen van de wachtrij geen invloed meer op het aantal verloren aanvragen. Het is een dalend exponentieel verband. We berekenen nu het gemiddeld aantal aanvragen in de server: N=
W X
kpk = p0
k=0
W X k=0
14
k
k (λ/µ)
(16)
Internettechnologie
Daan Pape
Met behulp van de hulpformule: W X k=0
bekomen we
kak =
W aW +2 − (W + 1)aW +1 + a (1 − a)2
(17)
h i W +1 W (λ/µ) W (λ/µ) − (W + 1) (λ/µ) + 1 h i N= W +1 1 − (λ/µ) (1 − λ/µ)
(18)
Op een gegeven moment zal het gemiddeld aantal aanvragen in de server een constante worden en niet langer stijgen indien de wachtrij langer wordt. Links zien we dus de fractie verloren aanvragen in functie van de lengte van de wachtlijn en rechts het gemiddeld aantal aanvragen in de server in functie van de lengte van de wachtlijn.
De gemiddelde verwerkingssnelheid van de server wordt nu gegeven door: W
X = U · µ + (1 − U ) · 0 = λ
1 − (λ/µ)
W +1
1 − (λ/µ)
(19)
De gemiddelde verwerkingssnelheid is dus kleiner dan de gemiddelde aankomstsnelheid omdat er aanvragen verloren gaan. De gemiddelde antwoordtijd wordt nu gegeven door: W +1
R=
W
N W (λ/µ) − (W + 1) (λ/µ) h i =S W X 1 − (λ/µ) (1 − λ/µ)
+1
(20)
Net zoals het gemiddelde aantal aanvragen zich stabiliseerd met een stijgende wachtlijn doet ook de gemiddelde verwerkingssnelheid zich en dit met hetzelfde soort verband tussen de twee, exact hetzelfde met de gemiddelde antwoordttijd, dit is zeer logisch natuurlijk. We hebben dan ook een veralgemeend servermodel met als karakteristieken: • Een oneindige populatie • De aankomstsnelheid van de aanvragen hangt af van de toestand • De behandelingssnelheid van de aanvragen hangt af van de toestand • Er is een eindige wachtlijn
15
Internettechnologie
Daan Pape
We berekenen nu weer deze formules en bekomen: pk = p0
k−1 Y i=0
W X k=0
p0
k−1 Y i=0
λi =1 µi+1
λi µi+1
(21)
" W k−1 #−1 X Y λi p0 = µ i=0 i+1
⇒
(22)
k=0
U = 1 − p0
X=
W X
µk pk
(23)
(24)
k=0
N=
W X
kpk
(25)
k=0 W X
kpk N k=0 = W R= X X µk pk
(26)
k=0
4
Hypermedia
De termen het internet en het web worden vaak verkeerdelijk als synoniemen gebruikt: • Het internet: een internationaal computernetwerk • Het web: het WWW of World Wide Web is een informatiesysteem bovenop het internet bestaande uit geconnecteerde documenten en diensten. Vroeger werden meestal adressen van ftp servers gegeven of emails met commando’s. Het internet was toen al goed uitgerold. Op het huidige web heb je echter geen technologische kennis meer nodig en verkrijg je een webpagina met links naar alle nodige documenten. We hebben dus: • Hypertext: een document waarin kan worden gelinkt naar andere documenten. Vanop een startpagina kan men dus naar alle beschikbare data gaan. • Hypermedia: het zelfde zoals hypertext maar dan voor gelijk welke media. De visie en implementatie van hypertext is veel veranderd van de originele visie van Ted Nelson. Hij had een fexibele manier van documenten linken voor ogen die multidirectioneel is en waarbij alle documenten aan elkaar hangen. Met een onderverdeling in: • Chunk-style-hypertext: keuzemogelijkheden via bv. voetnoten. • Collateral hypertext: annotaties over de eigenlijke tekst. • Strechtext: evoluerende teksten met externe fragmenten en ’LOD’. • grand hypertext: alles wat bestaat over een onderwerp.
16
Internettechnologie
Daan Pape
Het Xanadu platform van Ted Nelson alsook enkele andere platformen braken niet door omdat ze gesloten waren. De gepresenteerde informatie bevatte keuzes beperkt tot een lokale verzameling documenten. Er was n lokale databank en links naar andere systemen of software was niet mogelijk. Het idee van Tim Berners Lee werd niet enthousiast onthaald omdat het enkel tekst bevatte terwijl de andere systemen afbeeldingen, kaarten, . . . hadden. Het World Wide Web was echter heel simpel en had globale schaalbaarheid waardoor dit een van de snelst groeiende toepassingen was op het Internet. Het systeem bestaat uit 3 basiscomponenten: 1. Uniform Resource Locator (URL): dit is een unieke identificatie van resources bestaande uit een protocol, domein en pad. 2. HyperText Transfer Protocol (HTTP): dit werkt met een request/response paradigma en bevat standaardmethoden voor data. De server antwoordt dan met de gevraagde representatie. 3. HyperText Markup Language (HTML): deze taal wordt gebruikt om hypertextdocumenten op te stellen. De browser geeft deze weer en kan de URL’s gebruiken. Bovenstaande 3 zaken die samen het Web vormen zijn toevallig zo groot geworden omdat er in het begin nog geen formele definitie en analyse van de architecturale principes was. Vandaag wordt HTTP voor veel meer dan alleen maar HTML gebruikt volgens de REpresentational State Transfer of REST manier. Dit werd in 2000 voorgesteld door Roy Thomas Fielding en het is een conceptueel framework voor het analyseren van gedistribueerde hypermediasystemen zoals het Web. Het is een manier om data te bekijken en te bewerken en is toekomstbestendig: • De start is een systeem zonder ’grenzen’ • Er worden constraints toegevoegd om gewenste eigenschappen te bekomen. • De client en server zijn volledig ontkoppelt zodat er een onafhankelijke evolutie kan zijn. • Twee bekende constraints zijn: – Client-server constraint: dit leidt tot de gewenste schaalbaarheid. – Cacheability constraint: antwoorden kunnen en mogen gecached worden, ook dit leidt tot schaalbaarheid. HTTP is niet de enige implementatie van REST en niet elke HTTP toepassing houdt zich aan de REST constraints. Het is echter wel belangrijk om zich aan de REST constraints te houden om alle gewenste eigenschappen ervan te bekomen. Twee unieke constraints voor REST (en dus het Web) zijn statelessness en uniforme interface. Het toestandsloos zijn wil zeggen dat de interpretatie van een request niet mag afhangen van de vorige request. Dit leidt tot volgende eigenschappen: • Visibility: elke request bevat alle nodige context om het te begrijpen. De request is op zichzelf dus al voldoende om de interactie te visualiseren. • Reliability: het falen van een request heeft geen impact op het al dan niet falen van een andere request • Scalability: de server hoeft geen toestand bij te houden waardoor meer requests kunnen worden afgehandeld. Deze architectuur wil niet zeggen dat de server helemaal geen toestand bijhoud, we maken onderscheid tussen: • Resource state: deze wordt op de server bijghouden en betreft resources. Deze toestand is de gecombineerde toestand van alle resources binnen een applicatie en wordt wel op de server opgeslagen. Dit maakt dus geen deel uit van de statelessness constraint. 17
Internettechnologie
Daan Pape
• Application state: deze zit vervat in de body van berichten en deels op de client. Deze toestand beschrijft waar de client zich bevind in de interactie met de resource state en bevat info zoals de ’user agent’, welke links de client naartoe kan, of de client ingelogd is. . . Een resource is elk stukje informatie dat benoemd kan worden, in de web-toepassignen wereld zijn het conceptuele stukken informatie die door de server kunnen worden aangeboden. Een resource identificeert constante concepten en dus geen concrete waarden die een concept aanduiden op een bepaald ogenblik. Een resource is dus nooit gelijk aan zijn waarde. Clients kunnen de resource state bekijken en/of manipuleren en dat is net waarom een client met een server interageert. De resources zijn namelijk niet beschikbaar op de client en daarom wordt het client/server-paradigma gebruikt. Het is niet de taak van de server om de application state bij te houden. Als een antwoord verstuurd is mag de server vergeten dat dit gebeurde en dit komt de schaalbaarheid ten goede. Het maakt niet uit hoeveel clients er verbinden aangezien ze zelf hun application state bijhouden. De REST architecturale stijl benadrukt sterk de uniforme interface: • 4 constraints: identificatie van resources, manipulatie van resources via representaties, zelfbeschrijvende objecten, hypermedia als moter van application state (hypermedia constraint) • Dit leidt tot simplification, visibility en independent evolution Een resource moet uniek identificeerbaar zijn en elk stukje info dat uniek identificeerbaar is, is een resource. Een resource kan meerdere identifiers hebben maar elke identifier mag slechts naar ´e´en resource wijzen. Op het web zijn de URL’s de identifiers. In REST hebben de clients nooit rechtstreekse toegang tot resources en alle interacties gebeuren via representaties. Een representatie representeert een resource in een formaat gekozen door de client of server (in het web bv. HTML, txt, JSON, RDF, . . . ) . Dit formaat wordt ook wel het media type genoemd en eenzelfde resource kan soms in meerdere media types worden voorgesteld. Een representatie omvat de data en de metadate (bv. de HTML headers). Berichten moeten zelfbeschrijvend zijn en dus zonder voorgaande informatie kunnen worden ge¨ınterpreteerd, of dus zonder out-of-band informatie. HTPP heeft hiervoor de bekende GET, POST, PUT, DELETE, . . . methoden. Out-of-band info zou bijvoorbeeld documenten leesbaar voor mensen kunnen zijn, clients kunnen daardoor moeilijker met de toepassing interageren. Hypermedia is de motor van application state. Er wordt vereist dat de interactie gegeven wordt door informatie in hypermedia representaties die door de server uitgestuurd worden. Dit is dus fundamenteel verschillend van: • Out-of-band informatie zoals documentatie • Een lijst met stappen zoals bij RPC interacties Een REST systeem moet de representaties van hypermedia aanbieden die elementen bevatten die een client toelaten naar een volgende stap te gaan. In HTML zijn dit links, knoppen en formulieren. Andere representaties hebben andere elementen. Men verwacht dus dat een webpagina links bevat naar alle mogelijke volgende stappen, dit is echter niet altijd zo. Zo kan een webshop niet altijd een rechstreekse productlink aanbieden en men noemt dit unidirectionele links. Hypermedia is belangrijk omdat machines niet zo gemakkelijk als mensen manieren vinden om wel tot dat product te komen. Voor een machine moet men een Web API maken zodat deze gemakkelijk met de data overweg kan. In de praktijk bevatten representaties voor machines vaak geen hypermedia controls, hierdoor moetzen ze strikt geprogrammeerd worden met vaste adressen.
18
Internettechnologie
Daan Pape
REST bestaat dus uit 3 componenten: • Resources: zonder constraints en dit zijn adressen. • Acties: met constraints en dit is bv. GET, POST, . . . • Representaties: met constraints en dit si bv. JSON, HTML, . . . Met hypermedia op het web bedoelt men de simultane presentatie van informatie en controls. De representatie moet dit dus ondersteunen, maar het is niet pers´e nodig dat info en controls met elkaar verweven zijn, er moet enkel simultane toegang zijn. De affordance tussen dingen stelt hoe duidelijk het is dat je een actie kan ondernemen met iets. Sommige voorstellingen hebben een slechte affordance waarbij het niet duidelijk is welke acties je kan ondernemen met de data. Er zijn 3 types van machine clients: 1. Web browsers: bestuurd door mensen en toont hypermedia en verbetert de browsing ervaring afhankelijk van de content en representatie. 2. API client: een softwaretoepassing. 3. Autonome agent: kan met meerdere API’s interageren en complexe taken uitvoeren zonder daarvoor expliciet te zijn geprogrammeerd.
5
Metadata en semantiek
5.1
Metadata
Er is een overload aan informatie en om informatie te filteren is er nood aan metadata, de vele multimediabestanden vereisen ook metadata. Vroeger was metadata data over data waardoor men makkelijk con categoriseren, zoeken, browsen, . . . en het was een onderdeel van de eigenlijke informatie. Vandaag is metadata gestandaardiseerde en gestructureerde informatie die automatische processen kunnen sturen en er zijn verschillende types metadata: • identificatie • beschrijvend • annotaties • technisch • ... allemaal met als doel de gevonden data te begrijpen meer dan enkel en alleen te lokaliseren. In de toekomst wil men intertwingularity of het kristalliseren van informatie. Men wil kennis over de content uitdrukken en het zoeken naar informatie wordt het bevragen van kennis. Dit heeft semantische interoperabiliteit als doel wat wil zeggen dat er een medium is waarin zowel mensen als software bij het verwerken van data en content tot dezelfde conclusies kunnen komen, men genereert dus kennis. Metadata wordt gebruikt voor het begrijpen, delen, management, zoeken, verwerken, presenteren, . . . van content. Een taxonomie is een classificatie waarvan de structuur op voorhand is bepaald. Het is een hi¨erarchie met gecontroleerde woordenlijsten, thesauri, opgesteld door experts. In het begin was er enkel een classificatie voor diersoorten, maar nu zijn er voor heel veel dingen classificaties. Dit 19
Internettechnologie
Daan Pape
is een top-down aanpak. Een tag is een annotatie is een vrije tekst en het zijn sleutelwoorde die persoonlijk en informeel zijn. Waar vroeger taxonomie¨en of woordenlijsten werden geruikt om content te beschrijven worden nu tags of folksonomie¨en gebruikt die door de gebruikers worden gevormd. In een folksonomie zit geen voorafgedefinieerde structuur en/of hi¨erarchie en de gebruikers voegen samen metadata toe. Alle termen zijn dus evenwaardig en er wordt bottom-up gewerkt. Je hebt zowel brede en smalle folksonomie¨en. Het probleem met folksonomie¨en is dat er culturele verschillen zijn waarbij mensen data anders interpreteren, er zijn taalproblemen, er is ambiguiteit, spellingsfouten. Er kunnen subjectieve tags zijn, persoonlijke tags, . . . Er is een overvloed aan metadatastandaarden naar analogie met de vele multimediastandaarden. Er zijn ook standaarden die de structuur van metadata vastleggen: MODS of Medadata Object Description Schema. Dit is een XML bestand die volgens een vaste manier gestructureerd is. XML of eXtensible Markup Language is door de W3C gestandaardieseerd en het is een taal die de structuur van een document vastlegt. Een XML schema wordt gebruikt om de structuur van een document te beschrijven en zegt: • Welke elementen er mogen voorkomen. • In welke volgorde de elementen mogen voorkomen. • Welke types/waarden er mogen in staan. MODS is een XML schema waarbij een textuele specificatie de semantiek van de elementen bepaalt. Het voordeel van XML is dat zowel mensen als machines de documenten kunnen lezen ben begrijpen. Men bekomt dus gedeelde informatie voorgesteld in een algemene structuur. De huidige metadatastandaarden bepalen de structuur van de data en er zijn verschillende standaarden in ´e´en systeem waardoor er mappingen nodig zijn. Een standaard lost nog niet alles op omdat er soms nog dezelfde problemen zijn als bij tags. Zo kan men een ’creator’ property op meerdere manieren invullen. Het is moeilijk om de semantiek van metadata te beschrijven aangezien dit uit pure tekst bestaat en niet verstaanbaar is voor machines. Ook is de huidige metadata voor multimedia nog niet goed te begrijpen, twee verschillende standaarden kunnen hetzelfde beschrijven maar op een totaal verschillende manier. We moeten dus onderscheid maken tussen: Semantiek - bepaalt de betekenis van metadata elementen - gesloten beschrijving zorgt voor interoperabiliteit m.b.t. disambigu¨ıteit
Syntax - bepaalt de representatie van metadata - XML+XML schema zorgt voor interoperabiliteit m.b.t. correctheid - XML is de facto standaard
Het huidige web is bijna uitsluitend syntactisch opgebouwd.
5.2
Semantiek toevoegen aan data
XML bevat dus geen semantiek en enkel syntax, de oplossing zijn semantische web technieken: • Gebruik van RDF, RDF Schema, OWL, . . . • Er zijn ontologie¨en in plaats van XML schema’s
20
Internettechnologie
Daan Pape
Een ontologie is een formele representatie van een verzameling concepten binnen een domein en de relatie tussen deze concepten. Het wordt gebruikt om te redeneren over eigenschappen in dat domein en het kan gebruikt worden om dat domein te defini¨eren. Het bevat de volgende concepten: • Individuals (Instances) • Classes (Concepts) • Attributes • Relations • Functions • Constraints Het bestaat uit triples zoals <note, hasAuthor, Tim> die we in een graaf kunnen voorstellen. Het is essentieel dat er van URI’s gebruik wordt gemaakt. Deze URI’s wijzen naar een object en geven een unieke identificatie. De bedoeling is nu om meerdere bestaande data te linken en zo een enorme kennis te vergaren. Het Open Linked Data princiepe is een standaard procedure om domain ontologie¨en op het web te publiceren via HTTP, URI en RDF. Het is een robuuste en elegante manier om kennis te koppelen.
5.3
Het semantisch web
Om een semantisch web te maken moet de beschikbare informatie begrijpbaar zijn voor machines op een ondubbelzinnige manier. Het moet gemakkelijk zijn om de informatie te combineren en uit te wisselen. We willen dus een web van data (semantisch web) in plaats van een web van documenten (syntactisch web). Dit moet in het huidige web kunnen worden ge¨ıntegreerd. Informatie moet conceptueel worden voorgesteld door middel van gerichte grafen, dit wordt in de praktijk door RDF gerealiseerd. De structuur van het semantisch web bestaat dus uit 3 lagen:
De abstracte graafrepresentatie is onafhankelijk van de bestaande dataformaten en een verandering aan het schema van een lokale database breekt niets. Nieuwe informatie en connecties kunnen op een triviale manier aangebracht worden. Het semantisch web zorgt er dus voor dat niet alleen mensen het web begrijpen maar ook machines, de bezieler is weer Tim Berners-Lee. Deze metadata kan in de XHTML code worden verweven. Alles gaat dus om betekenisvolle representatie van data en traditionele technieken gaa nuit van een gecentraliseerd database systeem waarin alles staat. Dit is echter niet schaalbaar en staat haaks op het gedecentraliseerde web.
21
Internettechnologie
5.4
Daan Pape
Het web van data
Het semantisch web is meer dan enkel data op het web plaatsen, het is het linken van data aan elkaar (Open Linked Data). Hierbij zijn er 4 regels om het web te doen groeien: 1. Gebruik URI’s om dingen een naam te geven. 2. Gebruik van HTML URI’s (URL) zodat men namen kan opzoeken. 3. Als een URI wordt opgevraagd, geef dan nuttige data zoals RDF terug. Dit is vaak nog een probleem omdat er geen toegang is tot ruwe data, dit moet veranderen. 4. Leg links naar andere URI’s zodat data kan worden ontdekt, zoals hyperlinks In 2010 was er een poging ter aanmoediging om Open Linked Data te gebruiken en men kon sterren verdienen. Dit was echter vooral voor de overheden en publieke diensten en men kon sterren verdienen die aangaven hoever de dienst erin ging. Internationaal zijn er heel veel initiatieven om Open Linked Data aan te moedigen. Waar er vroeger een ketting van connecties tussen computers was met speciale protocollen is er nu een abstract netwerk met slechts enkele mechanismes om alle mogelijk connecties te abstraheren. Dit grote netwerk werd pas bruikbaar voor de modale mens na de opkomst van het WWW. De documenten zijn belangrijker dan de computers zelf en de WWW protocollen beschrijven hoe die documenten van de server naar de browser moeten worden verstuurd. Gebruikers zien dus enkel een web van geconnecteerde documenten maar soms moet men wel onder de moterkap kijken (404, phishing, . . . ). We zijn dus van het netwerkniveau naar een documentenniveau gegaan en nu willen we naar een data/dingen niveau gaan. Het zijn nu niet meer de documenten die interessant zijn maar wel de dingen waarover de documenten het hebben. Een goede Semantic Web Browser toont dus informatie over iets en dat kan uit verschillende bronnen komen. We hebben dus een evolutie gehad: kabels → netwerk → web → graaf documenten → data/dingen ongestructureerde content → gestructureerde content → slimme content → intelligente content In de praktijk kunnen we veel meer data linken en slimme bezoekingen, beter dan Google nu al kan. Google en Facebook gebruiken ook semantics en zijn de grote spelers. Meer specifiek hebben we volgende toepassingen: • Mashups: het is de integratie en/of visualisatie van verschillende data sets. Het automatisch samenbrengen van data is enkel mogelijk in het semantisch web. • Smart Queries: dingen zoeken met allerlei opties over de content. Zoals ’film met Peter Jackson’ en ’met Orlande Bloom’, . . . Freebase maakt dit mogelijk door een query met verschillende vocabularia te gebruiken en verschillende schema’s en datasets te combineren. DBPedia maakt dit mogelijk met SPARQL • Grote spelers schema.org is zeer belangrijk en door Google, Bing en Yahoo! gemaakt. Dit schema maakt het mogelijk te beschrijven wat er op een webpagina staat en men kan de semantiek uitdrukken door middel van HTML-microdata. Dit verbetert de zoekresultaten en maakt ze relevanter en domein specifiek. Het semantisch web is geen magische artifici¨ele intelligentie maar gewoon een goede manier om data ook voor machines begrijpbaar te maken. Het is geen herhaling van eerdere (mislukte) expirementen rond kennisrepresentatie. Het RDF model is generieker dan traditionele entiteitrelatiemodellen omdat de ene persoon de wielen van de auto kan specifieren en de andere persoon 22
Internettechnologie
Daan Pape
de kleur gewoon door van het juist vocabularium gebruik te maken. RDF mapt zeer goed op relationele databanken: record ↔ RDF node kolomnaam ↔ RDF propertyType waarde in cel ↔ waarde Relationele databanken hebben geen semantische restrictie bij het uitvoeren van joins en enkel op het datatype wat rare queries mogelijk maakt. Uitdagingen bestaan er in om generieke user interfaces te bedenken voor data-exploratie die elke vorm van data kan weergeven, iets krachtiger dan spreadsheets. Ook moeten er data policies komen om identiteit, privacy, transparantie en modellen voor trust in te bouwen. Het semantische web moet even robuust zijn als het Web dus ook met dingen als ’slashdot-effect’ rekening houden, 404 fouten, phising, . . . Een andere uitdaging is het beschrijven en annoteren van de steeds meer aanwezige multimediale data, de enorme hoeveelheid aan data masteren, . . .
6
Technologie¨ en voor het Semantisch Web
6.1
Basistechnologi¨ en
Een URI heeft volgend formaat: scheme:[//authority]path[?query][#fragment] met • Scheme: het type van de URI zoals http, ftp, mailto, . . . • authority: een domeinnaam zoals dbpedia.org • path: een pad zoals /resource/Berlin • query: niet-hi¨erarchische informatie zoals parameters • fragment: om een deel van de resource aan te duiden XML heeft dus enkele tekortkomingen en het komt er op neer dat het enkel om syntax gaat. Het idee achter RDF is om een gerichte graaf als datamodel te gebruiken. RDF of het Resource Description Framework is sinds 2004 een W3C recommendation. RDF is een datamodel dat gestructureerde data bevat en universeel en machine-leesbaar is, er wordt XML syntax voor serialisatie gebruikt. Het bestaat uit: • URI’s: referenties naar bronnen/resources • Literals: dit is een representatie van datawaarden en is gecodeerd als strings en g¨ınterpreteerd als datatypes. Literals zonder datatype worden als strings behandeld. • Empty/Blank nodes: iets wat geen naam heeft of een onbekende waarde heeft Grafen worden behandeld als een verzameling van RDF-tripels die bestaan uit een subject, predicaat en object. Daarin is toegestaan: • subject: URI’s en lege nodes • predicaat: URI’s (meestal properties genaamd) • object: URI’s, lege nodes en literals 23
Internettechnologie
Daan Pape
De graaf kan nu geconstrueerd worden op basis van een verzameling tripels. Er zijn verschillende mogelijkheden om RDF syntax in uit te drukken: • Turtle: de Terse RDF Triple Language bevat tripels als ’zinnen’ met drie ’woorden’ en een punt. Literals tussen dubbele quotes, URI’s tussen vishaken en er zijn enkele verkorte notaties. Dit is gemakkelijk te lezen maar geen W3C recommendation, normaliter wil men RDF XML-syntax gebruiken. • RDF XML-syntax: Bij deze syntax zit het object in het property welke op zijn beurt in het subject zit. In veel gevallen zijn de relaties tussen objecten complexer dan binaire relaties. RDF impliceert dit met het gebruik van hulpmethodes en de creatie van nieuwe predicaten. RDF heeft ook ondersteuning voor lijsten en er zijn twee types lijsten: • Open lijsten: RDF containers. Deze bevat dingen/leden/members die zowel resources, lege nodes als literals kunnen zijn. En we hebben: – rdf:Bag: volgordie is niet belangrijk, duplicaten toegestaan – rdf:Seq: volgorde belangrijk, dubplicaten toegestaan – rdf:Alt: lijst van alternatieven, typisch voor de waarde van een property De betekenis van de drie containers is niet meer dan een conventie en heeft dus geen formele betekenis. Het RDF-vocabularium dient om containers te beschrijven en niet om ze te defini¨eren. Mis gebruik van conventies wordt niet bestraft omdat het model zelf niet de kracht heeft om dit te controleren. • Gesloten lijsten: RDF collections. Deze laten toe om uit te drukken dat een groep enkel bestaat uit een aantal opgegeven resources (leden). De containers lieten niet toe om uit te drukken ”dit zijn alle leden van de container”. Het vocabularium is: – rdf:List (type) – rdf:first (property) – rdf:rest (property) – rdf:nil (resource: lege collectie) Net zoals bij containers zijn er geen formele voorwaren en correct gebruik wordt verondersteld. Er zijn semantische uitbreidingen zoals OWL nodig om dit af te dwingen. RDF zelf drukt ´e´en of meerdere feiten uit maar veelal willen we meer generieke kennis uitdrukken, dit wordt schema-kennis of terminologische kennis genoemd. Dit kunnen we met RDF-Schema (RDFS) en OWL uitdrukken. RDFS is een W3C recommendation en elk RDFS document is in RDF geschreven met een vaste naamruimte ’rdfs:’. Het vocabularium is generiek en niet gebonden aan specifieke domeinen en kan daardoor generiek ge¨ınterpreteerd worden. Enkele componenten: • Klassen: dit zijn verzamelingen ’dingen’ en in RDF is dit dus een verzameling URI’s. Een URI kan tot meerdere klassen behoren en Klassen kunnen met ’subClassOf’ hi¨erarchisch georganiseerd worden. Elke URI die een klasse voorstelt is een element van rdfs:Class en dit geldt ook voor rdfs:Class zelf. Verder zijn er een heleboel voorgedefinieerde klassen. • Properties: ook properties kunnen met ’rdfs:subPropertyOf’ hi¨erarchisch worden opgebouwd en ook hierop kan ’inferencing’ (zie verder) worden toegepast. Er kunnen beperkingen (restrictions) aan properties worden opgelegd die uitdrukken dat een relatie enkel mogelijk is tussen ’dingen’ van een bepaald ’rdf:type’, dit gaat ’rdfs:domain’ en ’rdfs:range’.
24
Internettechnologie
Daan Pape
Een RDF schema bevat ook impliciete kennis. Als er bijvoorbeeld een type ’ex:Textbook’ is welke een ’rdfs:subClassOf ex:Book’ is, dan zal er impliciet ook een ’rdfs:type ex:Book’ aanwezig zijn en het is niet nodig dit logisch gevolg expliciet op te nemen. Dit noemt men deductie of inferencing en er is een formele semantiek die bepaalt welke statements een logisch gevolg zijn op basis van een verzameling statements. Een reasoner produceert de impliciete kennis. We moeten in RDFS opletten voor valkuilen, bv: ex:authorOf ex:authorOf
rdfs:range rdfs:range
ex:Textbook. ex:Storybook.
Dit wil zeggen dat alls in de ’rdfs:rangen’ van ’ex:authorOf’ zowel een ’ex:Textbook’ als ’ex:Storybook’ is en niet of. Ook moeten we opletten dat de logische deductie geen extra types toevoegt, dus bij foute dingen moetne we goed opletten. ER is een nieuwe klasse ’rdfs:Container’ als superklasse van de open lijst types samen met een andere klasse ’rdfs:ContainerMembershipProperty’ welke een subklasse is van ’rdf:Property’. Deze klasse bevat properties die in containers gebruikt worden. De property ’rdfs:member’ is een superproperty van alle properties uit ’rdfs:ContainerMembershipProperty’. Reification is concretisering of materialisering. Dit zijn statements die over triples gaan. Stel de zin ’the detective supposes that the butler killed the gardener’: ex:detective ex:detective
ex:supposes ex:supposes
"The butler killed the gardener". ex:theButlerKilledTheGardener.
Bovenstaand statements werken niet omdat we iets willen zeggen over het triple: ex:butler
ex:killed
ex:gardener .
Dit lossen we op met ex:detective ex:theory ex:theory ex:theory
ex:supposes rdf:subject rdf:predicate rdf:object
ex:theory . ex:butler . ex:hasKilled . ex:gardener .
Bovenstaande zijn dus reified triples en typisch zal men een lege node (underscore) gebruiken in plaats van ’ex:theory’. ’rdf:Statement’ kan gebruikt worden om de ”centrale”node aan te duiden van een gematerialiseerd triple.
6.2
SPARQL
SPARQL staat voor SPARQL Protocol And RDF Query Language en is een query taal voor RDF net zoals XPath een query-taal is voor XML. Er is een nieuwe query-taal ontwikkelt voor RDF XML omdat er meerdere syntactisch correcte XML-voorstellingen mogelijk zijn voor eenzelfde RDF-statement. Ene bepaalde query zou dan tot verscheidene XPath-queries leiden. De taal is gebaseerd op het matchen van patronen in grafen en het eenvoudigste is een triple patroon. Men schrijft de query net zoals een RDF triple met de mogelijkheid een variabele te gebruiken en een combinatie van patronen leidt tot een basis graafpatroon. Er is een exacte match nodig om te voldoen aan dat patroon. Net zoals bij SQL zijn SPARQL-queries altijd opgebouwd uit: • ’SELECT’: bepaalt de projectie (aantal en volgorde van de data). • ’FROM’ (optioneel): duidt de databron aan
25
Internettechnologie
Daan Pape
• ’WHERE’: legt beperkingen op aan mogelijke oplossingen bv. in de vorm van graafpatroontemplates. Er worden door de SPARQL server impliciete ’joins’ gemaakt of je kan expliciete joins opgeven met ’FILTER’. Je kan ’FILTER’ ook gebruiken voor andere filtering zoals string matching.
6.3
OWL
RDFS is vrij primitief als modeleertaal voor het Web en daarom moet er een ontologie-laag bovenop RDF en RDFS komen. Ontologie-talen laten toe om expliciete en formele conceptualisaties van domeinmodellen neer te schrijven. De belangrijkste vereisen daarvoor zijn: • Een goed gedefinieerde syntax • Effici¨ente ondersteuning voor reasoning (automatisatie) • Formele semantiek (interpretatie is eenduidig bepaald) • Voldoende expressief Er moet steeds een trade-off tussen expressiviteit en effici¨ente reasoning zijn. Het is namelijk zo dat hoe rijker de taal is, hoe ineffici¨enter de reasoning wordt. Soms kan het zelfs onberekenbaar worden. Het redeneren over kennis in ontologie-talen omvat onder andere: • Lidmaatschap van klassen: als ’x’ een instantie is van de klasse ’C’, en ’C’ is een subklasse van ’D’, dan kunnen we afleiden dat ’x’ ook een instantie is van klasse ’D’. • Equivalentie tussen klassen: als klasse ’A’ equivalent is met klasse ’B’, en ’B’ is equivalent met klasse ’C’, dan is klasse ’A’ ook equivalent met klasse ’C’. • Consistentie: als ’x’ een instantie is van de klassen ’A’ en ’B’, en de klassen ’A’ en ’B’ zijn disjunct, dan wijst dit op een fout in de ontologie. • Classificatie: als bepaalde (property,value)-paren een voldoende voorwaarde vormen voor lidmaatschap van klasse ’A’, en een instantie ’x’ voldoet aan deze voorwaarden, an moet ’x’ een instantie zijn van klasse ’A’. Het automatiseren van reasoning is zeer belangrijk omdat het de consistentie van de ontologie of kennis controleert. Zo kan een statement niet tegelijk waar en vals zijn, men kan controleren op niet-bedoelde relaties tussen klassen en men kan automatisch classificeren van instanties in klassen. Bij het ontwerp van grote ontologie¨en met meerdere auteurs en bij het integreren en/of delen van ontologie¨en van verschillende bronnen zoals op het semantisch web zijn deze automatische controles zelfs onontbeerlijk. Een formele semantiek en reasoning worden typisch bekomen door het mappen van een ontologie op een bestaand en gekend logisch formalisme en het gebruik van reeds bestaande automatische reasoners voor deze formalismen. OWL kan (gedeeltelijk) gemapt worden op een Description Logic (DL): • DL is een subset van eerste-orde predicatenlogica (bv. # variabelen) • DL is een superset van propositielogica (bv. kwantoren) • OWL kan gebruik maken van reasoners zoals FaCT en RACER Zoals eerder gezegd is RDF Schema niet zo expressief en het heeft volgende beperkingen: • De locale scope van properties: ’rdfs:range’ bepaalt de range van een property voor alle klassen. In RDFS kunnen we niet uitdrukken dat beperkingen in de range enkel gelden voor bepaalde klassen. Zo eten koeien enkel planten terwijl andere dieren ook vlees eten. 26
Internettechnologie
Daan Pape
• Het disjunct zijn van klassen: bv. mannelijk en vrouwelijk. • Booleaanse combinatie van klassen: unie, doorsnede, complement • Beperkingen qua cardinaliteit: ”heeft exact twee ouders”, ”heeft ten minste ´e´en begeleider” • Speciale eigenschappen van relaties en proporties: transitiviteit (”groter dan”), unieke proporties (¨ıs moeder van”), inversie (¨eten”vs. ”wordt gegeten door”) In het ideaal geval was OWL een RDFS uitbreiding maar dit was niet mogelijk omdat RDFS een hoge expressiviteit verhindert. De combinatie van RDFS en logica leidt tot oncontroleerbare computationele eigenschappen. Zaken zoals rdfs:Class en rdf:Property zijn veel te expressief en daarop logica bouwen leidt tot beperkte reasoning support. Aangezien men dus steeds de afweging moet maken tussen expressiviteit en reasoning heeft het W3C OWL in drie vormen gereleased: 1. OWL Full: dit laat alle OWL taalprimitieven toe en men laat toe deze te combineren op een arbitraire manier met RDF en RDFS, men kan bv. een cardinaliteitsbeperking op de klasse van alle klassen toepassen. Het is volledig opwaarts compatibel met RDF (syntactisch en semantisch) wat wil zeggen dat elk RDF document een geldig OWL Full document is en elke geldige RDF(S)-conclusie is een geldige OWL Full conclusie. Het is zo krachtig dat het onbeslisbaar is en er geen complete of effici¨ente reasoning mogelijk is. 2. OWL DL: men legt beperkingen op wat betreft het gebruik van RDF- en OWL-vocabularium (’constructors’). Het is verboden dat OWL-constructors op elkaar worden toegepast en het komt dus overeen met Description Logic. Er is effici¨ente reasoning mogelijk maar het is niet compatibel met RDF. Elk OWL DL document is een geldig RDF document maar omgekeert niet vanwege de beperkingen. 3. OWL Lite: dit heeft nog meer beperkingen, is eenvoudiger te begrijpen voor gebruikers en eenvoudiger te implementeren voor ontwikkelaars. Het grote nadeel is de beperkte expressiviteit. De drie vormen zijn opwaarts compatibel met elkaar, dit is logisch want het zijn gewoon meer of minder beperkingen. Alle OWL varianten gebruiken RDF als hun syntax en instanties worden gedeclareerd zoals in RDF. De OWL constructors zijn specialisaties van hun RDF tegenhangers.
6.4
Regels
Formele logica vormt nog steeds de basis voor kennisrepresentatie en dit onder de vorm van eerste orde predicatenlogica. Dit omdat: • Het is een hoog-niveautaal voor het uitdrukken van kennis. • Het heeft een hoge expressiviteit. • Het is een goed bestudeerde formele semantiek. • Er is een precies gedefinieerde notie van logische gevolgtrekking. Er bestaan automatische ’proof systems’ die statements kunnen afleiden van een reeks premissen. Er bestaan ook bewijssystemen waarbij de semantische gevolgtrekking equivalent is met de syntactische afleiding binnen het bewijssysteem: • Geldigheid of Soundness: de regels bewaren de waarheid. • Compleetheid of Completeness: elke logische gevolgtrekking op basis van de premissen kan bewezen worden in het systeem.
27
Internettechnologie
Daan Pape
Predicatenlogica is uniek omdat er bewijssystemen bestaan die zowel geldig als compleet zijn. Dit is niet meer het geval voor hogere-orde logica. RDF en OWL zijn beide specialisaties van predicatenlogica. Ook de Horn-logica, een regelsysteem, is een specialisatie hiervan en regels kunnen op twee manieren ge¨ınterpreteerd worden: • Deductief: als alle Ai waar zijn, dan is ook B waar. • Reactief: als de voorwaarden Ai voldaan zijn, voer dan actie B uit. Regels kunnen beschouwd worden als een alternatief paradigma voor ontologie-modellering. OWL DL en Horn Logic zijn geen subset van elkaar. In OWL DL kan men bv. niet uitdrukken dat een persoon X die broer is van Y de oom is van Z waarbij Z ene kind is van Y . Met regels gaat dit als volgt: brother(X, Y ),childOf(Z, Y ) → uncle(X, Z) Regels kunnen niet uitdrukken dat een persoon ofwel een man, ofwel een vrouw moet zijn. Dit kan eenvoudig in OWL via disjuncte unie. Het integreren van ontologie- en regel-paradigma’s gaat niet omdat dit leidt tot onbeslisbaarheid. De N3 notatie is een systeem om regels te noteren. Predicatenlogcia heeft de beperking dat het enkel met monotone regels overweg kan. Stel volgende regels: R1: R2: R3:
indien verjaardag, geef korting indien niet verjaardag, geef geen korting indien verjaardag niet gekend, geef geen korting
Enkel regels 1 en 2 zijn monotoon, want: • Een conclusie blijft geldig ook al komt er nieuwe info of kennis in het systeem of is er missing data. • Monotone regels zijn een speciaal geval van predicatenlogica Er zijn drie stappen van abstractie van de gebruikte regels: • Er wordt een specifieke regel gebruikt voor twee resources (instanties). • Er wordt een algemenere regel gebruikt voor de relatie (predikaat). • Er wordt een algemene regel gebruikt voor alle symmetrische predicaten.
6.5
Redeneren op meta-niveau
Zowel kennis als schemakennis worden expliciet en formeel gedeclareerd. De intelligentie wordt dus verschoven van de software-laag naar de data/informatielaag. Software engineering wordt gelijk aan knowledge engineering. De regels zijn niet langer het primair medium om een doel te bereiken en ze ondersteunen de predicaten die dit doel uitdrukken.
7
Video in het Web
Waar het web vroeger uit documenten bestond is er nu een explosieve groei van de hoeveelheid multimidiale data die door gebruikers online wordt geplaatst. Er is dus nood aan een effici¨ente annotatie en ’retreival’ waarbij persoonlijke voorkeuren centraal moeten staan. HD wordt stilaan ook op het Web de norm en er is nood aan effici¨ ente adaptatie en aflevering van multimedia. Statische afbeeldingen zijn volleidg ge¨ıntegreerd in de webtechnologie stack. Browsers hebben eigen decoders, er kan met css gestyled worden een javascript heeft low level toegang tot eigenschappen. Video is eerder een extentie op het web en er zijn veelal plugins nodig omdat browsers 28
Internettechnologie
Daan Pape
geen eigen decoders hebben. Er is dan ook vaak geen directe link tussen een URI en de eigenlijke media resource. Er is nog geen integratie in de stack van webtechnologie¨en. HTML 5 bied met het
