Decentralized Knowledge Graphs on the Web
Christian Aebeloe · 2022
The increasing popularity of the Web of Data has over the past years caused a significant increase in the number of open knowledge graphs published on the Web.However, the structure of the Semantic Web today relies totally on the data providers to maintain Web services that provide efficient and scalable access to the knowledge graphs, as well as to keep the data up-todate.Without any monetary incentives to do so, publicly available knowledge graphs often become unavailable and outdated, making it difficult to trust the data available in the knowledge graphs.As a remedy, this thesis investigates and addresses the availability, scalability, and updatability issues with the aim of making knowledge graphs on the Web available, scalable, and updatable.First, the thesis explores load-balancing in client-server architectures in order to increase the availability and scalability of the knowledge graphs under heavy query processing load by introducing a system that we call WiseKG.To optimize queries in such a setup, WiseKG decomposes the query into star-shaped subqueries and determines, using a cost model that considers factors such as the current load on the server and the data transfer overhead, whether each subquery can be processed more efficiently by the client or the server.A comprehensive experimental evaluation shows that WiseKG significantly improves query processing performance for high demanding workloads compared to state-of-the-art systems while being able to answer more queries without timing out.Second, the thesis addresses the availability and scalability issues from a different point of view by proposing a decentralized Peer-to-Peer (P2P) architecture for sharing and querying knowledge graphs, called Piqnic.In Piqnic, nodes act as both clients and servers and thus maintain a local datastore (a set of knowledge graph fragments) and a local view over the network (a set of neighboring nodes).Piqnic replicates the fragments over multiple nodes within the network, ensuring the availability of the data even if the uploading node fails.An experimental evaluation shows that by doing so, Piqnic maintains high availability even when a large part of the nodes fails.Third, the thesis introduces two novel indexing schemes that allow nodes iii to determine which nodes hold relevant data to which subquery: (1) baseline locational indexes that map each predicate in the query to the nodes that hold relevant data to each predicate, and (2) Prefix-Partitioned Bloom Filter indexes that represent the set of subjects and objects in a fragment as a partitioned bitvector that allows the nodes to ascertain the joinability of two fragments.An experimental evaluation supports the hypothesis that such indexes significantly improve query processing performance while decreasing the network usage compared to Piqnic.Fourth, the thesis addresses the updatability issue by introducing ColChain, a system that allows the users to collaborate on keeping the data up to date.ColChain divides the P2P network into communities of nodes and relies on community-wide consensus to allow nodes to propose and apply consensual updates to the fragments.Furthermore, ColChain represents the entire history of updates to a fragment as a chain of updates, allowing nodes to trace-back faulty updates to their origin, as well as to dynamically roll-back fragments to an earlier version and process queries over them.A comprehensive experimental evaluation shows that ColChain provides efficient community-wide consensual updates to the fragments without incurring a significant cost on query performance.Fifth, the thesis demonstrates ColChain and introduces a fully functioning ColChain client with a graphical UI.The demonstration highlights how users can navigate the fragments stored by a particular ColChain node.Furthermore, the demonstration shows how users can participate in keeping the fragments up to date, as well as how queries can be processed over a previous version of the fragments.Last, the thesis introduces the Lothbrok approach to optimizing SPARQL queries in the decentralized setup.In particular, Lothbrok fragments data based on characteristic sets (predicate families) and uses star-shaped query decomposition similar to WiseKG.To accommodate the fragmentation technique, Lothbrok further introduces a novel indexing scheme, called Semantically Partitioned Bloom Filter indexes, that associates the objects in a fragment with the predicates they occur in triples with.Lothbrok nodes use these indexes to build a query execution plan in consideration of cardinality estimations, the compatibility of fragments for the given query, and the locality of the data.Lothbrok is further able to delegate subqueries to other nodes in the network such that the network overhead is minimized.A comprehensive experimental study shows a performance increase of up to two orders of magnitude when comparing Lothbrok to Piqnic and ColChain while the network usage is lowered as well. ResuméDet Semantiske Webs stigende popularitet har over de seneste år forårsaget en væsentlig stigning i antallet af frit tilgængelige vidensgrafer på nettet.Strukturen af det Semantiske Web afhænger imidlertid i dag af, at dataudbyderne vedligeholder webtjenester, der giver effektiv og skalerbar adgang til vidensgraferne, samt holder dataen opdateret.Manglen på monetære tilkyndelser til at vedligeholde vidensgrafer er i høj grad skyld i at frit tilgængelige vidensgrafer ofte er utilgængelige og forældede, hvilket gør det svært at stole på den tilgængelige data.Denne afhandling undersøger løsninger til hvert af disse problemer individuelt med formålet om at gøre åbne vidensgrafer mere tilgængelige, skalerbare og opdaterbare.For det første udforsker denne afhandling belastningsbalancering i klientserver arkitekturer for at øge tilgængeligheden og skalerbarheden af vidensgraferne, når mange forespørgsler bliver behandlet samtidigt, og introducerer et system kaldet WiseKG.For at effektivisere behandlingen af forespørgsler i sådan et setup, nedbryder WiseKG forespørgslen til stjerneformede underforespørgsler og fastlægger, baseret på faktorer såsom den nuværende belastning på serveren samt overhead af dataoverførsel, om hver forespørgsel kan behandles mest effektivt af klienten eller serveren.En omfattende undersøgelse viser, at WiseKG forbedrer ydeevnen for behandling af forespørgsler væsentligt for højt krævende arbejdsbyrder sammenlignet med state-of-theart systemer, samt kan besvare flere forespørgsler uden at time ud.For det andet undersøger afhandlingen tilgængeligheds-og skalerbahedsproblemerne fra et andet perspektiv ved at foreslå en decentraliseret Peer-to-Peer (P2P) arkitektur til deling og forespørgselsbehandling af vidensgrafer, kaldet Piqnic.Noder i Piqnic agerer både som klienter og servere, og vedligeholder derfor et lokalt datalager (en mængde af vidensgraffragmenter), samt en lokal oversigt over netværket (en mængde af nabonoder).Piqnic replikerer fragmenterne på flere noder i netværket for at sikre tilgængeligheden af dataen selv i tilfælde af, at den uploadende node fejler.En eksperimentel undersøgelse viser, at Piqnic fastholder høj tilgængelighed, selv når en stor andel af noderne fejler.For det tredje introducerer afhandlingen en ny form for decentraliseret inv deks, der tillader noder i et P2P-netværk at fastslå præcis hvilke noder, der indeholder relevant data til hvilke underforspørgsler: (1) locational indekser, der matcher hvert prædikat i forespørgslen med de noder, der indeholder relevant data for dem, og (2) Prefix-Partitioned Bloom Filter-indekser der repræsenterer mængden af subjekter og objekter i et fragment som en opdelt bitvektor, der lader noderne fastslå om to fragmenter producerer join-resultater for en given forespørgsel.En eksperimentel undersøgelse understøtter hypotesen om, at sådanne indekser forbedrer ydeevnen for behandling af forespørgsler væsentligt ved at formindske belastningen på netværket sammenlignet med Piqnic.For det fjerde adresserer afhandlingen opdaterbarhedsproblemet ved at introducere ColChain, et system der tillader brugerne at samarbejde om at holde dataen opdateret.ColChain deler netværket op i mindre fællesskaber af noder og bruger konsensus over fællesskaberne til at lade noder i netværket foreslå og anvende konsensuelle opdateringer til vidensgraferne.Ydermere repræsenterer ColChain hele opdateringshistorikken af et fragment som en kæde af opdateringer, hvilket lader brugerne spore fejlslagne opdateringer til deres oprindelse, samt dynamisk at behandle forespørgsler over tidligere tilgængelige versioner af vidensgraferne.En omfattende undersøgelse viser, at ColChain tillader effektive konsensuelle opdateringer af fragmenterne, foruden at pådrage sig en unødvendig omkostning på ydeevnen for behandling af forespørgsler.For det femte demonstrerer afhandlingen ColChain ved at introducere en fuldt fungerende ColChain-klient med en grafisk brugerflade.Demonstrationen fremhæver, hvordan brugere kan navigere i vidensgraferne lagret af en bestemt ColChain-node.Desuden viser demonstrationen, hvordan brugere kan deltage i at holde vidensgraferne opdateret, samt hvordan forespørgsler kan behandles over tidligere versioner af vidensgraferne.Til sidst introducerer afhandlingen Lothbrok, en metode til at optimere SPARQL-forespørgsler i den decentraliserede kontekst.Specifikt fragmenterer Lothbrok vidensgraferne baseret på characteristic sets (prædikatfamilier) og bruger stjerneformet nedbrydelse af forespørgslerne lignende WiseKG.Lothbrok introducerer ydermere en ny måde at indeksere dataen på ved at introducere Semantically Partitioned Bloom Filter-indekser, som associerer objekterne i et fragment med de prædikater, de optræder i tripler med.Lothbrok-noder bruger disse indekser til at bygge en plan for behandling af forespørgslerne, der tager højde for estimerede kardinaliteter, kompatibiliteten af fragmenter for en given forespørgsel, samt lokaliteten