Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/13198Full 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-24T12:22:59Z | - |
| dc.date.available | 2012-02-24T12:22:59Z | - |
| dc.date.issued | 2011 | - |
| dc.identifier.citation | Milo, Tova (Ed.). Database Theory - ICDT 2011, 14th International Conference, Uppsala, Sweden, March 21-24, 2011, Proceedings, ACM Press,p. 197-207 | - |
| dc.identifier.isbn | 978-1-4503-0529-7 | - |
| dc.identifier.uri | http://hdl.handle.net/1942/13198 | - |
| dc.description.abstract | Motivated by both established and new applications, we study navigational query languages for graphs (binary relations). The simplest language has only the two operators union and composition, together with the identity relation. We make more powerful languages by adding any of the following operators: intersection; set di erence; projection; coprojection; converse; transitive closure; and the diversity relation. All these operators map binary relations to binary relations. We compare the expressive power of all resulting languages. We do this not only for general path queries (queries where the result may be any binary relation) but also for boolean or yes/no queries (expressed by the nonemptiness of an expression). For both cases, we present the complete Hasse diagram of relative expressiveness. In particular, the Hasse diagram for boolean queries contains nontrivial separations and a few surprising collapses. | - |
| dc.description.sponsorship | Fund for Scientific Research FWO - Flanders | - |
| dc.language.iso | en | - |
| dc.publisher | ACM Press | - |
| dc.rights | Copyright 2011 ACM | - |
| dc.subject.other | XPath; graphs; relation algebra; indistinguishability; expressive power; finite variable logic | - |
| dc.title | Relative expressive power of navigational querying on graphs | - |
| dc.type | Proceedings Paper | - |
| local.bibliographicCitation.authors | Milo, Tova | - |
| local.bibliographicCitation.conferencedate | 21-24 March 2011 | - |
| local.bibliographicCitation.conferencename | 14th International Conference on Database Theory (ICDT 2011) | - |
| local.bibliographicCitation.conferenceplace | Uppsala, Sweden | - |
| dc.identifier.epage | 207 | - |
| dc.identifier.spage | 197 | - |
| local.bibliographicCitation.jcat | C1 | - |
| local.publisher.place | New York | - |
| dc.relation.references | [1] RDF primer, 2004. http://www.w3.org/TR/rdf-primer/. [2] S. Abiteboul, P. Buneman, and D. Suciu. Data on the Web: From Relations to Semistructured Data and XML. Morgan Kaufmann, 1999. [3] S. Abiteboul, R. Hull, and V. Vianu. Foundations of databases. Addison Wesley, Reading, MA, 1995. [4] R. Angles and C. Guti errez. Survey of graph database models. ACM Comput. Surv., 40(1):1-39, 2008. [5] F. Baader, D. Calvanese, D. McGuiness, D. Nardi, and P. Patel-Schneider, editors. The Description Logic Handbook. Cambridge University Press, 2003. [6] M. Benedikt, W. Fan, and G. M. Kuper. Structural properties of XPath fragments. In ICDT, pages 79-95, 2003. [7] C. Bizer, T. Heath, and T. Berners-Lee. Linked data - the story so far. Int. J. Semantic Web Inf. Syst., 5(3):1-22, 2009. [8] P. Blackburn, M. de Rijke, and Y. Venema. Modal Logic. Cambridge University Press, 2001. [9] D. Calvanese, G. D. Giacomo, M. Lenzerini, and M. Y. Vardi. Containment of conjunctive regular path queries with inverse. In KR, pages 176-185, 2000. [10] A. Deutsch and V. Tannen. Optimization properties for classes of conjunctive regular path queries. In DBPL, pages 21-39, 2001. [11] G. Fletcher, M. Gyssens, D. Leinders, J. Van den Bussche, D. Van Gucht, S. Vansummeren, and Y. Wu. Unpublished results, 2010. [12] D. Florescu, A. Levy, and A. Mendelzon. Database techniques for the World-Wide Web: A survey. SIGMOD Record, 27(3):59-74, 1998. [13] M. J. Franklin, A. Y. Halevy, and D. Maier. From databases to dataspaces: a new abstraction for information management. SIGMOD Record, 34(4):27-33, 2005. [14] S. G oller, M. Lohrey, and C. Lutz. PDL with intersection and converse: satis ability and in nite-state model checking. Journal of Symbolic Logic, 74(1):279-314, 2009. [15] V. Goranko and M. Otto. Model theory of modal logics. In P. Blackburn, J. van Benthem, and F. Wolter, editors, Handbook of Modal Logic, pages 249-329. Elsevier, 2007. [16] D. Harel, D. Kozen, and J. Tiuryn. Dynamic Logic. MIT Press, 2000. [17] R. D. Maddux. Relation algebras. Elsevier, Amsterdam, 2006. [18] N. Mamoulis. E cient processing of joins on set-valued attributes. In ACM SIGMOD, pages 157-168, 2003. [19] M. Marx. Conditional XPath. ACM Trans. Database Syst., 30(4):929-959, 2005. [20] M. Marx and M. de Rijke. Semantic characterizations of navigational XPath. SIGMOD Record, 34(2):41-46, 2005. [21] M. Marx and Y. Venema. Multi-Dimensional Modal Logic. Springer, 1997. [22] D. Olteanu. Forward node-selecting queries over trees. ACM Trans. Database Syst., 32(1):3, 2007. [23] M. Otto. Model theoretic methods for fragments of FO and special classes of ( nite) structures. Survey at 2006 Durham workshop on Finite and Algorithmic Model Theory, 2008. [24] R. Paige and R. Tarjan. Three partition re nement algorithms. SIAM J. Comput., 16(6):973-989, 1987. [25] V. R. Pratt. Origins of the calculus of binary relations. In LICS, pages 248-254, 1992. [26] A. Tarski and S. Givant. A formalization of set theory without variables. American Mathematical Society, 1987. [27] Y. Wu, D. Van Gucht, M. Gyssens, and J. Paredaens. A study of a positive fragment of path queries: expressiveness, normal form, and minimization. The Computer Journal, 2010. Published online, 11 July | - |
| local.type.refereed | Refereed | - |
| local.type.specified | Proceedings Paper | - |
| dc.bibliographicCitation.oldjcat | C2 | - |
| dc.identifier.doi | 10.1145/1938551.1938578 | - |
| local.bibliographicCitation.btitle | Database Theory - ICDT 2011, 14th International Conference, Uppsala, Sweden, March 21-24, 2011, Proceedings | - |
| item.fullcitation | Fletcher, George H. L.; GYSSENS, Marc; LEINDERS, Dirk; VAN DEN BUSSCHE, Jan; Van Gucht, Dirk; VANSUMMEREN, Stijn & Wu, Yuqing (2011) Relative expressive power of navigational querying on graphs. In: Milo, Tova (Ed.). Database Theory - ICDT 2011, 14th International Conference, Uppsala, Sweden, March 21-24, 2011, Proceedings, ACM Press,p. 197-207. | - |
| 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 | - |
| item.fulltext | With Fulltext | - |
| Appears in Collections: | Research publications | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| uppsala.pdf Restricted Access | Non Peer-reviewed author version | 309.49 kB | Adobe PDF | View/Open Request a copy |
SCOPUSTM
Citations
27
checked on Sep 3, 2020
Page view(s)
68
checked on Sep 7, 2022
Download(s)
56
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.