Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/13190Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Fletcher, George H. L. | - |
| dc.contributor.author | GYSSENS, Marc | - |
| dc.contributor.author | LEINDERS, Dirk | - |
| dc.contributor.author | VAN DEN BUSSCHE, Jan | - |
| dc.contributor.author | Van Gucht, Dirk | - |
| dc.contributor.author | VANSUMMEREN, Stijn | - |
| dc.contributor.author | Wu, Yuqing | - |
| dc.date.accessioned | 2012-02-24T08:05:16Z | - |
| dc.date.available | 2012-02-24T08:05:16Z | - |
| dc.date.issued | 2012 | - |
| dc.identifier.citation | Lukasiewicz, Thomas; Sali, Attila (Ed.). Foundations of Information and Knowledge Systems, 7th International Symposium, FoIKS 2012, Kiel, Germany, March 5-9, 2012. Proceedings., Springer,p. 125-144 | - |
| dc.identifier.isbn | 9783642284717 | - |
| dc.identifier.issn | 0302-9743 | - |
| dc.identifier.uri | http://hdl.handle.net/1942/13190 | - |
| dc.description.abstract | Several established and novel applications motivate us to study the expressive power of navigational query languages on graphs, which represent binary relations. Our basic language has only the operators union and composition, together with the identity relation. Richer languages can be obtained by adding other features such as other set operators, projection and coprojection, converse, and the diversity relation. In this paper, we show that, when evaluated at the level of boolean queries with an unlabeled input graph (i.e., a single relation), adding transitive closure to the languages with coprojection adds expressive power, while this is not the case for the basic language to which none, one, or both of projection and the diversity relation are added. In combination with earlier work [10], these results yield a complete understanding of the impact of transitive closure on the languages under consideration. | - |
| dc.description.sponsorship | Fund of Scientific Research FWO - Flanders | - |
| dc.language.iso | en | - |
| dc.publisher | Springer | - |
| dc.relation.ispartofseries | LECTURE NOTES OF COMPUTER SCIENCE | - |
| dc.rights | Copyright Springer-Verlag Berlin Heidelberg 2012 | - |
| dc.title | The Impact of Transitive Closure on the Boolean Expressiveness of Navigational Query Languages on Graphs | - |
| dc.type | Proceedings Paper | - |
| local.bibliographicCitation.authors | Lukasiewicz, Thomas | - |
| local.bibliographicCitation.authors | Sali, Attila | - |
| local.bibliographicCitation.conferencedate | 5-9 March 2012 | - |
| local.bibliographicCitation.conferencename | 7th International Symposium on Foundations of Information and Knowledge Systems | - |
| local.bibliographicCitation.conferenceplace | Kiel, Germany | - |
| dc.identifier.epage | 143 | - |
| dc.identifier.spage | 124 | - |
| dc.identifier.volume | 7153 | - |
| local.bibliographicCitation.jcat | C1 | - |
| dc.relation.references | 1. RDF primer (2004), http://www.w3.org/TR/rdf-primer/ 2. Abiteboul, S., Buneman, P., Suciu, D.: Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann (1999) 3. Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison Wesley, Reading (1995) 4. Aho, A.V., Ullman, J.D.: The universality of data retrieval languages. In: Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, San Antonio, Texas, pp. 110–120 (January 1979) 5. Angles, R., Guti´errez, C.: Survey of graph database models. ACM Comput. Surv. 40(1), 1–39 (2008) 6. Baader, F., Calvanese, D., McGuiness, D., Nardi, D., Patel-Schneider, P. (eds.): The Description Logic Handbook. Cambridge University Press (2003) 7. Benedikt, M., Fan, W., Kuper, G.M.: Structural Properties of XPath Fragments. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol. 2572, pp. 79–95. Springer, Heidelberg (2002) 8. Bizer, C., Heath, T., Berners-Lee, T.: Linked data - the story so far. Int. J. Semantic Web Inf. Syst. 5(3), 1–22 (2009) 9. Blackburn, P., de Rijke, M., Venema, Y.: Modal Logic. Cambridge University Press (2001) 10. Fletcher, G.H.L., Gyssens, M., Leinders, D., Van den Bussche, J., Van Gucht, D., Vansummeren, S., Wu, Y.: Relative expressive power of navigational querying on graphs. In: Milo, T. (ed.) ICDT, pp. 197–207. ACM (2011) 11. Florescu, D., Levy, A., Mendelzon, A.: Database techniques for the World-Wide Web: A survey. SIGMOD Record 27(3), 59–74 (1998) 12. Franklin, M.J., Halevy, A.Y., Maier, D.: From databases to dataspaces: a new abstraction for information management. SIGMOD Record 34(4), 27–33 (2005) 13. Gyssens, M., Paredaens, J., Van Gucht, D., Fletcher, G.H.L.: Structural characterizations of the semantics of XPath as navigation tool on a document. In: Vansummeren, S. (ed.) PODS, pp. 318–327. ACM (2006) 14. Harel, D., Kozen, D., Tiuryn, J.: Dynamic Logic. MIT Press (2000) 15. Heath, T., Bizer, C.: Linked Data: Evolving the Web into a Global Data Space, 1st edn. Synthesis Lectures on the Semantic Web: Theory and Technology, vol. 1. Morgan & Claypool Publishers (February 2011) 16. Libkin, L.: Elements of Finite Model Theory. Springer, Berlin (2004) 17. Maddux, R.D.: Relation Algebras. Elsevier, Amsterdam (2006) 18. Mamoulis, N.: Efficient processing of joins on set-valued attributes. In: Proceedings ACM SIGMOD International Conference on Management of Data, pp. 157–168 (2003) 19. Marx, M., Venema, Y.: Multi-Dimensional Modal Logic. Springer, Heidelberg (1997) 20. Marx, M.: Conditional XPath. ACM Trans. Database Syst. 30(4), 929–959 (2005) 21. Marx, M., de Rijke, M.: Semantic characterizations of navigational XPath. SIGMOD Record 34(2), 41–46 (2005) 22. Pratt, V.R.: Origins of the calculus of binary relations. In: Proceedings 7th Annual IEEE Symposium on Logic in Computer Science, pp. 248–254 (1992) 23. Tarski, A.: On the calculus of relations. J. of Symbolic Logic 6(3), 73–89 (1941) 24. Tarski, A., Givant, S.: A Formalization of Set Theory without Variables. American Mathematical Society (1987) 25. Wu, Y., Van Gucht, D., Gyssens, M., Paredaens, J.: A study of a positive fragment of Path queries: Expressiveness, normal form and minimization. Comput. J. 54(7), 1091–1118 (2011) | - |
| local.type.refereed | Refereed | - |
| local.type.specified | Proceedings Paper | - |
| local.relation.ispartofseriesnr | 7153 | - |
| dc.bibliographicCitation.oldjcat | C2 | - |
| local.bibliographicCitation.btitle | Foundations of Information and Knowledge Systems, 7th International Symposium, FoIKS 2012, Kiel, Germany, March 5-9, 2012. Proceedings. | - |
| item.fullcitation | Fletcher, George H. L.; GYSSENS, Marc; LEINDERS, Dirk; VAN DEN BUSSCHE, Jan; Van Gucht, Dirk; VANSUMMEREN, Stijn & Wu, Yuqing (2012) The Impact of Transitive Closure on the Boolean Expressiveness of Navigational Query Languages on Graphs. In: Lukasiewicz, Thomas; Sali, Attila (Ed.). Foundations of Information and Knowledge Systems, 7th International Symposium, FoIKS 2012, Kiel, Germany, March 5-9, 2012. Proceedings., Springer,p. 125-144. | - |
| item.fulltext | With Fulltext | - |
| item.contributor | Fletcher, George H. L. | - |
| item.contributor | GYSSENS, Marc | - |
| item.contributor | LEINDERS, Dirk | - |
| item.contributor | VAN DEN BUSSCHE, Jan | - |
| item.contributor | Van Gucht, Dirk | - |
| item.contributor | VANSUMMEREN, Stijn | - |
| item.contributor | Wu, Yuqing | - |
| item.accessRights | Restricted Access | - |
| Appears in Collections: | Research publications | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| foiks2012.pdf Restricted Access | Non Peer-reviewed author version | 406.47 kB | Adobe PDF | View/Open Request a copy |
Page view(s)
58
checked on Sep 5, 2022
Download(s)
42
checked on Sep 5, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.