Umeå University's logo

umu.sePublications
Change search
Link to record
Permanent link

Direct link
Okulmus, Cem
Publications (4 of 4) Show all publications
Gottlob, G., Lanzinger, M., Okulmus, C. & Pichler, R. (2024). Fast parallel hypertree decompositions in logarithmic recursion depth. ACM Transactions on Database Systems, 49(1), Article ID 1.
Open this publication in new window or tab >>Fast parallel hypertree decompositions in logarithmic recursion depth
2024 (English)In: ACM Transactions on Database Systems, ISSN 0362-5915, E-ISSN 1557-4644, Vol. 49, no 1, article id 1Article in journal (Refereed) Published
Abstract [en]

Various classic reasoning problems with natural hypergraph representations are known to be tractable if a hypertree decomposition (HD) of low width exists. The resulting algorithms are attractive for practical use in fields like databases and constraint satisfaction. However, algorithmic use of HDs relies on the difficult task of first computing a decomposition of the hypergraph underlying a given problem instance, which is then used to guide the algorithm for this particular instance. The performance of purely sequential methods for computing HDs is inherently limited, yet the problem is, theoretically, amenable to parallelisation. In this article, we propose the first algorithm for computing hypertree decompositions that is well suited for parallelisation. The newly proposed algorithm log-k-decomp requires only a logarithmic number of recursion levels and additionally allows for highly parallelised pruning of the search space by restriction to so-called balanced separators. We provide a detailed experimental evaluation over the HyperBench benchmark and demonstrate that log-k-decomp outperforms the current state of the art significantly.

Place, publisher, year, edition, pages
ACM Digital Library, 2024
Keywords
CCS Concepts, Information systems, Relational database query languages, Mathematics of computing, Hypergraphs, Computing methodologies, Parallel algorithms
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-223094 (URN)10.1145/3638758 (DOI)2-s2.0-85189106116 (Scopus ID)
Available from: 2024-04-10 Created: 2024-04-10 Last updated: 2024-04-10Bibliographically approved
Calvanese, D., Okulmus, C., Ortiz, M. & Šimkus, M. (2023). On the way to temporal OBDA systems. In: Proceedings of the 15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2023): . Paper presented at 15th Alberto Mendelzon International Workshop on Foundations of Data Management, AMW 2023, Santiago de Chile, Chile, May 22-26, 2023. CEUR-WS
Open this publication in new window or tab >>On the way to temporal OBDA systems
2023 (English)In: Proceedings of the 15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2023), CEUR-WS , 2023Conference paper, Published paper (Refereed)
Abstract [en]

Extending the OBDA approach - where multiple data sources are exposed to users via a unified conceptual schema based on description logics - to also cover temporal reasoning has been a long standing goal, with many proposals over the last decades. To the best of our knowledge, these have yet to yield results in the form of systems or prototypes. As part of our ongoing work towards practical applicability, we identify here a number of key problems, which we believe have not been addressed suitably by previous works. Among these is the ability to deal with heterogeneous representations of time, the ability to deal with temporal inconsistencies, either due to missing value samples or conflicting values for a given time point and finally we also seek a suitable query language, where we in particular want compositionality - the ability to use the output of queries to form new temporal views on the data. We present here our initial ideas on how to meet these challenges.

Place, publisher, year, edition, pages
CEUR-WS, 2023
Series
CEUR Workshop proceedings, ISSN 1613-0073 ; 3409
Keywords
description logic, Ontology-based data access, temporal database
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-211805 (URN)2-s2.0-85162909647 (Scopus ID)
Conference
15th Alberto Mendelzon International Workshop on Foundations of Data Management, AMW 2023, Santiago de Chile, Chile, May 22-26, 2023
Funder
Knut and Alice Wallenberg Foundation
Available from: 2023-07-11 Created: 2023-07-11 Last updated: 2023-11-24Bibliographically approved
Gottlob, G., Lanzinger, M., Longo, D. M., Okulmus, C., Pichler, R. & Selzer, A. (2023). Reaching back to move forward: using old ideas to achieve a new level of query optimization. In: Proceedings of the 15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2023): . Paper presented at 15th Alberto Mendelzon International Workshop on Foundations of Data Management, AMW 2023, Santiago de Chile, Chile, May 22-26, 2023. CEUR-WS, Article ID 6.
Open this publication in new window or tab >>Reaching back to move forward: using old ideas to achieve a new level of query optimization
Show others...
2023 (English)In: Proceedings of the 15th Alberto Mendelzon International Workshop on Foundations of Data Management (AMW 2023), CEUR-WS , 2023, article id 6Conference paper, Published paper (Refereed)
Abstract [en]

Join queries involving many relations pose a severe challenge to today's query optimisation techniques. To some extent, this is due to the fact that these techniques do not pay sufficient attention to structural properties of the query. In stark contrast, the Database Theory community has intensively studied structural properties of queries (such as acyclicity and various notions of width) and proposed efficient query evaluation techniques through variants of Yannakakis' algorithm for many years. However, although most queries in practice actually are acyclic or have low width, structure-guided query evaluation techniques based on Yannakakis' algorithm have not found their way into mainstream database technology yet.

The goal of this work is to address this gap between theory and practice. We want to analyse the potential of considering the query structure for speeding up modern DBMSs in cases that have been traditionally challenging. To this end, we propose a rewriting of SQL queries into a sequence of SQL statements that force the DBMS to follow a Yannakakis-style query execution. Through first empirical results we show that structure-guided query evaluation can indeed make the evaluation of many difficult join queries significantly faster.

Place, publisher, year, edition, pages
CEUR-WS, 2023
Series
CEUR Workshop proceedings, ISSN 1613-0073 ; 3409
Keywords
large join queries, query optimization, Yannakakis' algorithm
National Category
Computer Sciences
Identifiers
urn:nbn:se:umu:diva-211822 (URN)2-s2.0-85162848779 (Scopus ID)
Conference
15th Alberto Mendelzon International Workshop on Foundations of Data Management, AMW 2023, Santiago de Chile, Chile, May 22-26, 2023
Funder
Wallenberg AI, Autonomous Systems and Software Program (WASP)
Available from: 2023-07-11 Created: 2023-07-11 Last updated: 2023-07-11Bibliographically approved
Dragovic, N., Okulmus, C. & Ortiz, M. (2023). Rewriting ontology-mediated navigational queries into cypher. In: Oliver Kutz; Carsten Lutz; Ana Ozaki (Ed.), Proceedings of the 36th international workshop on Description Logics (DL 2023): . Paper presented at 36th International Workshop on Description Logics, DL 2023, Rhodes, Greece, September 2-4, 2023. CEUR-WS
Open this publication in new window or tab >>Rewriting ontology-mediated navigational queries into cypher
2023 (English)In: Proceedings of the 36th international workshop on Description Logics (DL 2023) / [ed] Oliver Kutz; Carsten Lutz; Ana Ozaki, CEUR-WS , 2023Conference paper, Published paper (Refereed)
Abstract [en]

The ontology-based data access (OBDA) paradigm has successfully grown over the last decade as a powerful means to access data from possibly diverse and incomplete sources, using a domain ontology as a mediator. The ability to query generic graph-structured data is often highlighted as an advantage of OBDA, but in practice, existing solutions do not allow to access data in popular graph database management systems (DBMS) (e.g., Neo4j) that adopt the so-called 'property graph' data model and support dedicated query languages such as Cypher. Towards overcoming this major limitation, we propose a technique for ontology-mediated querying (OMQ) of property graphs. We tailor a suitable query language that supports path navigation in a form that can be naturally expressed in Cypher and other important graph query languages. It keeps the data complexity of query evaluation tractable even under trail semantics and is sufficient for our motivating use case in the autonomous driving domain. We address the semantic gap between the traditional path semantics adopted by most works on graph databases, and the trail semantics used in Cypher, and identify cases where both semantics coincide. To our knowledge, OMQs with trail semantics had not been addressed before. We develop a rewriting algorithm for queries mediated by DL-Lite ontologies that enables query answering using plain Cypher. The experimental evaluation of our proof-of-concept prototype on a sample set of use case queries reveals that the approach is promising, and can be a stepping stone to making OBDA applicable to data stored in graph DBMS.

Place, publisher, year, edition, pages
CEUR-WS, 2023
Series
CEUR workshop proceedings., E-ISSN 1613-0073 ; 3515
Keywords
Graph databases, Ontology-based data access, Property graphs, Query rewriting
National Category
Computer Sciences Computer Systems
Identifiers
urn:nbn:se:umu:diva-217217 (URN)2-s2.0-85176468627 (Scopus ID)
Conference
36th International Workshop on Description Logics, DL 2023, Rhodes, Greece, September 2-4, 2023
Available from: 2023-12-01 Created: 2023-12-01 Last updated: 2023-12-01Bibliographically approved
Organisations

Search in DiVA

Show all publications