Abstract
Graph data models provide flexibility and extensibility, which makes them well-suited to modelling data that may be irregular, complex, and evolving in structure and content. However, a consequence of this is that users may not be familiar with the full structure of the data, which itself may be changing over time, making it hard for users to formulate queries that precisely match the data graph and meet their information-seeking requirements. There is a need, therefore, for flexible querying systems over graph data that can automatically make changes to the user’s query so as to find additional or different answers, and so help the user to retrieve information of relevance to them. This chapter describes recent work in this area, looking at a variety of graph query languages, applications, flexible querying techniques and implementations.
Access provided by CONRICYT-eBooks. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Abiteboul S, Quass D, McHugh J, Widom J, Wiener J (1997) The LOREL query language for semistructured data. Int J Digit Libr 1(1):68–88
Aho AV, Hopcroft JE, Ullman JD (1974) The design and analysis of computer algorithms. Addison-Wesley, Reading
Alkhateeb F, Baget J, Euzenat J (2009) Extending SPARQL with regular expression patterns (for querying RDF). J Web Semantics 7(2):57–73
Almendros-Jimenez J, Luna A, Moreno G (2014) Fuzzy XPath queries in XQuery. In: Proceedings of OTM 2014, pp 457–472
Amer-Yahia S, Lakshmanan LVS, Pandit S (2004) FleXPath: flexible structure and full-text querying for XML. In: Proceedings of ACM SIGMOD 2004, pp 83–94
Angles R, Gutierrez C (2008) Survey of graph database models. ACM Comput Surv 40(1):1–39
Ayers R (1997) Databases for criminal intelligence analysis: knowledge representation issues. AI Soc 11:18–35
Babcock B, Chaudhuri S, Das G (2003) Dynamic sample selection for approximate query processing. In: Proceedings of ACM SIGMOD 2003, pp 539–550
Barcelo P, Hurtado CA, Libkin L, Wood PT (2010) Expressive languages for path queries over graph-structured data. In: Proceedings of PODS 2010, pp 3–14
Barcelo P, Libkin L, Lin AW, Wood PT (2012) Expressive languages for path queries over graph-structured data. ACM Trans Database Syst 37(4):1–46
Batini C, Lenzerini M, Navathe SB (1986) A comparative analysis of methodologies for database schema integration. ACM Comput Surv 18(4):323–364
Bordogna G, Psaila G (2008) Customizable flexible querying in classical relational databases. In: Handbook of research on fuzzy information processing in databases. IGI Global, Hershey, pp 191–217
Bosc P, Pivert O (1992) Some approaches for relational databases flexible querying. J Intell Inf Syst 1(3):323–354
Bosc P, Hadjali A, Pivert O (2009) Incremental controlled relaxation of failing flexible queries. J Intell Inf Syst 33(3):261–283
Bray T et al (eds) (2008) Extensible markup language (XML) 1.0, W3C Recommendation
Buche P, Dibie-Barthelemy J, Chebil H (2009) SPARQL querying of web data tables driven by an ontology. In: Proceedings of FQAS 2009
Buneman P, Fernandez M, Suciu D (2000) A query language and algebra for semistructured data based on structural recursion. VLDB J 9(1):76–110
Buratti G, Montesi D (2008) Ranking for approximated XQuery full-text queries. In: Proceedings of BNCOD 2008, pp 165–176
Calì A, Frosini R, Poulovassilis A, Wood PT (2014) Flexible querying for SPARQL. In: Proceedings of ODBASE 2014 (OTM Conferences), pp 473–490
Calvanese D, Giacomo GD, Lenzerini M, Vardi MY (2000) Containment of conjunctive regular path queries with inverse. In: Proceedings of KR 2000, pp 176–185
Cedeno J, Candan KS (2011) R2DF framework for ranked path queries over weighted RDF graphs. In: Proceedings of WIMS 2011
Chakrabarti K, Garofalakis M, Rastogi R, Shim K (2001) Approximate query processing using wavelets. VLDB J 10(2–3):199–223
Chen AC, Gao S, Karampelas P, Alhajj R, Rokne J (2011) Finding hidden links in terrorist networks by checking indirect links of different sub-networks. In: Counterterrorism and open source intelligence, pp 143–158
Chu W, Yang H, Chiang K, Minock M, Chow G, Larson C (1996) CoBase: a scalable and extensible cooperative information system. J Intell Inf Syst 6(2/3):223–259
Consens M, Mendelzon AO (1989) Expressing structural hypertext queries in GraphLog. In: Proceedings of ACM hypertext 1989, pp 269–292
Consens M, Mendelzon AO (1993) Low complexity aggregation in Graphlog and Datalog. Theor Comput Sci 116(1–2):95–116
Cruz IF, Mendelzon AO, Wood PT (1987) A graphical query language supporting recursion. In: Proceedings of SIGMOD 1987, pp 323–330
de Freitas S, Harrison I, Magoulas G, Papamarkos G, Poulovassilis A, van Labeke N, Mee A, Oliver M (2008) L4All: a web-service based system for lifelong learners. In: The learning grid handbook: concepts, technologies and applications. The future of learning, vol 2. IOS Press, Amsterdam
De Virgilio R, Maccioni A, Torlone R (2013) A similarity measure for approximate querying over RDF data. In: Proceedings of EDBT/ICDT 2013 workshops, pp 205–213
Deo N (2004) Graph theory with applications to engineering and computer science. PHI Learning, New Delhi
Dey S, Cuevas-Vicenttin V, Kohler S, Gribkoff E (2013) On implementing provenance-aware regular path queries with relational query engines. In: Proceedings of EDBT 2013, pp 214–223
Dolog P, Stuckenschmidt H, Wache H (2006) Robust query processing for personalized information access on the semantic web. In: Proceedings of FQAS 2006
Dolog P, Stuckenschmidt H, Wache H, Diederich J (2009) Relaxing RDF queries based on user and domain preferences. J Intell Inf Syst 33(3):239–260
Droste M, Kuich W, Vogler H (2009) Handbook of weighted automata. Springer, Berlin
Eckhardt A, Hornicak E, Vojtas P (2011) Evaluating top-k algorithms with various sources of data and user preferences. In: Proceedings of FQAS 2011, pp 258–269
Elbassuoni S, Ramanath M, Schenkel R, Sydow M, Weikum G (2009) Language model-based ranking for queries on RDF-graphs. In: Proceedings of CIKM 2009, pp 977–986
Elbassuoni S, Ramanath M, Weikum G (2011) Query relaxation for entity-relationship search. In: Proceedings of ESWC 2011 (Part 2)
Fan W, Li J, Ma S, Tang N, Wu Y (2011) Adding regular expressions to graph reachability and pattern queries. In: Proceedings of ICDE 2011, pp 39–50
Fan W, Wang X, Wu Y (2013) Diversified top-k graph pattern matching. PVLDB 6(13):1510–1521
Fernandez M, Suciu D (1998) Optimizing regular path expressions using graph schemas. In: Proceedings of ICDE 1998, pp 14–23
Fernandez M, Florescu D, Levy A, Suciu D (2000) Declarative specification of web sites with strudel. VLDB J 9(1):38–55
Finger J, Polyzotis N (2009) Robust and efficient algorithms for rank join evaluation. In: Proceedings of SIGMOD 2009
Fink R, Olteanu D (2011) On the optimal approximation of queries using tractable propositional languages. In: Proceedings of ICDT 2011, pp 174–185
Frosini R, Calì A, Poulovassilis A, Wood PT (2017) Flexible query processing for SPARQL. Semantic Web 8(4):533–563
Galindo J, Medina J, Pons O, Cubero C (1998) A server for fuzzy SQL queries. In: Proceedings of FQAS 1998, pp 164–174
Goble CA, Stevens R (2008) State of the nation in data integration for bioinformatics. J Biomed Inform 41(5):687–693
Gottlob G, Leone N, Scarcello F (2001) The complexity of acyclic conjunctive queries. J ACM 43(3):431–498
Grahne G, Thomo A (2001) Approximate reasoning in semi-structured databases. In: Proceedings of KRDB 2001
Grahne G, Thomo A (2006) Regular path queries under approximate semantics. Ann Math Artif Intell 46(1–2):165–190
Grahne G, Thomo A, Wadge WW (2007) Preferentially annotated regular path queries. In: Proceedings of ICDT 2007, pp 314–328
Gubichev A, Bedathur S, Seufert S (2013) Sparqling kleene: fast property paths in rdf-3x. In: Proceedings of 1st international workshop on graph data management experiences and systems (GRADES’13)
Gutierrez C, Hurtado C, Mendelzon AO (2004) Foundations of Semantic Web Databases. In: Proceedings of PODS 2004, pp 95–106
Halevy A, Rajaraman A, Ordille J (2006) Data integration: the teenage years. In: Proceedings of VLDB 2006, pp 9–16
Harris S, Seaborne A (eds) (2013) SPARQL 1.1 Query Language, W3C Recommendation
Hayes P (ed) (2004) RDF Semantics, W3C Recommendation
Heer J, Agrawala M, Willett M (2008) Generalized selection via interactive query relaxation. In: Proceedings of CHI 2008, pp 959–968
Hill J, Torson J, Guo B, Chen Z (2010) Toward ontology-guided knowledge-driven XML query relaxation. In: Proceedings of 2nd international conference on computational intelligence, modelling and simulation (CIMSiM) 2010, pp 448–453
Hogan A, Mellotte M, Powell G, Stampouli D (2012) Towards fuzzy query relaxation for RDF. In: Proceedings of ISWC 2012, pp 687–702
Huang H, Liu C (2010) Query relaxation for star queries on RDF. In: Proceedings of WISE 2010, pp 376–389
Huang H, Liu C, Zhou X (2008) Computing relaxed answers on RDF databases. In: Proceedings of WISE 2008, pp 163–175
Hurtado CA, Poulovassilis A, Wood PT (2008) Query relaxation in RDF. J Data Semantics X:31–61
Hurtado CA, Poulovassilis A, Wood PT (2009a) Finding top-k approximate answers to path queries. In: Proceedings of FQAS 2009, pp 465–476
Hurtado CA, Poulovassilis A, Wood PT (2009b) Ranking approximate answers to semantic web queries. In: Proceedings of ESWC 2009, pp 263–277
Ilyas I, Aref W, Elmagarmid A (2004) Supporting top-k join queries in relational databases. VLDB J 13:207–221
Ioannidis Y, Poosala V (1999) Histogram-based approximation of set-valued query-answers. In: Proceedings of VLDB 1999, pp 174–185
Kanza Y, Sagiv Y (2001) Flexible queries over semistructured data. In: Proceedings of ACM PODS 2001, pp 40–51
Kasneci G, Ramanath M, Suchanek F, Weikum G (2009) The YAGO-NAGA approach to knowledge discovery. ACM SIGMOD Rec 37(4):41–47
Kiefer C, Bernstein A, Stocker M (2007) The fundamentals of iSPARQL: a virtualtriple approach for similarity-based semantic web tasks. In: Proceedings of ISWC 2007
Kochut K, Janik M (2007) Extended SPARQL for semantic association discovery. In: Proceedings of ESWC 2007, pp 145–159
Koschmieder A, Leser U (2012) Regular path queries on large graphs. In: Proceedings of SSDBM 2012, pp 177–194
Lacroix Z, Murthy H, Naumann F, Raschid L (2004) Links and paths through life sciences data sources. In: Proceedings of DILS 2004, pp 203–211
Larriba-Pey J, Martinez-Bazan N, Dominguez-Sal D (2014) Introduction to graph databases. In: Proceedings of reasoning web 2014, pp 171–194
Leser U, Trissl S (2009) Graph management in the life sciences. In: Encyclopedia of database systems, pp 1266–1271
Libkin L, Vrgoc D (2012) Regular path queries on graphs with data. In: Proceedings of ICDT 2012, pp 74–85
Liu C, Li J, Yu J, Zhou R (2010) Adaptive relaxation forquerying heterogeneous XML data sources. Inf Syst 35(6):688–707
Ma S, Cao Y, Fan W, Huai J, Wo T (2014) Strong simulation: capturing topology in graph pattern matching. ACM Trans Database Syst 39(1):1–46
Mandreoli F, Martoglia R, Villani G, Penzo W (2009) Flexible query answering on graph-modeled data. In: Proceedings of EDBT 2009, pp 216–227
Martin MS, Gutierrez C, Wood PT (2011) A social networks query and transformation language. In: Proceedings of AMW 2011, pp 631–646
Mendelzon AO, Wood PT (1989) Finding regular simple paths in graph databases. In: Proceedings of VLDB 1989, pp 185–193
Mendelzon AO, Wood PT (1995) Finding regular simple paths in graph databases. SIAM J Comput 24(6):1235–1258
Meng X, Ma ZM, Yan L (2008) Providing flexible queries over web databases. In: Knowledge-based intelligent information and engineering systems, pp 601–606
Mishra C, Koudas N (2009) Interactive query refinement. In: Proceedings of EDBT 2009, pp 862–873
Munoz S, Pérez J, Gutierrez C (2007) Minimal deductive systems for RDF. In: Proceedings of ESWC 2007, pp 53–67
Na S, Park S (2005) A process of fuzzy query on new fuzzy object oriented data model. In: Proceedings of DEXA 2005, pp 500–509
Pérez J, Arenas M, Gutierrez C (2006) Semantics and complexity of SPARQL. In: Proceedings of ISWC 2006, pp 30–43
Pérez J, Arenas M, Gutierrez C (2008) nSPARQL: a navigational language for RDF. In: Proceedings of ISWC 2008, pp 66–81
Poulovassilis A, Wood PT (2010) Combining approximation and relaxation in semantic web path queries. In: Proceedings of ISWC 2010, pp 631–646
Poulovassilis A, Selmer P, Wood PT (2012) Flexible querying of lifelong learner metadata. IEEE Trans Learn Technol 5(2):117–129
Poulovassilis A, Gutierrez-Santos S, Mavrikis M (2015) Graph-based modelling of students’ interaction data from exploratory learning environments. In: Proceedings of GEDM 2015 (at Educational Data Mining 2015), pp 46–51
Poulovassilis A, Selmer P, Wood PT (2016) Approximation and relaxation of semantic web path queries. J Web Semant 40:1–21
Reddy BRK, Kumar PS (2010) Efficient approximate SPARQL querying of web of linked data. In: Proceedings of URSW 2010, pp 37–48
Sakr S, Elnikety S, He Y (2012) G-SPARQL: a hybrid engine for querying large attributed graphs. In: Proceedings of CIKM 2012, pp 335–344
Sarma D et al (2008) Bootstrapping pay-as-you-go data integration systems. In: Proceedings of SIGMOD 2008, pp 861–874
Sassi M, Tlili O, Ounelli H (2012) Approximate query processing for database flexible querying with aggregates. Trans Large-Scale Data- Knowl Centered Syst V:1–27
Selmer P (2016) Flexible querying of graph-structured data. PhD thesis, Birkbeck, University of London
Selmer P, Poulovassilis A, Wood PT (2015) Implementing flexible operators for regular path queries. In: Proceedings of GraphQ 2015 (EDBT/ICDT Workshops), pp 149–156
Siepen J et al (2008) ISPIDER Central: an integrated database web-server for proteomics. Nucleic Acids Res (Web-Server-Issue) 36:485–490
Suthers D (2015) From contingencies to network-level phenomena: multilevel analysis of activity and actors in heterogeneous networked learning environments. In: Proceedings of LAK 2015, pp 368–377
Theobald M, Schenkel R, Weikum G (2005) An efficient and versatile query engine for TopX search. In: Proceedings of VLDB 2005, pp 625–636
Vanhatalo J, Völzer H, Leymann F, Moser S (2008) Automatic workflow graph refactoring and completion. In: Proceedings of ICSOC 2008. Springer, Berlin, pp 100–115
Wood PT (2012) Query languages for graph databases. ACM SIGMOD Rec 41(1):50–60
Wu B, Ye Q, Yang S, Wang B (2009) Group CRM: a new telecom CRM framework from social network perspective. In: Proceedings of 1st ACM international workshop on complex networks meet information and knowledge management (CNIKM’09), pp 3–10
Wu Y, Yan X, Yang S (2013) Ontology-based subgraph querying. In: Proceedings of ICDE 2013, pp 697–708
Yakovets N, Godfrey P, Gryz J (2015) Towards query optimization for SPARQL property paths. arXiv preprint arXiv:150408262
Yang S, Wu Y, Sun H, Yan X (2014) Schemaless and structureless graph querying. Proc VLDB Endowment 7(7):565–576
Zhang S, Yang J, Jin W (2010) SAPPER: subgraph indexing and approximate matching in large graphs. PVLDB 3(1):1185–1194
Zhou X, Gaugaz J, Balke WT, Nejdl W (2007) Query relaxation using malleable schemas. In: Proceedings of ACM SIGMOD 2007, pp 545–556
Zhu L, Ng WK, Cheng J (2011) Structure and attribute index for approximate graph matching in large graphs. Inf Syst 36(6):958–972
Zou L, Mo J, Chen L, Ozsu MT, Zhao D (2011) gStore: answering SPARQL queries via subgraph matching. PVLDB 4(8):482–493
Acknowledgements
The author gratefully thanks Andrea Calì, Riccardo Frosini, Sergio Gutierrez-Santos, Carlos Hurtado, Manolis Mavrikis, Petra Selmer, Alex Wollenschlaeger and Peter Wood for our collaboration in the work described here.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this chapter
Cite this chapter
Poulovassilis, A. (2018). Applications of Flexible Querying to Graph Data. In: Fletcher, G., Hidders, J., Larriba-Pey, J. (eds) Graph Data Management. Data-Centric Systems and Applications. Springer, Cham. https://doi.org/10.1007/978-3-319-96193-4_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-96193-4_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-96192-7
Online ISBN: 978-3-319-96193-4
eBook Packages: Computer ScienceComputer Science (R0)