Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Wissensmanagement in der Bioinformatik

Neue Entwicklungen im Datenbankbereich und in der Bioinformatik

• wann? Dienstags, 15-17 Uhr
• wo? RUD25, 3.101

Dieses Seminar wird von den Mitgliedern der beiden Arbeitsgruppen als Forum der Diskussion und des Austauschs genutzt. Studenten und Gäste sind herzlich eingeladen.

Folgende Termine und Vorträge sind bisher vorgesehen:

Zusammenfassungen

HUODINI – Flexible Information Integration for Disaster Management (Bastian Quilitz)

Fast and effective disaster management requires access to a multitude of heterogeneous, distributed, and quickly changing data sets, such as maps, satellite images, or governmental databases. In the last years, also the information created by affected persons on web sites such as flickr.com or blogger.com became an important and very quickly adapting source of information. We developed HUODINI, a prototype system for the flexible integration and visu-alization of heterogeneous data sources for disaster management. HUODINI is based on Semantic Web technolo-gies, and in particular RDF, to offer maximal flexibility in the types of data sources it can integrate. It supports a hybrid push/pull approach to cater for the requirements of fast-changing sources, such as news feeds, and maximum performance for querying the integrated data set. In this paper, we describe the design goals underlying our approach, its architecture, and report on first experiences with the system.

Modellgetriebene Entwicklung von Informationsintegrationssystemen (Susanne Busse)

Informationsintegrationssysteme (IIS) bieten einen lesenden Zugriff auf eine Menge heterogener Datenquellen. Die Ansaetze fuer die Informationsintegration sind jedoch sehr unterschiedlich: Von schema-getriebenen Ansaetzen, wie sie etwa in mediatorbasierten Systemen zu finden sind, bis hin zu Suchmaschinen sind verschiedene Varianten zu finden. Auch bei Datenmodellen und Integrationsalgorithmen kann aus einer Fuelle existierender Ansaetze gewaehlt werden. In der Softwareentwicklung wird zunehmend auf ein modellgetriebenes Vorgehen gesetzt, das auch den Umgang mit verschiedenen Varianten ermoeglicht. In dem Vortrag soll gezeigt werden, wie die modellgetriebene Entwicklung auf Informationsintegrationssysteme angewendet werden kann. Kernstueck ist dabei die explizite Modellierung von Merkmalen: Sie kann sowohl genutzt werden, um anforderungsgerecht existierene IIS-Bausteine auszuwaehlen und in einen IIS-Entwurf zu integrieren als auch um ein existierendes System zu beschreiben und zu bewerten. In dem Vortrag wird dies anhand typischer Fragestellungen bei der Entwicklung eines IIS diskutiert.

Semantische Anfragen an PubMed mit SPARQL (Johannes Vogt)

Die Datenbank PubMed enthält über 16 Millionen Abstracts medizinischer und biomedizinischer Veröffentlichungen. Suchanfragen an PubMed erfolgen stichwortbasiert und sind somit oft unpräzise. Die dem Vortrag zugrundeliegende Diplomarbeit beschäftigt sich mit dem Entwurf eines Systems, das semantische Anfragen an Inhalte der Datenbank PubMed mit der Graphanfragesprache SPARQL ermöglichen soll. Der als Anfragegrundlage dienende Graph besteht hierbei aus Relationen zwischen biomedizinischen Fachbegriffen. Die Begriffe und Relationen werden von der Textmining-Pipeline des Tools AliBaba in den PubMed-Abstracts gefunden und markiert. Die Relationen müssen im RDF-Datenmodell vorliegen, um SPARQL-Anfragen darauf ausführen zu können. Als Triple Store wurde das Jena Semantic Web Framework verwendet. Darüber hinaus wurde das System testweise um die Gene Ontology (ein Vokabular zur Beschreibung von Genen) erweitert. In dem Vortrag werden desweiteren Möglichkeiten erörtert, mit denen die hierarchische Struktur der Gene Ontology in Anfragen berücksichtigt werden kann. Zudem wird ein Tool vorgestellt, mit dem die SPARQL-Anfragen gesendet, und deren Ergebnisse visualisiert werden.

Cost-based Optimization of Graph Queries in Relational Database Systems (Silke Trißl)

Many applications require efficient management and querying of graph structured data. For example, Systems Biology studies metabolic pathways and gene regulation networks modeled as directed graphs. These graphs consist of tens of thousands of molecules and interactions between them. To get a better understanding of these networks biologists need to query the networks and extract information. In this paper we propose a framework for cost-based optimization of graph queries in relational database management systems. The result of graph queries are subgraphs of queried graphs that are selected based on conditions on nodes and paths. We present the pathway query language as syntax to express graph queries. We show how to utilize techniques of classical cost-based query optimization to optimize graph queries. To handle graph specific predicates, such as the existence of paths, we propose new operators. In addition we describe two implementations of path operators in more detail and give an overview of future work.

Fast and Practical Indexing and Querying of Very Large Graphs (Silke Trißl)

Many applications work with graph-structured data. As graphs grow in size, indexing becomes essential to ensure sufficient query performance. We present the GRIPP index structure (GRaph Indexing based on Pre- and Postorder numbering) for answering reachability queries in graphs. GRIPP requires only linear time and space. Using GRIPP, we can answer reachability queries on graphs with 5 million nodes on average in less than 5 milliseconds, which is unrivaled by previous methods. We evaluate the performance and scalability of our approach on real and synthetic random and scale-free graphs and compare our approach to existing indexing schemes. GRIPP is implemented as stored procedure inside a relational database management system and can therefore very easily be integrated into existing graphoriented applications.

Informationsmanagement in Krisensituationen - Erfahrungen und Konsequenzen aus dem Hochwasser in Sachsen 2002 (Stephan Gottwald)

Die Hochwasserereignisse der letzten Jahre in Europa haben dazu geführt, dass neue IT-Systeme für den Einsatz zur Gefahrenabwehr entwickelt wurden. Umweltinformationssysteme in Echtzeit werden immer wichtiger bei weltweit sich ständig verändernden meteorologischen Verhältnissen. Die Überschwemmungen 2005 und 2006 in Süd- und Ostdeutschland haben gezeigt, wie wichtig die schnelle Reaktion des Zivilschutzes ist. Die Zeitspanne, die nötig ist, um die Öffentlichkeit zu alarmieren, kann durch Echtzeit-Systeme drastisch verkürzt werden. Diese Systeme müssen in eine Kommunikationsinfrastruktur eingebettet sein mit eindeutig definierten Verantwortungsbereichen, kurzen Informationswegen, und der Akzeptanz zeitgemäßer Technologien, um der katastrophalen Auswirkung von Hochwasser entgegen zu wirken.

The SPARQL Query Graph Model for Query Optimization (Olaf Hartig)

The Semantic Web community has proposed several query languages for RDF before the World Wide Web Consortium started to standardize SPARQL. Due to the declarative nature of the query language, a query engine should be responsible to choose an efficient evaluation strategy. Although all RDF repositories provide query capabilities, some of them require manual interaction to reduce query execution time by several orders of magnitude. In this paper, we propose the SPARQL query graph model (SQGM) supporting all phases of query processing. On top of the SQGM we defined transformations rules to simplify and to rewrite a query. Based on these rules we developed heuristics to achieve an efficient query execution plan. Experiments illustrate the potential of our approach.

What's new? What's certain? - Scoring Search Results in the Presence of Overlapping Data Sources (Silke Trißl)

Data integration projects in the life sciences often gather data on a particular subject from multiple sources. Some of these sources overlap to a certain degree. Therefore, integrated search results may be supported by one, few, or all data sources. To reflect these differences, results should be ranked according to the number of data sources that support them. How such a ranking should look like is not clear per se. Either, results supported by only few sources are ranked high because this information is potentially new, or such results are ranked low because the strength of evidence supporting them is limited. We present two scoring schemes to rank search results in the integrated protein annotation database Columba. We define a surprisingness score, preferring results supported by few sources, and a confidence score, preferring frequently encountered information. Unlike many other scoring schemes our proposal is purely data-driven and does not require users to specify preferences among sources. Both scores take the concrete overlaps of data sources into account and do not presume statistical independence. We show how our schemes have been implemented efficiently using SQL.

Simulation und Qualitätsbewertung von LC/MS-Maps (Alexander Haupt)

In dieser Diplomarbeit werden sowohl ein Simulator als auch ein Klassifizierer für LC/MS-Maps entwickelt und getestet. Dafür werden zunächst moderne Verfahren zur Analyse von Proteinen anhand von Massenspektren vorgestellt, grundlegende Begriffe eingeführt und anschließend LC/MS-Maps unter dem Aspekt ihrer Simulationsmöglichkeit genauer analysiert. Es werden eine Reihe von Simulationsmodellen entwickelt, die als Grundlage für den implementierten MapSimulator dienen. Im Anschluss daran wird gezeigt, dass dieser in der Lage ist, anhand gegebener Proteinsequenzen sowohl einzelne Massenspektren als auch vollständige LC/MS-Maps zu simulieren, deren Qualität durch einstellbare Messungenauigkeiten und Rauschintensitäten vielfältig steuerbar ist. Im zweiten Teil der Arbeit wird ein Programm entwickelt, mit dem sich LC/MS-Maps hinsichtlich ihrer Qualität klassifizieren lassen. Zuerst werden eine Reihe existierender Verfahren zur Abschätzung der Qualität von Tandem-Massenspektren vorgestellt und ihre mögliche Anwendung auf LC/MS-Maps diskutiert. Auf Grundlage eines angepassten intensitätsbasierten Qualitätsmaßes wird daraufhin ein Klassifikator mit Hilfe einer Support Vector Machine implementiert, der in den anschließenden Tests mit experimentellen und simulierten Maps eine Klassifikationsgenauigkeiten von bis zu 90% erreicht.

Indexierung von RDF-Daten für SPARQL-Anfragen (Christian Rothe)

Das Resource Description Framework (RDF) ist das fundamentale Datenmodell des Semantic Webs. In jüngsten Entwicklungen kristallisiert sich SPARQL als künftiger Standard des W3Cs für die Anfrageformulierung an RDF-Datensammlungen heraus. Da RDF ein graphbasiertes Datenmodell ist, liegt der Bearbeitung einer SPARQL-Anfrage das Subgraphisomorphieproblem zugrunde, also die Suche mit einem Graphmuster nach passenden Subgraphen des Datengraphs. Dieser Prozess ist sehr rechenintensiv und daher wird in dieser Diplomarbeit ein Ansatz vorgeschlagen, um die Komplexität des Problems zu reduzieren. Kern des Ansatzes ist die Einführung von Indexen in Form materialisierter Anfragen, um einen Teil der Kosten zu sparen. Ausgehend von nutzerdefinierten Indexen wird das Problem der Überdeckung eines Anfragemusters durch Indexmuster beschrieben und ein Kostenmodell für deren Verwendung eingeführt. Wir studieren das Problem der Auswahl einer optimalen Indexmenge für eine gegebene Anfrage und schließlich erfolgt eine Evaluation des Ansatzes durch Implementation und Messungen.

Predicting Protein Function from Phenotypes (Philip Groth)

In our study presented in this talk, phenotypes have been used to generate new ways of clustering genes into functional groups. We have used phenotypes – described in textual form – to predict protein function with text clustering methods. I will show that these clusters correlate well with other indicators for functional coherence in gene groups, such as functional annotations from the Gene Ontology (GO) and protein-protein interactions. We have predicted GO-terms from the biological process sub-ontology for some groups with up to 86.5% precision and 64.2% recall. I will discuss some examples for gene groups derived from clustered phenotypes that reveal high biological coherence, and other groups with inconsistent GO-annotations that could be resolved. I will show that systematically analyzing phenotype data on a large scale are well worth the effort.

Linked Data, DBpedia and D2R Server - Building blocks for the Emerging Web of Data (Chris Bizer, Freie Universität Berlin)

The basic idea of Linked Data is to set RDF links between data items within different repositories. These links enable users to navigate from one data source into the other using Semantic Web browsers. They also enable Semantic Web Search Engines to crawl data from a (theoretically) unbound set of data sources and to provide sophisticated query capabilities over the crawled data. The talk will illustrate the principles of Linked Data using DBpedia and the W3C SWEO Linking Open Data community project as examples. Afterwards, it is shown how D2R Server and the D2RQ mapping language can be employed to integrate existing relational databases into the Web of Data.

Tools and Concepts for extending Siemens’ DirX LDAP-Server - DirX Index Wizard (Lukas Dölle)

A fundamental part of database design is selecting indexes, because picking the right set of indexes can dramatically improve performance. Hence a tool for automating the choice of indexes is desirable. This selection problem, a variation of the well-known knapsack problem, has been studied for several relation database management systems (RDBMSs). DirX is an implementation of the 1993 X.500 Directory Services standard developed by Siemens AG. The index wizard uses techniques from RBDMS and adapts and extends them to the hierarchical environment of DirX. The tool consists of two components, the log analyzer and the index advisor. First, the DirX-Log is analysed in order to discover significant queries and query pattern and define a workload for further analysis. The second component generates, evaluates and recommends sets of indexes by invoking the DirXQuE³ – DirXQuery Evaluation and Execution Engine – an optimizer for Siemens’ DirX. The optimizer is also able to select hypothetical indexes for executing the workload, i. e. indexes which aren’t actually present in the database. The recommendation of the index wizard is the set of indexes which provides the minimal costs without exceeding a given disc space constraint.

Towards Effective and Efficient Behavior-based Trust Models (Prof. Klemens Boehm, Univ. Karlsruhe)

Trust models have been touted to facilitate cooperation among unknown entities. In our current work, we are interested in behavior-based trust models, i.e., models that derive the trustworthiness of an entity from its behavior in previous interactions. Existing proposals in this field typically feature one specific trust model. Further, various publications exist which have proposed different centrality measures to rank individuals, i.e., compute their reputation based on feedback, and have demonstrated their effectiveness in certain (rather specific) situations. This presentation in turn proposes a framework for behavior-based trust models for open environments with the following distinctive characteristic. Based on a relational representation of behavior-specific knowledge, we propose a trust-policy algebra allowing for the specification of a wide range of trust policies. Since the evaluation of the standing of an entity requires centrality indices, we propose a first-class operator of our algebra for their computation. The presentation concludes with an objective comparison of the effectiveness of the various centrality measures in reputation systems.

Hierarchische Versionierung in relationalen Datenbanken (Karsten Lohse)

Das Ziel meiner Studienarbeit ist die Entwicklung einer leistungsfähigen hierarchischen Versionierungsstrategie in relationalen Datenbanken, die auch den Zugriff von Altanwendungen ermöglicht, die diese Versionierung nicht unterstützen. Die entwickelte Strategie wurde mit den Daten von SwissProt gemessen werden. Diese Messung wurde mit einer Datenbank ohne Versionierung und mit dem Oracle Workspace Manager verglichen werden.

GROPUS - an Adaptive Approach to Information Extraction (Peter Siniakov)

While the ultimate goal of natural language processing -- understanding and communication in natural language -- still remains out of the scope of modern research, the focus of the text-based NLP is being increasingly relocated towards solving less complex, but very relevant practical problems in text processing and analysis. One of the most promising efforts in this area is information extraction (IE). Internet, mass media, scientific literature are the source of huge, continuously growing amount of information that is comprised by natural language texts and stored in digital form. This information can hardly be immediately accessed and processed by computers while human access is often connected with a time-consuming search. Extracting and storing it in a formal representation (e.g. in form of relations in databases) allows efficient querying and easy administration of the extracted data. Moreover, information stored and queried in a canonical way can be processed and interpreted by computers without human interaction; it can serve for establishing ontologies, creation of knowledge bases and data analysis. The area of IE comprises techniques, algorithms and methods performing two important tasks: finding (identifying) the desired, relevant data in natural language texts and storing it in a structured representation suitable for automatic processing. First IE systems relied on domain-specific extraction rules written by a domain expert requiring large human effort and lacking portability to other domains. To compensate the insufficiencies of the classical rule-based approach human effort should be adequately replaced by a learning component. In my talk I will present an adaptive, rule-based algorithm for IE that autonomously learns the extraction rules. The algorithm is based on induction learning deriving general extraction rules from a set of sample extractions annotated by a human in a training corpus. Requiring only an annotated training corpus and no additional resources the approach is portable to different application domains and even languages. The extraction rules incorporate linguistic patterns that capture typical expression forms of extracted information in a given text corpus. We introduce a higher-order formal pattern specification language that supports regular expressions, permutation, negation and hierarchical XML structures significantly extending common pattern models. Linguistic patterns are not restricted to a fix context window, but encode whole sentences as primary semantic units of natural language. The proposed pattern language is powerful and expressive enough to capture non-trivial kinds of phrases and sentences containing relevant information. The linguistic patterns are matched with linguistically preprocessed texts that have a valid XML markup. Regarding linguistic patterns as XML queries we reduce the problem of IE to XML query evaluation. Having developed formal semantics and an efficient query evaluation algorithm for the pattern language we create a new XML query language, which is especially suitable for querying XML annotated texts. Beginning with the rules generated from training instances, which were extracted by the human, rules are generalized to account for different kinds of information expression in the texts. The generalization of rules is formally specified and involves beside rule merging abstraction of single rules and substitution of extracted parts in context of different rules. For establishing a similarity measure for extraction rules and rule merging an algorithm for determination of optimal alignment of two sequences with minimum runtime (which is an extension of the LCS problem) has been designed and its correctness proved. To achieve a gradual generalization of extraction rules the rule learning algorithm includes validation of induced rules and rule correction. We demonstrate the effectiveness of our approach comparing its performance with other state of the art approaches achieving comparable or even best results depending on the kind of texts and assess its potential comparing its results with the human performance. Based on varying performance of different approaches on different corpora conclusions about the efficiency of statistical and rule-based approaches for different kinds of text are made. The quantitative investigation is supplemented by the analysis what factors influence the extraction quality, what are the sources of errors etc. Finally, we draw a conclusion in what conditions application of IE in general is expedient, what kinds of text can be managed and characterize the range of environments where the presented approach can be usefully utilized.

Efficient Exploitation of Similar Subexpressions for Query Processing (Prof. Freytag)

Complex queries often contain common or similar subex-pressions, either within a single query or among multiple queries submitted as a batch. If so, query execution time can be improved by evaluating a common subexpression once and reusing the result in multiple places. However, current query optimizers do not recognize and exploit similar subex-pressions, even within the same query.

Design of a Scientific Workflow for the analysis of Microarray Experiments with Taverna and R (Marcus Ertelt)

Microarrays erlauben Biologen die Aktivität von mehreren Zehntausend Genen von verschiedenen Gewebe- oder Zelltypen zu messen. Es entstehen dabei gewaltige Datenmengen, welche mit verschiedensten Datentransformationen und statistischen Analysien aufbereitet und ausgewertet werden müssen. Einige der besten Methoden für die Auswertung von Microarrays sind für die Programmiersprache R als Teil des Bioconductor Projektes implementiert. Oft müssen Biologen und Mediziner auf teure, proprietäre Software oder spezialisierte Bioinformatikfirmen ausweichen, um qualitativ hochwertige Ergebnisse zu erhalten. In meiner Diplomarbeit untersuchte ich die Möglichkeit gängige Methoden des Bioconductor Projektes mit Hilfe von Scientific Workflows bzw. Scientific Workflow Management Systems nutzbar zu machen und Workflows zu entwickeln, welche die gängigsten Aufgaben- und Fragestellungen bezüglich Microarrays lösen. Auf diese Art könnten Nutzer der Workflows selbstständig Analysen durchführen, ohne mit der Programmiersprache R direkt in Kontakt zu kommen oder weiteres Wissen über Bioconductor zu benötigen. Diese Workflows wurden mit Hilfe von Taverna, einem Scientific Workflow Management System mit Ursprüngen in der Bioinformatik entwickelt. Kernkomponenten der Workflows sind Web Services, welche die Funktionalität von Bioconductor-Methoden anbieten. In diesem Vortrag möchte ich einen kurzen Einblick in die Probleme und Fragestellungen von Microarrays geben und anschließend die Entwicklung der Workflows und deren Vor- und Nachteile erläutern. Zum Schluss soll, wenn möglich, einer der Workflows direkt mit Taverna vorgeführt werden.

Extend data sources available in AliBaba (Kevin Arnoult)

The AliBaba software aims to graphically display results obtained using the PubMed search engine. The purpose of this three-months project is to integrate into AliBaba two other sources of information: the KEGG pathways, and proteins extracted from protein-protein interactions (PPI) databases. The main challenge is to extract the information from different sources that have different forms. KEGG pathways requires the extraction of data from HTML pages, XML files, and flat files. The PPI databases can be accessed through online search engines; therefore proteins can be extrated from HTML pages generated according to the query. Different methods of data extraction have been tested in order to find the ones who give the best results depending on the source. A particular interest has been put on RoadRunner and XWRAP, two automatic wrapper generation tools. This project was an opportunity to test these systems in a concrete situation. However due to poor results in the extraction of data with these tools, more “classic” methods have been used. XML files have been parsed using the JDOM API, while flat files and static HTML pages have been accessed using regular expressions. The Java Swing HTML parser has been used to extract data from the dynamic HTML pages. At present the system developed gives the results expected. Nevertheless it can be noted that the methods used to extract data from HTML pages may not work if the structure of the pages are modified. Moreover this work may need further research in order to provide a better display when many information are added to AliBaba.

Finden von Präfix- und Suffix-Inklusionsbeziehungen zwischen RDBMS (Jan Hegewald)

Bisher gibt es kein standardisiertes Konstrukt um semantische Zusammenhänge zwischen verschiedenen Datenbanken zu beschreiben. Solche Zusammenhänge können Verweise von Entitäten einer Datenbank, etwa über Krankheiten, auf Entitäten einer anderen sein, die beispielsweise Proteine beschreibt. Daher müssen externe Verweise in Datenbanken nachträglich gefunden werden. Insbesondere bei der Integration von Datenquellen ist dies eine wichtige Aufgabe. Da praktisch jedes Attribut einer Datenquelle auf jedes andere der zu integrierenden Datenquelle verweisen könnte, sind sehr effiziente Algorithmen erforderlich um eine automatische Erkennung überhaupt durchführbar zu machen. In diesem Vortrag wird eine Diplomarbeit als Teil des Projektes Aladin vorgestellt, die sich mit der automatischen Erkennung von Präfix- und Suffix-Inklusionsbeziehungen zwischen Life-Sciences-Datenbanken befasst.

Search Component for DESWAP (Carmen Garcia Valero)

Nowadays, a lot of Semantic Web applications are continually being developed. Within the DESWAP project (Development Environment for Semantic Web APplications) it is being developed a methodology and procedure for the development of software systems that apply Semantic Web technologies and a supporting framework. The DESWAP environment will basically offer two main functionalities. First, it will assist software engineers in creating the software model during the design phase of the proposed procedure. Based on the mentioned idea, users can determine and specify functionalities that support the activities in the software model and DESWAP suggests software products that offers these functionalities. To enable these tasks, DESWAP uses Semantic Web technologies, like knowledge bases and reasoning. It have been developed an ontology that defines the relevant concepts (e.g. software products, software types, functionalities). To establish a knowledge base upon this ontology, DESWAP needs an appropriate interface. The MSC Dissertation focuses on the development of an appropriate search facility. It is supposed to permit finding specific entities in the knowledge base (i.e. concept instances) that comply with certain criteria. The Dissertation focuses this new search facility in the main concepts instances stored on the DESWAP Knowledge base, Software, Functionality, Functionality Property and Property Values. Along the report it is going to be described the design, implementation and giving some examples of the prototype of this component.

High-Precision Function Prediction using Conserved Interactions (Samira Jaeger)

The recent availability of large data sets of protein- protein-interactions (PPIs) from various species offers new opportunities for functional genomics and proteomics. We describe a method for exploiting conserved and connected subgraphs (CCSs) in the PPI networks of multiple species for the prediction of protein function. Structural conservation is combined with functional conservation using a GeneOntology-based scoring scheme. We applied our method to the PPI networks of five species, i.e., E. coli, D. melanogaster, M. musculus, H. sapiens and S. cerevisiae. We detected surprisingly large CCSs for groups of three species but not beyond. A manual analysis of the biological coherence of exemplary subgraphs strongly supports a close relationship between structural and functional conservation. Based on this observation, we devised an algorithm for function prediction based on CCS. Using our method, for instance, we predict new functional annotations for human based on mouse proteins with a precision of 70%.

Indizierung von XML-Dokumenten mittels GRIPP (Florian Zipser)

Das Ziel meiner Studienarbeit ist, die von Silke Trissl entwickelte Indizierungsmethode GRIPP auf XML-Dokumente anzuwenden. GRIPP bietet die Möglichkeit, auch große relational gespeicherte Graphen effizient zu indizieren. Solche Techniken sind ein wichtiger Aspekt in der relationalen Speicherung von XML-Dokumenten. Die durch das W3C standardisierten Konzepte der XLinks und XIncludes erweitern die Baumstruktur eines „normalen“ XML-Dokumentes zu einem allgemeinen Graphen. Daher stellt sich auch hier die Frage nach effizienten Indizierungsmöglichkeiten.