6533b7dafe1ef96bd126d896
RESEARCH PRODUCT
Efficient evaluation for a subset of recursive queries
Seppo SippuEljas Soisalon-soininenGösta Grahnesubject
Theoretical computer scienceComputer scienceLogic0102 computer and information sciences02 engineering and technologycomputer.software_genre01 natural sciencesDatalogSet (abstract data type)020204 information systemsGraph traversal0202 electrical engineering electronic engineering information engineeringComputer Science::Databasescomputer.programming_languageMathematicsDiscrete mathematicsProgramming languageBinary relationEfficient algorithmInformationSystems_DATABASEMANAGEMENT16. Peace & justiceTransformation (function)TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESrestrict010201 computation theory & mathematicscomputerdescription
Abstract We consider the efficient evaluation of recursive queries in logic databases where the queries are expressed using a Datalog program (function-free Horn-clause program) that contains only regularly or linearly recursive predicates. Using well-known results on graph traversal, we develop an efficient algorithm for evaluating relations defined by a binary-chain program. We also present a transformation by which the evaluation of a subset of queries involving nonbinary relations can be reduced to the evaluation of binary-chain queries. This transformation is guided by the choice of bound arguments in the query, and the bindings are propagated through the program so that in the evaluation of the transformed program the bindings will be used to restrict the set of database facts consulted.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1991-04-01 | Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems - PODS '87 |