Recently research has deeply investigated the problem of querying semi-structured data and data which can be represented by means of graphs (e.g. object-oriented data, XML data, etc.). Typically queries on graph-like data, called path queries, are expressed by means of regular expressions denoting paths in the graph. The result of a path query is the set of nodes reachable by means of a path expressed by a specified regular expression. In this paper we investigate the problem of extracting a subgraph satisfying a given property from a given graph representing some information. We propose a new form of queries, called graph queries, whose answers are (marked) graphs having a particular structure, extracted from the source graph. We show that a simple form of graph grammars can be profitably used to define graph queries. The result of a graph query, using a grammar G over a database D, is a marked subgraph of D 'matching' a graph derived from G. We consider different types of graph grammars which can be used to query graph-like data and consider their expressiveness and complexity.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
|Titolo:||Graph Grammars for Querying Graph-like Data|
|Data di pubblicazione:||2001|
|Citazione:||Graph Grammars for Querying Graph-like Data / Flesca, Sergio; Furfaro, F.; Greco, Sergio. - In: ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE. - ISSN 1571-0661. - 50:3(2001), pp. 247-256. ((Intervento presentato al convegno GT-VMT 2001, Graph Transformation and Visual Modeling Techniques (Satellite Workshopof ICALP 2001) tenutosi a Crete, Greece nel 2001.|
|Appare nelle tipologie:||1.1 Articolo in rivista|